Authentication device, authentication method, and program
An authentication device includes circuitry that holds L (L≧2) secret keys s i (i=1 to L) and L public keys y i that satisfy y i =F(s i ) 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 s i that satisfy y i =F(s i ). 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 s i , (L−1) responses respectively for the (L−1) challenges selected, and transmits the (L−1) responses generated.
1. An authentication device comprising:
circuitry configured to
set sεK n to a secret key, and setting multi-order polynomials on a ring K, f i (x 1 , . . . , x n ) (i=1 to m) and y i =f i (s) to a public key;
transmit message c to a verifier;
receive information on one verification pattern selected from k (k≧3) verification patterns by the verifier according to one piece of the message c; and
transmit response information corresponding to the information on the verification pattern received, the response information being one of k ways of response information to the verifier,
wherein the response information is calculated using information zεK n in which the secret key s is masked by rεK n , t′εK n in which the r is masked by tεK n , polynomial f i ″(x) in which multi-order polynomials f i (x+r) related to x is masked by polynomial f i ′(x).
2. An authentication device according to claim 1 ,
wherein the multi-order polynomials f i (x 1 , . . . , x n ) (i=1 to m) is a second-order polynomial, and
the f i ′(x) is a first-order polynomial.
3. An authentication device according to claim 2 ,
wherein the first-order polynomial is a first-order polynomial f i (x+t)−−f i (x)−f i (t)+e i (e i εK) related to x.
4. An authentication device comprising:
circuitry configured to
set sεK n to a secret key, and setting second-order polynomials on a ring K, f i (x 1 , . . . , x n ) (i=1 to m) and y i =f i (s) to a public key;
transmit message c to a verifier;
receive information on one verification pattern selected from k (k≧3) verification patterns by the verifier according to one piece of the message c; and
transmit response information corresponding to the information on the verification pattern received, the response information being one of k ways of response information to the verifier,
wherein the response information is calculated using information zεK n in which the secret key s is masked by rεK n , t′εK n in which the r is masked by tεK n , e i ′εK in which f i (r) substituted by the r for the second-order polynomials f i is masked by e i εK.
5. An authentication method comprising:
setting, with circuitry, sεK n to a secret key, and setting multi-order polynomials on a ring K, f i (x 1 , . . . , x n ) (i=1 to m) and y i =f i (s) to a public key;
transmitting, with the circuitry, message c to a verifier;
receiving, with the circuitry, information on one verification pattern selected from k (k≧3) verification patterns by the verifier according to one piece of the message c; and
transmitting, with the circuitry, response information corresponding to the information on the verification pattern received, the response information being one of k ways of response information to the verifier,
wherein the response information is calculated using information zεK n in which the secret key s is masked by rεK n , t′εK n in which the r is masked by tεK n , polynomial f i ″(x) in which multi-order polynomials f i (x+r) related to x is masked by polynomial f i ′(x).
6. An authentication method comprising:
setting, with circuitry, sεK n to a secret key, and setting second-order polynomials on a ring K, f i (x 1 , . . . , x n ) (i=1 to m) and y i =f i (s) to a public key;
transmitting, with the circuitry, message c to a verifier;
receiving, with the circuitry, information on one verification pattern selected from k (k≧3) verification patterns by the verifier according to one piece of the message c; and
transmitting, with the circuitry, response information corresponding to the information on the verification pattern received, the response information being one of k ways of response information to the verifier,
wherein the response information is calculated using information zεK n in which the secret key s is masked by rεK n , t′εK n in which the r is masked by tεK n , e i ′εK in which f i (r) substituted by the r for the second-order polynomials f i is masked by e i εK.
7. A non-transitory computer readable medium including computer executable instructions causing a computer to perform operations comprising:
setting SεK n to a secret key, and setting multi-order polynomials on a ring K, f i (x 1 , . . . , x n ) (i=1 to m) and y i =f i (s) to a public key;
transmitting message c to a verifier;
receiving information on one verification pattern selected from k (k≧3) verification patterns by the verifier according to one piece of the message c; and
transmitting response information corresponding to the information on the verification pattern received, the response information being one of k ways of response information to the verifier,
wherein the response information is calculated using information zεK n in which the secret key s is masked by rεK n , t′εK n in which the r is masked by tεK n , polynomial f i ″(x) in which multi-order polynomials f i (x+r) related to x is masked by polynomial f i ′(x).
8. A non-transitory computer readable medium including computer executable instructions causing a computer to perform operations comprising:
setting sεK n to a secret key, and setting second-order polynomials on a ring K, f i (x 1 , . . . , x n ) (i=1 to m) and y i =f i (s) to a public key;
transmitting message c to a verifier;
receiving information on one verification pattern selected from k (k≧3) verification patterns by the verifier according to one piece of the message c; and
transmitting response information corresponding to the information on the verification pattern received, the response information being one of k ways of response information to the verifier,
wherein the response information is calculated using information zεK n in which the secret key s is masked by rεK n , t′εK n in which the r is masked by tεK n , e i ′εK in which f i (r) substituted by the r for the second-order polynomials f i is masked by e i εK.