A method authenticates d.sub.i identities in parallel using two prime numbers p and q such that q|p-1. Each identity includes a private key s.sub.i and a public key v.sub.i, and a publicly known generator is .alpha. such that .alpha..sup.q.ident.1 (mod p). A verifier is provided with an ordered list of the public keys v.sub.i. A prover selects uniformly at random a non-negative number r less than q. A number x=.alpha..sup.r (mod p) is sent from the prover to a verifier. The verifier selects uniformly at random a non-negative number e less than 2.sup.(t+logd), where log is base 2, and a number t is a predetermined security parameter. The prover receives from the verifier the number e. A number y=r+.SIGMA..sub.i s.sub.i*e.sup.i (mod q) is generated by the prover, and the number Y is sent to the verifier, who then determines if an equality x=.alpha..sup.y*.PI..sub.i(v.sub.i).sup.e.sup.i (mod p) is true. The prover is accepted as having the d.sub.i identities if and only if the equality is true. In a preferred embodiment the communications between the prover and the verifier is via a low-bandwidth optical channel.