An authentication device includes circuitry that holds L (L≧2) secret keys si (i=1 to L) and L public keys yi that satisfy yi=F(si) with respect to a set F of multivariate polynomials of n-th order (n≧2). The circuitry also performs with a verifier, an interactive protocol for proving knowledge of (L−1) secret keys si that satisfy yi=F(si). The circuitry receives L challenges from the verifier, arbitrarily selects (L−1) challenges from the L challenges received. The circuitry also generates, by using the secret keys si, (L−1) responses respectively for the (L−1) challenges selected, and transmits the (L−1) responses generated.