Abstract:
A cryptographic processing device includes a processor that generates a first encrypted polynomial, a receiver that receives cryptographic information representing a fourth encrypted polynomial, and cryptographic information representing a second random number, the fourth encrypted polynomial including a first operation result that is a result of an operation of a fifth vector and a sixth vector, the first operation result being obtained by a second encrypted polynomial and a third encrypted polynomial, wherein the second encrypted polynomial is obtained based on the first encrypted polynomial, the second random number, and a second polynomial that corresponds to a third vector obtained by adding zero to the second vector, and the third encrypted polynomial is obtained based on the fifth vector obtained by adding zero to a fourth vector. The processor generates a second operation result that is a result of an operation of the second vector and the fourth vector.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
       [0001]    This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2015-047742, filed on Mar. 10, 2015, the entire contents of which are incorporated herein by reference. 
       FIELD 
       [0002]    The embodiments discussed herein are related to a cryptographic processing device and a cryptographic processing method. 
       BACKGROUND 
       [0003]    While regulations to protect personal information and confidential information have recently been tightened, the market of the services that use on such information has been expanding. A service that uses the information on the positions of personal users that can be obtained from their smartphones is an example of such a service. 
         [0004]    Thus, securing technologies that permit using of personal information or confidential information that remains protected have been attracting attention. Among the securing technologies, there is a method that uses a cryptographic technology or a statistical technology according to a data type or service requirements. 
         [0005]    A homomorphic encryption technology is known as a securing technology that uses a cryptographic technology. The homomorphic encryption technology is one of the public key encryption methods in which a pair of different keys is used for encryption and decryption, and has a function that permits a data operation in a state in which the data remains encrypted. For example, an encryption function E of a homomorphic encryption with respect to addition and multiplication has the characteristics as described in the following formulas for a plain text m 1  and a plain text m 2 : 
         [0000]        E ( m 1)+ E ( m 2)= E ( m 1+ m 2)   (1)
 
         [0000]        E ( m 1)* E ( m 2)= E ( m 1* m 2)   (2)
 
         [0006]    Formula (1) indicates that it is homomorphic for addition, and Formula (2) indicates that it is homomorphic for multiplication. As described above, according to the homomorphic encryption technology, when performing, on two or more encrypted texts, an operation that corresponds to an addition or multiplication, an encrypted text that is a result of an operation of adding or multiplying the original plain texts can be obtained without decrypting the encrypted texts. 
         [0007]    Such characteristics of a homomorphic encryption have been expected to be used in the field of e-voting or e-money, or in the field of cloud computing, in recent years. As a homomorphic encryption with respect to addition or multiplication, the Rivest Shamir Adleman (RSA) encryption that only permits multiplication to be performed and the Additive ElGamal encryption that only permits addition to be performed are known. 
         [0008]    Further, a homomorphic encryption that satisfies Formulas (1) and (2) was proposed in 2009 that permits both addition and multiplication to be performed (see, for example, Non Patent Document 1). Non Patent Document 1 only discloses a theoretical method for realizing a homomorphic encryption, and does not disclose a practical constructing method. However, in recent years, a practical constructing method of a somewhat homomorphic encryption has been proposed that permits both addition and multiplication to be performed (see, for example, Non Patent Document 2). 
         [0009]    For a secured distance calculation using a homomorphic encryption, a cryptographic processing device that permits a reduction in both a size of encrypted vector data and a time for the secured distance calculation is also known (see, for example, Patent Document 1). This cryptographic processing device obtains a first polynomial from a first vector by use of a first transform polynomial and a second polynomial from a second vector by use of a second transform polynomial. Then, the cryptographic processing device obtains a first weight that relates to a secured distance of the first vector and a second weight that relates to a secured distance of the second vector. 
         [0010]    Next, the cryptographic processing device encrypts each of the first polynomial, the second polynomial, the first weight, and the second weight using a homomorphic encryption, so as to obtain a first encrypted polynomial, a second encrypted polynomial, a first encrypted weight, and a second encrypted weight. Then, the cryptographic processing device obtains an encrypted secured distance that corresponds to an encryption of a secured distance between the first vector and the second vector from the first encrypted polynomial, the second encrypted polynomial, the first encrypted weight, and the second encrypted weight. 
         [0011]    Patent Document 1: Japanese Laid-open Patent Publication No. 2014-126865 
         [0012]    Non Patent Document 1: C. Gentry, “Fully Homomorphic Encryption Using Ideal Lattices”, STOC 2009, pp. 169-178, 2009. 
         [0013]    Non Patent Document 2: K. Lauter, M. Naehrig and V. Vaikuntanathan, “Can Homomorphic Encryption be Practical?”, In ACM workshop on Cloud Computing Security Workshop-CCSW 2011, ACM, pp. 113-124, 2011. 
       SUMMARY 
       [0014]    According to an aspect of the invention, a cryptographic processing device includes a processor, a transmitter, and a receiver. 
         [0015]    The processor generates a first encrypted polynomial by encrypting a first polynomial that corresponds to a first vector obtained by adding a first random number to a zero vector as a component. 
         [0016]    The transmitter transmits, to a terminal, first cryptographic information that represents the first encrypted polynomial. 
         [0017]    The receiver receives, from a calculation device, second cryptographic information that represents a fourth encrypted polynomial, and receives, from the calculation device, third cryptographic information that represents a second random number, the fourth encrypted polynomial including a first operation result that is a result of an operation of a fifth vector and a sixth vector that is obtained by adding, to a second vector, a result of a multiplication of the first random number by the second random number as a component, the first operation result being obtained by calculating from a second encrypted polynomial and a third encrypted polynomial, wherein the second encrypted polynomial is obtained by adding a result of a multiplication of the first encrypted polynomial by the second random number to a second polynomial that corresponds to a third vector obtained by adding zero to the second vector as a component, and the third encrypted polynomial is obtained by encrypting a third polynomial that corresponds to the fifth vector obtained by adding zero to a fourth vector as a component. 
         [0018]    The processor decrypts the second cryptographic information and the third cryptographic information. 
         [0019]    On the basis of a result of decrypting the second cryptographic information and a result of decrypting the third cryptographic information, the processor generates a second operation result that is a result of an operation of the second vector and the fourth vector. 
         [0020]    The object and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the claims. 
         [0021]    It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are not restrictive of the invention, as claimed. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0022]      FIG. 1  is a block diagram of a biometric system using encrypted polynomials; 
           [0023]      FIG. 2  is a block diagram of a biometric system according to an embodiment; 
           [0024]      FIG. 3  is a flowchart of a cryptographic process according to the embodiment; and 
           [0025]      FIG. 4  is a block diagram of an information processing device (a computer). 
       
    
    
     DESCRIPTION OF EMBODIMENTS 
       [0026]    Embodiments of the present invention will now be described in detail with reference to the drawings. 
         [0027]    Section 3.2 of Non Patent Document 2 discloses a practical constructing method of a homomorphic encryption. According to this method, three key-generating parameters (n,q,t) are mainly used to generate an encryption key. n is an integer that is a power of two, and is referred to as a lattice dimension. q is a prime, and t is an integer that is less than the prime q. 
         [0028]    In the process of the encryption key generation, first, a polynomial sk of degree n−1 in which each coefficient is very small is generated as a secret key at random. The value of each coefficient is restricted by a certain parameter σ. Next, a polynomial a 1  of degree n−1 in which each coefficient is less than q and a polynomial e of degree n−1 in which each coefficient is very small are generated at random. Then, the following formula for a polynomial a 0  is calculated, and a pair of polynomials (a 0 ,a 1 ) is defined as a public key pk. 
         [0000]        a 0=−( a 1* sk+t*e )   (11)
 
         [0029]    However, in a calculation of the polynomial a 0 , a polynomial whose degree is lower than n is always calculated by using “x n =−1, x n+1 =−x, . . . ” with respect to a polynomial whose degree is higher than or equal to n. Further, as a coefficient in each term included in a polynomial, a remainder obtained by dividing the coefficient by a prime q is used. A space in which such a polynomial operation is performed is often technically represented as R q :=F q [x]/(x n +1). 
         [0030]    Next, for plaintext data m that is represented by a polynomial of degree n−1 in which each coefficient is less than t and a public key pk, three polynomials u, f, and g of degree n−1 in which each coefficient is very small are generated at random, and cryptographic data Enc(m,pk) of the plaintext data m is defined by the following formulas: 
         [0000]        Enc ( m,pk )=( c 0, c 1)   (12)
 
         [0000]        c 0= a 0* u+t*g+m    (13)
 
         [0000]        c 1= a 1* u+t*f    (14)
 
         [0031]    The polynomial operation in the space R q  is also used for a calculation of the polynomial c 0  and the polynomial c 1 . In this case, a cryptographic addition for cryptographic data Enc(m 1 ,pk)=(c 0 ,c 1 ) and cryptographic data Enc(m 2 ,pk)=(d 0 ,d 1 ) is performed by the following formula: 
         [0000]        Enc ( m 1, pk )+ Enc ( m 2, pk )=( c 0+ d 0, c 1+ d 1)   (15)
 
         [0032]    Further, a cryptographic multiplication for the cryptographic data Enc(m 1 ,pk) and the cryptographic data Enc(m 2 ,pk) is performed by the following formula: 
         [0000]        Enc ( m 1, pk )* Enc ( m 2, pk )=( c 0* d 0, c 0* d 1+ c 1* d 0, c 1* d 1)   (16)
 
         [0033]    When performing the cryptographic multiplication by Formula (16), the cryptographic data changes from that of a two-dimensional vector to that of three-dimensional vector. If the cryptographic multiplication is repeated several times, there is a further increase in the elements of the cryptographic data that is a multiplication result. 
         [0034]    Next, decryption processing is described. The cryptographic data c=(c 0 ,c 1 ,c 2 , . . . ) in which the elements have increased as a result of an operation such as a several-times cryptographic multiplication is decrypted by calculating the following formula for a decryption result Dec(c,sk) by use of a secret key sk. 
         [0000]        Dec ( c,sk )=[ c 0+ c 1* sk+c 2* sk   2 + . . . ] q    mod t    (17)
 
         [0035]    In Formula (17), [f(x)] q  mod t represents a polynomial in which each coefficient z i  in a polynomial f(x) is replaced with [z i ] q  mod t. A value of [z] q  for an integer z is defined by the following formula by use of a remainder w obtained by dividing z by q: 
         [0000]      [ z]   q   =w  (in case of  w&lt;q/ 2)   (18)
 
         [0000]      [ z]   q   =w−q  (in case of  w≧q/ 2)   (19)
 
         [0036]    Thus, the range of values of [z] q  is [−q/2,q/2). Further, a mod t represents a remainder obtained by dividing an integer a by t. 
         [0037]    Taking (n,q,t)=(4,1033,20) for example, the following polynomial is a simple example of a secret key sk, a public key pk, and cryptographic data Enc(m,pk): 
         [0000]        sk=Mod ( Mod (4,1033)* x   3   +Mod (4,1033)* x   2   +Mod (1,1033)* x,x   4 +1)   (20)
 
         [0000]        pk= ( a 0, a 1)   (21)
 
         [0000]                    a                 0     =     Mod        (             Mod        (     885   ,   1033     )       *          x   3       +         Mod        (     519   ,   1033     )       *          x   2       +         Mod        (     621   ,   1033     )       *        x     +     Mod        (     327   ,   1033     )         ,       x   4     +   1       )               (   22   )                 a                 1     =     Mod        (             Mod        (     661   ,   1033     )       *          x   3       +         Mod        (     625   ,   1033     )       *          x   2       +         Mod        (     861   ,   1033     )       *        x     +     Mod        (     311   ,   1033     )         ,       x   4     +   1       )               (   23   )                 Enc ( m,pk )=( c 0, c 1)   (24)
 
         [0000]        m= 3+2 x+ 2 x   2 +2 x   3    (25)
 
         [0000]    
       
         
           
             
               
                 
                   
                     c 
                      
                     
                         
                     
                      
                     0 
                   
                   = 
                   
                     Mod 
                      
                     
                       ( 
                       
                         
                           
                             
                               
                                 Mod 
                                  
                                 
                                   ( 
                                   
                                     822 
                                     , 
                                     1033 
                                   
                                   ) 
                                 
                               
                               * 
                             
                              
                             
                               x 
                               3 
                             
                           
                           + 
                           
                             
                               
                                 Mod 
                                  
                                 
                                   ( 
                                   
                                     1016 
                                     , 
                                     1033 
                                   
                                   ) 
                                 
                               
                               * 
                             
                              
                             
                               x 
                               2 
                             
                           
                           + 
                           
                             
                               
                                 Mod 
                                  
                                 
                                   ( 
                                   
                                     292 
                                     , 
                                     1033 
                                   
                                   ) 
                                 
                               
                               * 
                             
                              
                             x 
                           
                           + 
                           
                             Mod 
                              
                             
                               ( 
                               
                                 243 
                                 , 
                                 1033 
                               
                               ) 
                             
                           
                         
                         , 
                         
                           
                             x 
                             4 
                           
                           + 
                           1 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   26 
                   ) 
                 
               
             
             
               
                 
                   
                     c 
                      
                     
                         
                     
                      
                     1 
                   
                   = 
                   
                     Mod 
                      
                     
                       ( 
                       
                         
                           
                             
                               
                                 Mod 
                                  
                                 
                                   ( 
                                   
                                     840 
                                     , 
                                     1033 
                                   
                                   ) 
                                 
                               
                               * 
                             
                              
                             
                               x 
                               3 
                             
                           
                           + 
                           
                             
                               
                                 Mod 
                                  
                                 
                                   ( 
                                   
                                     275 
                                     , 
                                     1033 
                                   
                                   ) 
                                 
                               
                               * 
                             
                              
                             
                               x 
                               2 
                             
                           
                           + 
                           
                             
                               
                                 Mod 
                                  
                                 
                                   ( 
                                   
                                     628 
                                     , 
                                     1033 
                                   
                                   ) 
                                 
                               
                               * 
                             
                              
                             x 
                           
                           + 
                           
                             Mod 
                              
                             
                               ( 
                               
                                 911 
                                 , 
                                 1033 
                               
                               ) 
                             
                           
                         
                         , 
                         
                           
                             x 
                             4 
                           
                           + 
                           1 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   27 
                   ) 
                 
               
             
           
         
       
     
         [0038]    In Formulas (20) to (27), Mod(a,q) represents a remainder obtained by dividing an integer a by a prime q, and Mod(f(x), x 4 +1) represents a remainder (polynomial) obtained by dividing a polynomial f(x) by a polynomial x 4 +1. For example, Mod(f(x),x 4 +1) for f(x)=x 4  is equal to Mod(f(x),x 4 +1) for f(x)=−1, and Mod(f(x),x 4 +1) for f(x)=x 5  is equal to Mod(f(x),x 4 +1) for f(x)=−x. 
         [0039]    The two pieces of cryptographic data, Enc(f(x),pk) and Enc(g(x),pk), for the two polynomials of a degree not higher than n−1, f(x) and g(x), have characteristics with respect to addition and multiplication as described in the following formulas: 
         [0000]        Enc ( f ( x ), pk )+ Enc ( g ( x ), pk )= Enc ( f ( x )+ g ( x ), pk )   (31)
 
         [0000]        Enc ( f ( x ), pk )* Enc ( g ( x ), pk )= Enc ( f ( x )* g ( x ), pk )   (32)
 
         [0040]    Further, a cryptographic processing device of Patent Document 1 permits a great improvement in processing time and a size of cryptographic data by performing a polynomial transformation to represent the vector data as one polynomial and encrypting the polynomial by a homomorphic encryption. 
         [0041]    In this cryptographic processing device, for example, the following two d-dimensional vectors are used as input data: 
         [0000]        A =( a   0   , a   1   , . . . , a   n-1 )   (41)
 
         [0000]        B =( b   0   , b   1   , . . . , b   n 1 )   (42)
 
         [0042]    The following two types of polynomial transformation, for example, an ascending-order transformation and a descending-order transformation, are used to calculate an inner product or a distance of two vectors at a high speed in a state in which those two vectors remain encrypted. 
       [Ascending-Order Transformation] 
       [0043]    
       
         
           
             
               
                 
                   A 
                   = 
                   
                     
                       
                         ( 
                         
                           
                             a 
                             0 
                           
                           , 
                           
                             a 
                             1 
                           
                           , 
                           
                             a 
                             2 
                           
                           , 
                           … 
                            
                           
                               
                           
                           , 
                           
                             a 
                             
                               n 
                               - 
                               1 
                             
                           
                         
                         ) 
                       
                        
                       
                         
 
                       
                       ⇒ 
                       
                         pm 
                          
                         
                             
                         
                          
                         1 
                          
                         
                           ( 
                           A 
                           ) 
                         
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           0 
                         
                         
                           n 
                           - 
                           1 
                         
                       
                        
                       
                           
                       
                        
                       
                         
                           a 
                           i 
                         
                          
                         
                           x 
                           i 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   43 
                   ) 
                 
               
             
           
         
       
     
       [Descending-Order Transformation] 
       [0044]    
       
         
           
             
               
                 
                   B 
                   = 
                   
                     
                       
                         ( 
                         
                           
                             b 
                             0 
                           
                           , 
                           
                             b 
                             1 
                           
                           , 
                           
                             b 
                             2 
                           
                           , 
                           … 
                            
                           
                               
                           
                           , 
                           
                             b 
                             
                               n 
                               - 
                               1 
                             
                           
                         
                         ) 
                       
                        
                       
                         
 
                       
                       ⇒ 
                       
                         pm 
                          
                         
                             
                         
                          
                         2 
                          
                         
                           ( 
                           B 
                           ) 
                         
                       
                     
                     = 
                     
                       - 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             0 
                           
                           
                             n 
                             - 
                             1 
                           
                         
                          
                         
                             
                         
                          
                         
                           
                             b 
                             i 
                           
                            
                           
                             x 
                             
                               n 
                               - 
                               i 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   44 
                   ) 
                 
               
             
           
         
       
     
         [0045]    When encrypting the polynomial pm 1 (A) and the polynomial pm 2 (B) by a homomorphic encryption, an encrypted polynomial E(pm 1 (A)) and an encrypted polynomial E(pm 2 (B)) are generated. 
         [0000]        E ( pm 1( A ))= Enc ( pm 1( A ), pk )   (45)
 
         [0000]        E ( pm 2( B ))= Enc ( pm 2( B ), pk )   (46)
 
         [0046]    When multiplying the encrypted polynomial E(pm 1 (A)) by the encrypted polynomial E(pm 2 (B)), a multiplication pm 1 (A)*pm 2 (B) is performed in a state in which the polynomials remain encrypted. Then, when decrypting a multiplication result E(pm 1 (A))*E(pm 2 (B)), a constant term included in a polynomial that is a decryption result is a value such as the following formula: 
         [0000]      Σ i=0   n-1   a   i   b   i   =a   0   b   0   =a   1   b   1   + . . . +a   n-1   b   n-1    (47)
 
         [0047]    Formula (47) represents an inner product of a vector A and a vector B. According to this method, it is possible to calculate the inner product more efficiently than by using the method for encrypting respective elements of the vector A and the vector B and multiplying them. Further, it is also possible to calculate, for example, a Hamming distance or an L2 norm at a high speed in a state in which they remain encrypted, using this inner calculation. 
         [0048]      FIG. 1  is a block diagram of an example of a biometric system for which the cryptographic processing device disclosed in Patent Document 1 is used. The biometric system in  FIG. 1  is a personal authentication system that uses biometric information, and includes a terminal  101 , a calculation device  102 , and an authentication device  103 . The calculation device  102  is connected to the terminal  101  and the authentication device  103  via a communication network. The terminal  101  is, for example, a device of a user such as a client terminal, and the calculation device  102  and the authentication device  103  are, for example, a server. The terminal  101  has a public key of a homomorphic encryption and the authentication device  103  has a secret key of a homomorphic encryption. 
         [0049]    While the biometric system is a personal authentication system that can easily be used because a user does not have to remember complicated information such as a password, it is desirable to provide strong protections against, for example, leaks of biometric information because the biometric information is permanent confidential information for the user. Thus, in the biometric system in  FIG. 1 , biometric information of a user is protected using a homomorphic encryption. 
         [0050]    When registering biometric information, the terminal  101  obtains biometric information on a user who is a registrant using a sensor, transforms the feature information extracted from the biometric information into a vector A as described in Formula (41), and performs encryption processing  111 - 1 . As biometric information obtained by a sensor, image information such as a fingerprint, a face, a vein, and an iris, or phonetic information such as a voice can be used. 
         [0051]    In the encryption processing  111 - 1 , the terminal  101  transforms the vector A into a polynomial pm 1 (A) as described in Formula (43), and encrypts the polynomial pm 1 (A) using a homomorphic encryption so as to generate an encrypted polynomial E(pm 1 (A)). Then, the terminal  101  transmits cryptographic information that represents the encrypted polynomial E(pm 1 (A)) to the calculation device  102 . The calculation device  102  registers the cryptographic information received from the terminal  101  in a database as a template  112  that represents registered biometric information. 
         [0052]    When authenticating biometric information, the terminal  101  obtains biometric information on a user who is a target to be authenticated, transforms feature information extracted from the biometric information into a vector B as described in Formula (42), and performs encryption processing  111 - 2 . 
         [0053]    In the encryption processing  111 - 2 , the terminal  101  transforms the vector B into a polynomial pm 2 (B) as described in Formula (44), and encrypts the polynomial pm 2 (B) using a homomorphic encryption so as to generate an encrypted polynomial E(pm 2 (B)). Then, the terminal  101  transmits cryptographic information that represents the encrypted polynomial E(pm 2 (B)) to the calculation device  102 . 
         [0054]    The calculation device  102  performs a cryptographic operation by use of the encrypted polynomial E(pm 1 (A)) represented by the template  112  and the encrypted polynomial E(pm 2 (B)) represented by the cryptographic information received from the terminal  101 , and transmits cryptographic information that represents a result of the cryptographic operation to the authentication device  103 . 
         [0055]    The authentication device  103  performs authentication processing  114  on the basis of the cryptographic information received from the cryptographic processing device  101 . In the authentication processing  114 , the authentication device  103  generates a result of an operation of the vector A and the vector B by decrypting the received cryptographic information, and performs authentication on the basis of the generated result of the operation. 
         [0056]    For example, a distance between the vector A and the vector B (such as a Hamming distance) is used as the result of the operation of the vector A and the vector B. In this case, the calculation device  102  can calculate the distance between the vector A and the vector B in a state in which the two vectors remain encrypted, and the authentication device  103  can determine whether authentication has been successful by comparing the distance to a threshold. It is determined that the authentication of the target to be authenticated has been successful when the distance is less than the threshold, and it is determined that the authentication has been unsuccessful when the distance is not less than the threshold. 
         [0057]    According to such a biometric system, the terminal  101  only transmits encrypted information to the calculation device  102 , and the calculation device  102  does not have a secret key, so the calculation device  102  never knows the vectors that represent biometric information of a user. Further, the calculation device  102  only transmits a result of a cryptographic operation to the authentication device  103 , and the authentication device  103  only generates a result of an operation of a vector A and a vector B by description, so the authentication device  103 , too, never knows the vectors that represent the biometric information of the user. 
         [0058]    Thus, unless the calculation device  102  and the authentication device  103  collude with each other, neither the vector A nor the vector B is generated, and a personal authentication service is provided in a state in which the biometric information of the user remains protected. 
         [0059]    However, in the biometric system in  FIG. 1 , it is possible for a malicious user to spoof a normal user by performing a replay attack. The replay attack is one of the typical spoofing attacks in an authentication system; in concrete terms, an attacker illegally obtains cryptographic information on an encrypted polynomial that is to be transmitted by a normal user by eavesdropping on the communication path between the terminal  101  and the calculation device  102 . The attacker retransmits the obtained cryptographic information to the cryptographic processing device  102  spoofing the normal user, which permits a successful authentication to be performed by the authentication device  103 . 
         [0060]    The above-mentioned problem may occur not only in a personal authentication system based on an encrypted secured distance but also in the other authentication systems based on a cryptographic operation by use of encrypted polynomials. 
         [0061]    The challenge-response authentication scheme is effective against such a replay attack. In this authentication scheme, a device which performs authentication generates a random number that is called a “challenge”, and transmits it to a terminal. The terminal generates data that is called a “response” on the basis of the received challenge and information to be authenticated, and replies to the device which performs authentication. Then, the device which performs authentication performs authentication processing by use of the challenge and the received response. According to the challenge-response authentication scheme, authentication will not be successfully performed even if a response is obtained by eavesdropping and is retransmitted because the response changes every time the challenge is generated. 
         [0062]    Thus, an introduction of a mechanism that uses a challenge-response authentication is considered as protection against replay attacks in the biometric system in  FIG. 1 . 
         [0063]    The characteristics of a cryptographic operation using a homomorphic encryption will be described before a biometric system according to embodiments is described. 
         [0064]    As described in Formulas (31) and (32), in a cryptographic operation using a homomorphic encryption, addition and multiplication for two polynomials f(x) and g(x) have the characteristics described in the following formulas: 
         [0000]        E ( f ( x ))+ E ( g ( x ))= E ( f ( x )+ g ( x ))   (51)
 
         [0000]        E ( f ( x ))* E ( g ( x ))= E ( f ( x )* g ( x ))   (52)
 
         [0065]    Further, when using the practical constructing method disclosed in Non Patent Document 2, the characteristics of these addition and multiplication can be rewritten into the following formulas: 
         [0000]        f ( x )+ E ( g ( x ))= E ( f ( x )+ g ( x ))   (53)
 
         [0000]        f ( x )* E ( g ( x ))= E ( f ( x )* g ( x ))   (54)
 
         [0066]    Formula (53) or Formula (54) indicate that even if an f(x) that has not been encrypted is added to or multiplied by E(g(x)), it is possible to obtain a decryption result that is identical with E(f(x)+g(x)) or E(f(x)*g(x)) when decrypting an operation result obtained by the addition or the multiplication. Such a cryptographic operation makes processing more efficient because the processing of encrypting f(x) can be omitted. Therefore, the characteristics of Formula (53) and Formula (54) maybe used in the following cryptographic operation. 
         [0067]      FIG. 2  is a block diagram of a biometric system according to an embodiment. 
         [0068]    A biometric system  200  includes a terminal  201 , a calculation device  301 , and an authentication device  401 . The terminal  201 , the calculation device  301 , and the authentication device  401  are connected to one another via a communication network, and can communicate with one another. 
         [0069]    The terminal  201  is, for example, a device of a user such as a client terminal, and the calculation device  301  and the authentication device  401  are, for example, a server. The terminal  201  and the authentication device  401  have a public key of a homomorphic encryption and the authentication device  401  has a secret key of a homomorphic encryption that corresponds to the public key. Further, the terminal  201  and the authentication device  401  have a key-generating parameter t used when the public key is generated. The authentication device  401  is an example of a cryptographic processing device. 
         [0070]    When registering biometric information, the terminal  201  obtains biometric information on a registrant using a sensor, and transforms the feature information extracted from the biometric information into a vector A as described in Formula (41). Next, the terminal  201  generates a vector A′ obtained by adding zero to the vector A as a last component (element). The vector A′ may be represented as a vector (A| | 0 ). The vector A′ is obtained by use of Formula (61) below: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           A 
                           ′ 
                         
                         = 
                           
                          
                         
                           ( 
                           
                             
                               A 
                                
                               
                                  
                                 0 
                                 ) 
                               
                             
                             = 
                             
                               ( 
                               
                                 
                                   a 
                                   0 
                                 
                                 , 
                                 
                                   a 
                                   1 
                                 
                                 , 
                                 … 
                                  
                                 
                                     
                                 
                                 , 
                                 
                                   a 
                                   
                                     n 
                                     - 
                                     1 
                                   
                                 
                                 , 
                                 0 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           = 
                             
                            
                           
                             ( 
                             
                               
                                 a 
                                 0 
                               
                               , 
                               
                                 a 
                                 1 
                               
                               , 
                               … 
                                
                               
                                   
                               
                               , 
                               
                                 a 
                                 
                                   n 
                                   - 
                                   1 
                                 
                               
                               , 
                               
                                 a 
                                 n 
                               
                             
                             ) 
                           
                         
                         , 
                         
                           
                             wherein 
                              
                             
                                 
                             
                              
                             
                               a 
                               n 
                             
                           
                           = 
                           0 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   61 
                   ) 
                 
               
             
           
         
       
     
         [0071]    The terminal  201  transforms the vector A′ into a polynomial pm 1 (A′) as described in Formula (63) below, and encrypts the polynomial pm 1 (A′) using a homomorphic encryption so as to generate an encrypted polynomial E(pm 1 (A′)). Then, the terminal  201  transmits cryptographic information that represents the encrypted polynomial E(pm 1 (A′)) to the calculation device  301 . 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       A 
                       ′ 
                     
                     = 
                     
                       ( 
                       
                         
                           a 
                           0 
                         
                         , 
                         
                           a 
                           1 
                         
                         , 
                         
                           a 
                           2 
                         
                         , 
                         … 
                          
                         
                             
                         
                         , 
                         
                           a 
                           
                             n 
                             - 
                             1 
                           
                         
                         , 
                         
                           a 
                           n 
                         
                       
                       ) 
                     
                   
                   , 
                   
                     
                       wherein 
                        
                       
                           
                       
                        
                       
                         a 
                         n 
                       
                     
                     = 
                     
                       
                         0 
                          
                         
                           
 
                         
                         ⇒ 
                         
                           pm 
                            
                           
                               
                           
                            
                           1 
                            
                           
                             ( 
                             
                               A 
                               ′ 
                             
                             ) 
                           
                         
                       
                       = 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             0 
                           
                           n 
                         
                          
                         
                             
                         
                          
                         
                           
                             a 
                             i 
                           
                            
                           
                             x 
                             i 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   63 
                   ) 
                 
               
             
           
         
       
     
         [0072]    terminal  201  receives a challenge from the authentication device  401  and generates a random number r. The terminal  201  generates a response using the random number r and the challenge, and transmits the response to the calculation device  301 . 
         [0073]    The calculation device  301  includes a receiver  311 , a storage  321 , a calculator  331 , and a transmitter  341 . 
         [0074]    The receiver  311  receives cryptographic information from the terminal  201 . Further, the receiver  311  receives a response from the terminal  201 . 
         [0075]    The storage  321  is a storage device that stores a program or data used in the calculation device  301 . The storage  321  stores therein an encrypted polynomial. Specifically, the storage  321  stores therein, as registered cryptographic information  322 , the cryptographic information received from the terminal  201 , the cryptographic information representing the encrypted polynomial E(pm 1 (A′)). As cryptographic information that represents an encrypted polynomial, for example, a coefficient included in each term of the encrypted polynomial can be used. Further, the storage  321  stores therein the public key and the key-generating parameter t. 
         [0076]    The calculator  331  performs a cryptographic operation using the response and the registered cryptographic information that have been received from the terminal  201 . 
         [0077]    The transmitter  341  transmits, to the authentication device  401 , cryptographic information that represents a result of the cryptographic operation performed by the calculator  331  and cryptographic information that represents the random number r. 
         [0078]    The authentication device  401  includes a generator  411 , a transmitter  421 , a receiver  431 , a decryption unit  441 , an authentication processing unit  451 , and a storage  461 . 
         [0079]    The generator  411  generates a random number p and generates a challenge using the random number p. 
         [0080]    The transmitter  421  transmits the generated challenge to the terminal  201 . 
         [0081]    The receiver  431  receives the cryptographic information received from the calculation device  301 . 
         [0082]    The decryption unit  441  decrypts the received cryptographic information. 
         [0083]    The authentication processing unit  451  performs authentication processing on the basis of a decryption result. 
         [0084]    The storage  461  is a storage device that stores a program or data used in the authentication device  401 . The storage  461  stores therein the generated random number p, the public key, the secrete key, and the key-generating parameter t. 
         [0085]      FIG. 3  is a flowchart of a cryptographic process according to the embodiment. 
         [0086]    In Step  501 , the terminal  201  transmits an authentication request to the authentication device  401 . 
         [0087]    In Step  502 , the receiver  431  receives the authentication request. Then, the generator  411  generates a random number p. The random number p is an integer not less than zero, and is less than a key-generating parameter t. The generator  411  generates a vector P′ obtained by adding a random number r to a zero vector as a component. Specifically, the generator  411  determines the random number p as a last component, and generates the vector P′ in which n components except for the last component are zero. The vector P′ may be represented as a vector ( 0  . . .  0 | |p). The vector P′ is obtained by use of Formula (71) below: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           P 
                           ′ 
                         
                         = 
                           
                          
                         
                           ( 
                           
                             
                               0 
                                
                               
                                   
                               
                                
                               … 
                                
                               
                                   
                               
                                
                               0 
                                
                               
                                  
                                 p 
                                 ) 
                               
                             
                             = 
                             
                               ( 
                               
                                 0 
                                 , 
                                 0 
                                 , 
                                 … 
                                  
                                 
                                     
                                 
                                 , 
                                 0 
                                 , 
                                 p 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           = 
                             
                            
                           
                             ( 
                             
                               
                                 p 
                                 0 
                               
                               , 
                               
                                 p 
                                 1 
                               
                               , 
                               … 
                                
                               
                                   
                               
                               , 
                               
                                 p 
                                 
                                   n 
                                   - 
                                   1 
                                 
                               
                               , 
                               
                                 p 
                                 n 
                               
                             
                             ) 
                           
                         
                         , 
                         
                           
                             wherein 
                              
                             
                                 
                             
                              
                             
                               p 
                               0 
                             
                              
                             
                                 
                             
                              
                             to 
                              
                             
                               
                                   
                               
                                
                               
                                   
                               
                             
                              
                             
                               p 
                               
                                 n 
                                 - 
                                 1 
                               
                             
                           
                           = 
                           0 
                         
                         , 
                         
                           
                             p 
                             n 
                           
                           = 
                           p 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   71 
                   ) 
                 
               
             
           
         
       
     
         [0088]    In Step  503 , the generator  411  transforms the vector P′ into a polynomial pm 2 (P′) as described in Formula (72) using a descending-order polynomial transformation. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       P 
                       ′ 
                     
                     = 
                     
                       ( 
                       
                         
                           p 
                           0 
                         
                         , 
                         
                           p 
                           1 
                         
                         , 
                         
                           p 
                           2 
                         
                         , 
                         … 
                          
                         
                             
                         
                         , 
                         
                           p 
                           
                             n 
                             - 
                             1 
                           
                         
                         , 
                         
                           p 
                           n 
                         
                       
                       ) 
                     
                   
                   , 
                   
                     
                       wherein 
                        
                       
                           
                       
                        
                       
                         p 
                         0 
                       
                        
                       
                           
                       
                        
                       to 
                        
                       
                           
                       
                        
                       
                         p 
                         
                           n 
                           - 
                           1 
                         
                       
                     
                     = 
                     0 
                   
                   , 
                   
                     
                       p 
                       n 
                     
                     = 
                     
                       
                         p 
                          
                         
                           
 
                         
                          
                         
                             
                         
                         ⇒ 
                         
                           pm 
                            
                           
                               
                           
                            
                           2 
                            
                           
                             ( 
                             
                               P 
                               ′ 
                             
                             ) 
                           
                         
                       
                       = 
                       
                         - 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               0 
                             
                             n 
                           
                            
                           
                               
                           
                            
                           
                             
                               p 
                               i 
                             
                              
                             
                               x 
                               
                                 n 
                                 + 
                                 1 
                                 - 
                                 i 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   72 
                   ) 
                 
               
             
           
         
       
     
         [0089]    The generator  411  generates challenge cryptographic data chl=E(pm 2 (P′)) by encrypting the polynomial pm 2 (P′) using a homomorphic encryption. 
         [0090]    In Step  504 , the transmitter  421  transmits cryptographic information that represents the challenge cryptographic data chl to the terminal  201  as a challenge. 
         [0091]    In Step  505 , the terminal  201  receives the challenge cryptographic data chl from the authentication device  401 . Specifically, the terminal  201  receives cryptographic information that represents the challenge cryptographic data chl. The terminal  201  obtains biometric information on a target to be authenticated using a sensor and transforms the feature information extracted from the biometric information into a vector B as described in Formula (42). In the present embodiment, the vector A and the vector B are binary vectors. In other words, each of the elements a 0  to a n-1  of the vector A is 0 or 1, and each of the elements b 0  to b n-1  of the vector B is 0 or 1. 
         [0092]    In Step  506 , the terminal  201  generates a vector B′ obtained by adding zero to the vector B as a last component (element). The vector B′ maybe represented as a vector (B| | 0 ). The vector B′ is obtained by use of Formula (73) below: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           B 
                           ′ 
                         
                         = 
                           
                          
                         
                           ( 
                           
                             
                               B 
                                
                               
                                  
                                 0 
                                 ) 
                               
                             
                             = 
                             
                               ( 
                               
                                 
                                   b 
                                   0 
                                 
                                 , 
                                 
                                   b 
                                   1 
                                 
                                 , 
                                 … 
                                  
                                 
                                     
                                 
                                 , 
                                 
                                   b 
                                   
                                     n 
                                     - 
                                     1 
                                   
                                 
                                 , 
                                 0 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           = 
                             
                            
                           
                             ( 
                             
                               
                                 b 
                                 0 
                               
                               , 
                               
                                 b 
                                 1 
                               
                               , 
                               … 
                                
                               
                                   
                               
                               , 
                               
                                 b 
                                 
                                   n 
                                   - 
                                   1 
                                 
                               
                               , 
                               
                                 b 
                                 n 
                               
                             
                             ) 
                           
                         
                         , 
                         
                           
                             wherein 
                              
                             
                                 
                             
                              
                             
                               b 
                               n 
                             
                           
                           = 
                           0 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   73 
                   ) 
                 
               
             
           
         
       
     
         [0093]    The terminal  201  transforms the vector B′ into a polynomial pm 2 (B′) as described in Formula (74) below using a descending-order polynomial transformation. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       B 
                       ′ 
                     
                     = 
                     
                       ( 
                       
                         
                           b 
                           0 
                         
                         , 
                         
                           b 
                           1 
                         
                         , 
                         
                           b 
                           2 
                         
                         , 
                         … 
                          
                         
                             
                         
                         , 
                         
                           b 
                           
                             n 
                             - 
                             1 
                           
                         
                         , 
                         
                           b 
                           n 
                         
                       
                       ) 
                     
                   
                   , 
                   
                     
                       wherein 
                        
                       
                           
                       
                        
                       
                         b 
                         n 
                       
                     
                     = 
                     
                       
                         0 
                          
                         
                           
 
                         
                         ⇒ 
                         
                           pm 
                            
                           
                               
                           
                            
                           2 
                            
                           
                             ( 
                             
                               B 
                               ′ 
                             
                             ) 
                           
                         
                       
                       = 
                       
                         - 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               0 
                             
                             n 
                           
                            
                           
                               
                           
                            
                           
                             
                               b 
                               i 
                             
                              
                             
                               x 
                               
                                 n 
                                 + 
                                 1 
                                 - 
                                 i 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   74 
                   ) 
                 
               
             
           
         
       
     
         [0094]    In Step  507 , the terminal  201  generates a random number r. Then, the terminal  201  calculates an inverse r 1  of the random number r, in which t is a divisor. The random number r is an integer not less than zero, and is less than the key-generating parameter t. 
         [0095]    In Step  508 , the terminal  201  multiplies the challenge cryptographic data chl by the random number r, and adds the polynomial pm 2 (B′) to a multiplication result, so as to calculate response cryptographic data res. The response cryptographic data res that is an encrypted polynomial is obtained by use of Formula (75) below, using the characteristics of Formulas (53) and (54): 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         res 
                         = 
                           
                          
                         
                           
                             pm 
                              
                             
                                 
                             
                              
                             2 
                              
                             
                               ( 
                               
                                 B 
                                 ′ 
                               
                               ) 
                             
                           
                           + 
                           
                             
                               chl 
                               * 
                             
                              
                             r 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           pm 
                            
                           
                               
                           
                            
                           2 
                            
                           
                             
                               ( 
                               
                                 
                                   B 
                                    
                                   
                                      
                                     0 
                                     ) 
                                   
                                 
                                 + 
                                 
                                   E 
                                    
                                   
                                     ( 
                                     
                                       pm 
                                        
                                       
                                           
                                       
                                        
                                       2 
                                        
                                       
                                         ( 
                                         
                                           0 
                                            
                                           
                                               
                                           
                                            
                                           … 
                                            
                                           
                                               
                                           
                                            
                                           0 
                                         
                                          
                                       
                                        
                                       p 
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                             * 
                           
                            
                           r 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           pm 
                            
                           
                               
                           
                            
                           2 
                            
                           
                             ( 
                             
                               
                                 B 
                                  
                                 
                                    
                                   0 
                                   ) 
                                 
                               
                               + 
                               
                                 E 
                                  
                                 
                                   ( 
                                   
                                     pm 
                                      
                                     
                                         
                                     
                                      
                                     2 
                                      
                                     
                                       ( 
                                       
                                         0 
                                          
                                         
                                             
                                         
                                          
                                         … 
                                          
                                         
                                             
                                         
                                          
                                         0 
                                       
                                        
                                     
                                      
                                     rp 
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           E 
                           ( 
                           
                             pm 
                              
                             
                                 
                             
                              
                             2 
                              
                             
                               ( 
                               
                                 B 
                                  
                                 
                                    
                                   rp 
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   75 
                   ) 
                 
               
             
           
         
       
     
         [0096]    Here, the vector (B| |rp)=(b 0 ,b 1 , . . . ,b n-1 ,rp). 
         [0097]    Further, the terminal  201  generates an encrypted inverse E(r −1 ) by encrypting the inverse r −1  using a homomorphic encryption. 
         [0098]    In Step  509 , the terminal  201  transmits, to the calculation device  301 , as a response, pieces of cryptographic information that respectively represent the response cryptographic data res and the encrypted inverse E(r −1 ). It is difficult to calculate an encrypted random number E(r) from an encrypted inverse E(r 1 ), so even when an attacker eavesdrops on challenge cryptographic data chl and response cryptographic data res, it is possible to prevent an encrypted polynomial E(pm 2 (B| | 0 )) from being calculated from these pieces of information, which results in enhancing security. 
         [0099]    In Step  510 , the receiver  311  receives the response from the terminal  201 . The calculator  331  performs a cryptographic operation by use of the registered cryptographic information  322  (that is, the encrypted polynomial E(pm 1 (A′))) and the response cryptographic data res (that is, the encrypted polynomial E(pm 2 (B| |rp))) that are stored in the storage  321 , so as to generate a result of the cryptographic operation. 
         [0100]    Specifically, as a result of the cryptographic operation of E(pm 1 (A′)) and E(pm 2 (B| |rp)), the calculator calculates an encrypted Hamming distance E(D H ) between the vector A′ and the vector (B| |rp) using Formula (76) below: 
         [0000]        E ( D   H )= E ( pm 1( A ′))* C 1+ E ( pm 2( B| |rp ))* C 2−2* E ( pm 1( A ′))* E ( pm 2( B| |rp ))   (76)
 
         [0101]    In this case, a polynomial C 1  and a polynomial C 2  are obtained using the following formulas: 
         [0000]        C 1=2 −C 2   (77)
 
         [0000]      C2=Σ i=0   n   x   i    (78)
 
         [0102]    In Step  511 , the transmitter  341  transmits, to the authentication device  401 , pieces of cryptographic information that respectively represent the encrypted Hamming distance E(D H ) and the encrypted inverse E(r −1 ). The cryptographic information that represents the encrypted inverse E(r −1 ) is an example of cryptographic information that represents a random number r. 
         [0103]    In Step  512 , the receiver  431  receives the pieces of cryptographic information that respectively represent the encrypted Hamming distance E(D H ) and the encrypted inverse E(r −1 ). 
         [0104]    The decryption unit  441  decrypts the encrypted Hamming distance E(D H ) represented by the received cryptographic information, so as to generate a polynomial D H  that is a decryption result. This polynomial D H  is equivalent to a polynomial obtained by calculating Formula (79) below: 
         [0000]      pm1(A′)*C1+pm2(B| |rp)*C2−2*pm1(A′)*pm2(B| |rp)   (79)
 
         [0105]    Further, the decryption unit  441  calculates the inverse r −1  by decrypting the encrypted inverse represented by the received cryptographic information. 
         [0106]    In Step  513 , the authentication processing unit  451  calculates the random number r from the inverse r −1 . The authentication processing unit  451  multiplies the random number r by the random number p so as to obtain a multiplication result rp. The authentication processing unit  451  calculates, from a constant term included in the polynomial D H , a Hamming distance HD between the vector A′ and the vector (B| |rp) that is represented by Formula (80) below: 
         [0000]        HD=a   0   +a   1   + . . . +a   n-1   +a   n   +b   0   +b   1   + . . . +b   n-1   +b   n −2( a   0   b   0   +a   1   b   1   + . . . +a   n-1   b   n-1   +a   n   b   n ), wherein  a   n =0, b   n   =rp    (80)
 
         [0107]    The authentication processing unit  451  obtains an operation result by subtracting the multiplication result rp from the Hamming distance HD. The Hamming distance HD between the vector A′ and the vector (B| |rp) that is represented by Formula (80) above is equivalent to a value obtained by adding a Hamming distance HD AB  between the vector A and the vector B to the multiplication result rp. Thus, if the multiplication result rp is subtracted from the Hamming distance HD, the Hamming distance HD AB  between the vector A and the vector B is obtained as an operation result. 
         [0108]    The authentication processing unit  451  performs the authentication of the target to be authenticated on the basis of the operation result (the Hamming distance HD AB ), and outputs an authentication result. Specifically, the authentication processing unit  451  determines whether authentication has been successful by comparing the operation result (the Hamming distance HD AB ) to a threshold. In this case, it is determined that the authentication of the target to be authenticated has been successful when the operation result (the Hamming distance HD AB ) is less than the threshold, and it is determined that the authentication has been unsuccessful when the operation result (the Hamming distance HD AB ) is not less than the threshold. 
         [0109]    According to the biometric system of the present embodiment, authentication will not be successfully performed even if an attacker eavesdrops on response cryptographic data and retransmits it because the response cryptographic data changes every time the authentication device generates challenge cryptographic data. As a result, it is possible to prevent spoofing by a replay attack. 
         [0110]    Further, according to the biometric system of the present embodiment, even if an attacker is allowed to see data in the calculation device (for example, if the attacker is an administrator of the calculation device), it is still possible to prevent spoofing by a replay attack because the response cryptographic data is generated by use of a random number generated by the terminal and a random number generated by the authentication device. 
         [0111]    The configuration of the biometric system in  FIG. 2  is merely an example and some of the components may be omitted or changed according to the applications or the requirements of the calculation device  301  and the authentication device  401 . For example, in the biometric system in  FIG. 2 , a target to be authenticated may perform processing for authenticating biometric information using a different terminal than the terminal  201 . A plurality of users may perform processing for registering and authenticating biometric information, and a plurality of terminals  201  may be provided for the plurality of users. 
         [0112]    Further, the calculation device  301  and the authentication device  401  in  FIG. 2  are also applicable to an authentication system other than a biometric system that uses a result of an operation of a vector A and a vector B. For example, it is possible to perform a personal authentication by transforming information other than biometric information, such as image information and phonetic information, into vectors. 
         [0113]    The flowchart illustrated in  FIG. 3  is merely an example, and some of the processes may be omitted or changed according to the applications or the requirements of the calculation device  301 , the authentication device  401 , or the biometric system. For example, in the cryptographic process in  FIG. 3 , when a device that is located outside the authentication device  401  generates a random number, the process of generating a random number p in Step  502  can be omitted. Likewise, when a device that is located outside the terminal  201  generates a random number, the process of generating a random number r in Step  507  can be omitted. 
         [0114]    Formulas (1) to (80) are merely examples, and other formulations may be used. For example, instead of the ascending-order transformation in Formula (63) being used for the vector A′, the descending-order transformation in Formula (72) being used for the vector P′, and the descending-order transformation in Formula (74) being used for the vector B′, the ascending-order transformation may be used for the vector P′ and the vector B′, and the descending-order transformation for the vector A′. 
         [0115]    The vectors A′, B′, and P′ described above are merely examples, and zeros in the vectors A′ and B′ and the random number p in the vector P′ may be in any position if zeros added to the vectors A and B as a component and the random number p in the vector P′ are in the same position. For example, a vector obtained by adding zero to the vector A as a first component may be the vector A′, a vector in which the random number p is a first component and n components except for the first component are zero may be the vector P′, and a vector obtained by adding zero to the vector B as a first component may be the vector B′. 
         [0116]    In a cryptographic operation using a homomorphic encryption, addition and multiplication for two polynomials f(x) and g(x) may be performed on the basis of Formulas (51) and (52), instead of Formulas (53) and (54). 
         [0117]    The terminal  201  may transmits cryptographic information that represents an encrypted random number E(r) instead of cryptographic information that represents an encrypted inverse E(r −1 ). In this case, the transmitter  341  of the calculation device  301  transmits the cryptographic information that represents an encrypted random number E(r) instead of the cryptographic information that represents an encrypted inverse E(r −1 ). The decryption unit  441  of the authentication device  401  calculates a random number r by decrypting the received cryptographic information, and the authentication processing unit  451  uses the random number r obtained by the decryption unit  441 . 
         [0118]    The formulation such that a Hamming distance HD appears in a coefficient in a term other than a constant term included in the polynomial D H  in Formula (79) may be used. 
         [0119]    The terminal  201 , the calculation device  301 , and the authentication device  401  in  FIG. 2  can be implemented, for example, as a hardware circuit. In this case, each component in the calculation device  301  and the authentication device  401  maybe implemented as an individual circuit, or a plurality of components may be implemented as an integrated circuit. 
         [0120]      FIG. 4  is a block diagram of an information processing device (a computer). 
         [0121]    The terminal  201 , the calculation device  301 , and the authentication device  401  can also be realized by using an information processing device (a computer) as illustrated in  FIG. 4 . 
         [0122]    The information processing device in  FIG. 4  includes a central processing unit (CPU)  701 , a memory  702 , an input device  703 , an output device  704 , an auxiliary storage  705 , a medium driving device  706 , and a network connecting device  707 . These components are connected to one another via a bus  708 . 
         [0123]    The memory  702  is, for example, a semiconductor memory such as a read only memory (ROM), a random access memory (RAM), and a flash memory. The memory  702  stores therein a program and data used for processing performed by the terminal  201 , the calculation device  301 , or the authentication device  401 . The memory  702  can be used as the storage  321 ,  461 . 
         [0124]    When the information processing device is the terminal  201 , the CPU  701  performs the processing of the terminal  201  by, for example, executing the program by use of the memory  702 . 
         [0125]    When the information processing device is the calculation device  301 , the CPU  701  operates as the calculator  331  to perform a cryptographic process by, for example, executing the program by use of the memory  702 . 
         [0126]    When the information processing device is the authentication device  401 , the CPU  701  operates as the generator  411 , the decryption unit  441 , and the authentication processing unit  451  to perform a cryptographic process by, for example, executing the program by use of the memory  702 . 
         [0127]    The input device  703  is, for example, a keyboard or a pointing device, and is used for inputting instructions or information from a user or an operator. The output device  704  is, for example, a display, a printer, or a speaker, and is used for outputting inquiries to the user or the operator, or outputting a result of processing. The result of processing may be a result of the authentication processing performed by the authentication device  401 . 
         [0128]    The auxiliary storage  705  is, for example, a magnetic disk device, an optical disk device, a magneto-optical disk device, or a tape device. The auxiliary storage  705  may be a hard disk drive or a flash memory. The information processing device stores the program and the data in the auxiliary storage  705  so as to load them into the memory  702  and use them. The auxiliary storage  705  can be used as the storage  321 ,  461 . 
         [0129]    The medium driving device  706  drives a portable recording medium  709  so as to access the recorded content. The portable recording medium  709  is, for example, a memory device, a flexible disk, an optical disc, or a magneto-optical disk. The portable recording medium  709  may be, for example, a compact disk read only memory (CD-ROM), a digital versatile disk (DVD), or a universal serial bus (USB) memory. The user or the operator can store the program and the data in the portable recording medium  709  so as to load them into the memory  702  and use them. 
         [0130]    As described above, a computer-readable recording medium that stores therein a program and data is a physical (non-transitory) recording medium such as the memory  702 , the auxiliary storage  705 , and the portable storage medium  709 . 
         [0131]    The network connecting device  707  is a communication interface that is connected to a communication network such as a local area network (LAN) or the Internet and makes a data conversion associated with communication. The information processing device can receive the program and the data from an external device via the network connecting device  707  so as to load them into the memory  702  and use them. The network connecting device  707  can be used as the receiver  311 ,  431 , or the transmitter  341 ,  421 . 
         [0132]    The information processing device does not necessarily include all the components in  FIG. 4 , and some of the components can be omitted according to the applications or the requirements. For example, when the instructions or the information from the user or the operator are not to be input, the input device  703  may be omitted, and when the inquiries to the user or the operator or the result of processing is not to be output, the output device  704  may be omitted. When the information processing device does not access the portable recording medium  709 , the medium driving device  706  may be omitted. 
         [0133]    All examples and conditional language provided herein are intended for pedagogical purposes to aiding the reader in understanding the invention and the concepts contributed by the inventor to further the art, and are not to be construed as being limitations to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although one or more embodiments of the present invention have been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.