Method for authenticating secret information which protects secret information

1. A computer-implemented method for authenticating secret information, the method comprising:

receiving, by an authentication server, Q{right arrow over (X)} from a terminal for registering secret information;

storing, by the authentication server, the received Q{right arrow over (X)};

receiving, by the authentication server, a vector {right arrow over (Z)} from a terminal for requesting authentication of secret information;

calculating, by the authentication server, the inner product of Q{right arrow over (X)} and {right arrow over (Z)};

calculating, by the authentication server, ½(n−the inner product); and

determining, by the authentication server, that the authentication is successful if ½(n−the inner product) is within a predetermined value and that the authentication fails otherwise,

wherein {right arrow over (X)} is a vector, having a length of n, of secret information to be registered, the elements of which consists of {−1, 1 } n ; Q is a matrix having m rows and n columns where m>n, the elements of which is randomly selected from q m×n ; {right arrow over (Y)} is a vector of secret information to be requested for authentication, the elements of which consists of {−1, 1} n ; and {right arrow over (Z)} is a vector which satisfies Q T {right arrow over (Z)}={right arrow over (Y)} where Q T is a transpose matrix of the matrix Q, and

wherein q m×n is defined by {0, 1, 2, . . . q−1}; and q, m, and n are positive integers.

2. The computer-implemented method for authenticating secret information according to claim 1 , wherein the matrix Q can be deleted after Q{right arrow over (X)} is received by the authentication server.

3. The computer-implemented method for authenticating secret information according to claim 1 , wherein at least one of Q{right arrow over (X)} and {right arrow over (Z)} is encrypted before transmission to the authentication server.

4. A computer-implemented method for authenticating secret information, the method comprising:

receiving, by an authentication server, Q{right arrow over (X)} from a terminal for registering secret information;

storing, by the authentication server, the received Q{right arrow over (X)};

receiving, by the authentication server, a vector {right arrow over (Z)} from a terminal for requesting authentication of secret information;

calculating, by the authentication server, the inner product of Q{right arrow over (X)} and {right arrow over (Z)};

calculating, by the authentication server, ½(n−the inner product); and

determining, by the authentication server, that the authentication is successful if ½(n−the inner product) is within a predetermined value and that the authentication fails otherwise,

wherein {right arrow over (X)} is a vector, having a length of n, of secret information to be registered, the elements of which consist of {−1, 1} n ; Q is a matrix having m rows and n columns where m>n, the elements of which are randomly selected from q m×n ; {right arrow over (Y)} is a vector of secret information to be requested for authentication, the elements of which consist of {−1,1} n ; {right arrow over (Z)} is a vector which satisfies Q T {right arrow over (Z)}={right arrow over (Y)}+{right arrow over (e)} where Q T is a transpose matrix of the matrix Q; and {right arrow over (e)} is an error vector having a length of n, the elements of which are randomly selected from q n , and

wherein q m×n and q n are defined by {0, 1, 2, . . . q−1}; and q, m, and n are positive integers.

5. The computer-implemented method for authenticating secret information according to claim 4 , wherein the matrix Q can be deleted after Q{right arrow over (X)} is received by the authentication server.

6. The computer-implemented method for authenticating secret information according to claim 4 , wherein at least one of Q{right arrow over (X)} and {right arrow over (Z)} is encrypted before transmission to the authentication server.

7. A computer-implemented method for authenticating secret information, the method comprising:

receiving, by an authentication server, a first ciphertext “SK X ” of a vector “{right arrow over (X)}”, having a length of k, of secret information to be registered from a terminal for registering secret information;

storing, by the authentication server, the received first ciphertext;

receiving, by the authentication server, a second ciphertext “C Y ” of a vector “{right arrow over (Y)}” of secret information to be requested for authentication of secret information from a terminal for requesting authentication of secret information;

calculating, by the authentication server, the inner product of “{right arrow over (X)}” and “{right arrow over (Y)}”;

calculating, by the authentication server, a distance for determining similarity based on the inner product; and

determining, by the authentication server, that the authentication is successful if the distance is within a predetermined value and that the authentication fails otherwise,

wherein the elements of “{right arrow over (X)}” consist of the elements of p k ; the first ciphertext “SK X ” is defined by

[

I

k

S

]

⁢

X

->

+

u

->

,

where I k is an identity matrix of k×k, the elements of the matrix “S” are randomly selected from q n×k and the elements of the vector “{right arrow over (u)}” are randomly selected from q m ; the elements of “{right arrow over (Y)}” consist of the elements of p k ; the second ciphertext “C Y ” is defined by

C

Y

:=

c

1

->

=

(

-

S

T

⁢

a

->

+

(

q

p

)

⁢

Y

->

+

e

->

,

a

->

⁢

←

$

⁢

ℤ

q

n

)

,

c

0

=

-

〈

u

->

,

c

1

->

〉

+

e

*

,

where S T is a transpose matrix of the matrix S, the symbol $ denotes that the elements of the left of the symbol are randomly selected from the right of the symbol, {right arrow over (e)} and e* are vectors having elements of real numbers; the elements of {right arrow over (e)} are randomly selected from q k and the elements of e* are randomly selected from q ; and

wherein q n×k , q m , and q n are defined by {0, 1, 2, . . . q−1}, p k is defined by {0, 1, 2, . . . p−1}, and q and q k are defined by [0, q); p, q, k, n and m are positive integer; q>p; and m=k+n.

8. The computer-implemented method for authenticating secret information according to claim 7 , wherein the elements of the error vectors {right arrow over (e)} and e* are selected with less distribution such that | {right arrow over (X)}, {right arrow over (e)} +e*| is less than

q

2

⁢

p

.

9. The computer-implemented method for authenticating secret information according to claim 8 , wherein the elements of “{right arrow over (X)}” and “{right arrow over (Y)}” consist of −1 or +1; and the distance for determining similarity is the hamming distance between “{right arrow over (X)}” and “{right arrow over (Y)}, which is ½ (k− {right arrow over (X)},{right arrow over (Y)} ).

10. The computer-implemented method for authenticating secret information according to claim 8 , wherein the elements of the matrix “S” are randomly selected from the subset of q where q is defined by {0, 1, 2, . . . q−1}.

11. The computer-implemented method for authenticating secret information according to claim 7 , wherein the elements of “{right arrow over (X)}” and “{right arrow over (Y)}” consist of −1 or +1; and the distance for determining similarity is the hamming distance between “{right arrow over (X)}” and “{right arrow over (Y)}, which is ½ (k− {right arrow over (X)},{right arrow over (Y)} ).

12. The computer-implemented method for authenticating secret information according to claim 7 , wherein the elements of the matrix “S” are randomly selected from the subset of q where q is defined by {0, 1, 2, . . . q−1}.