A method authenticates di identities in parallel using two prime numbers p and q such that q|p−1. Each identity includes a private key si and a public key vi, and a publicly known generator is α such that αq≡1 (mod p). A verifier is provided with an ordered list of the public keys vi. A prover selects uniformly at random a non-negative number r less than q. A number x=α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(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+Σi si*ei (mod q) is generated by the prover, and the number Y is sent to the verifier, who then determines if an equality x=αy*Πi(vi)ei (mod p) is true. The prover is accepted as having the di 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.