AUTHENTICATION DEVICE, AUTHENTICATION METHOD, AND PROGRAM

摘要

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.

主权项

1. An authentication device comprising:
a Central Processing Unit (CPU) configured to:
generate 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); andperform, with a verifier, an interactive protocol for proving knowledge of (L−1) secret keys si that satisfy yi=F(si), wherein to perform the interactive protocol the CPU is configured to:
receive L challenges Chi from the verifier,arbitrarily select (L−1) challenges Chi from the L challenges Chi received from the verifier,generate, by using the secret keys si, (L−1) responses Rspi respectively for the selected (L−1) challenges Chi, andtransmit the generated (L−1) responses Rspi to the verifier.