Cryptographic system using pairing with errors

Abstract

Using the same mathematical principle of paring with errors, which can be viewed as an extension of the idea of the LWE problem, this invention gives constructions of a new key exchanges system, a new key distribution system and a new identity-based encryption system. These new systems are efficient and have very strong security property including provable security and resistance to quantum computer attacks.

The invention claimed is: 
     
       1. Method for establishing a key exchange over an open channel between a first party A and a second party B, comprising:
 (1) openly selecting, by Party A and Party B together, parameters, n, q and small whole number t, (t<<n), where q is an odd prime, and an error distribution κ n     2    to be a distribution over n×n matrix over F q , a n×n matrix M over F q  uniformly and randomly, where q is of size of a polynomial of n like n 3 , and elements of F q  are represented by integers in the range [−(q−1)/2, (q−1)/2)];   (2) choosing, by each of the parties privately, its own secret matrix S i  (i=A, B) a n×n matrix chosen according to the error distribution κ n     2   , and error matrix e i , (i=A, B) as a n×n matrix following the error distribution κ n     2   ;
 computing by a processor of the Party A
   M A =MS A +te A , 
 
 where t is a small integer (t<<n); 
 computing by the Party B
   M B =M t S B +te B , 
 
   (3) Both of the parties exchange M i  in the open communication channel;   (4) computing by the Party A:
   K A =S t   A ×M B =S t   A M t S B +tS t   A e B ;
 
 computing by the Party B:
   K B =M t   A ×S B =S t   A M t S B +te t   A S B ;
 
 
   (5) performing by both the Party A and the Party B a rounding technique to derive the shared key, comprising:
 (a) making by the Party B a list T 1  of all positions of the entries of K B  such that these entries are in the range of [−(q−1)/4, (q−1)/4] and a list T 2  of all positions which are not in the range of [−(q−1)/4, (q−1)/4], then sending by the Party B to the Party A the list T 1 , 
 (b) computing by each of the parties privately the residues of these entries modular t in T 1 , and for the entries not in T 1 , which is in T 2 , adding (q−1)/2 to each entry and computing the residue modular q first (into the range of [−(q−1)/4, (q−1)/4]) then the residue modular t, which gives a shared key between the two parties. 
   
     
     
       2. The method according to  claim 1 , wherein q is a polynomial function of degree 2 or higher, or a similar function, and κ n     2    is the a distribution that each component are independent and each component follow certain error distribution like the discrete error distribution κ σ , namely a discrete normal distribution over F q  center around 0 with standard deviation approximately √{square root over (n)}, or a similar distribution. 
     
     
       3. The method according to  claim 1 , wherein the matrices is rectangular as long as the matrix multiplication is compatible and the parameters are adjusted accordingly. 
     
     
       4. The method according to  claim 1 , wherein the matrices are replaced with elements of the ring R q =F q [x]/f(x) with f(x)=x n +1 and the parameters is adjusted accordingly. 
     
     
       5. The method according to  claim 1 , wherein the rounding technique is replaced with a similar technique. 
     
     
       6. The method according to  claim 1 , wherein the matrices are replaced with elements of the ring R q =F q [x]/f(x) with f(x)=x n +1, the parameters is adjusted accordingly, and the polynomial elements used are selected in the form of f(x)=Πf i (x)+g(x), where each f i , g(x) is a sparse matrix with very few terms terms none-zero. 
     
     
       7. Method, for a central server, building a key distribution (KD) system, comprising:
 (1) selecting, by the central server, parameters select parameters, n, q and small whole number t, (t<<n), where q is an odd prime, q is of size of a polynomial of n like n 3  and elements of F q  are represented by integers in the range [−(q−1)/2, (q−1)/2)], an error distribution κ n     2    a distribution over n×n matrix over F q ; and selecting by the central server a symmetric randomly chosen n×n matrix S over F q  as a master key;   (2) giving, by the central server, to each user index as i, a general matrix A i  as an ID with small entries following error distribution κ n     2   , where the ID matrix of each user is public and the central server have also a choice to generate the ID with information that can identify the user;   (3) distributing, by the central server, for each user securely a secret:
   E i =A i S+te i , 
 where e i  is a matrix selected following error distribution κ n     2    and this is kept private for each user; 
   obtaining a secret key shared between the User i and the User j comprising:   computing by a process of the User i:
   K i =E i ×A j   t =A i SA j   t +te i A j   t ;
 
   and computing by a processor of the User j
   K j =A i ×(E j ) t =A i S t A j   t +tA i e j   t =A i SA j   t +tA i e j   t ;
 
   then the two users deriving a shared key between the two users using the following simple rounding method, comprising:
 when the User j wants to establish a shared key with the user i, collecting by the user j all the entries (including their positions in the matrix) in K j  that are in the range of (−(q−1)/4, (q−1)/4), namely those entries which are closer to 0 than (q−1)/2; sending by the User j to the user i a list of the positions of the entries in the matrix (only the position not the values of the entries themselves) that are randomly selected from the collection, which is tagged by 0, and a list of entries not in the list tagged by 0; then selecting by the user i the same entries in its own matrix E i ×A j , which gives them a shared list of common entry positions, therefore the corresponding entries of the matrix; then computing by each of the users the residue of the entries modular t lagged by 1 and compute the residue of the sum of each of the entries tagged by 0 with (q−1)/2, which build a new identical ordered list of values, their shared secret key. 
   
     
     
       8. The method according to  claim 7 , wherein q is a polynomial function of degree 2 or higher, or a similar function, κ n     2    is the a distribution that each component are independent and each component follow certain error distribution like the discrete error distribution κ σ , namely a discrete normal distribution over F q  center around 0 with standard deviation approximately √{square root over (n)} or a similar distribution. 
     
     
       9. The method according to  claim 7 , wherein the matrices are replaced with elements of the ring R q =F q [x]/f(x) with f(x)=x n +1 and the parameters is adjusted accordingly. 
     
     
       10. The method according to  claim 7 , wherein the procedure for two users i and j to derive a shared key is modified such that the roles of i and j and exchanged. 
     
     
       11. The method according to  claim 7 , wherein several central servers to work together to build a distributed KD system. 
     
     
       12. The method according to  claim 7 , wherein the matrices are replaced with elements of the ring R q =F q [x]/f(x) with f(x)=x n +1, the parameters is adjusted accordingly, and the polynomial elements used are selected in the form of f(x)=Πf i (x)+g(x), where each f i , g(x) is a sparse matrix with very few terms terms none-zero. 
     
     
       13. Method, for a central, building an identity-based encryption system, comprising:
 (1) selecting by the central server parameters, n, q and small whole number t, (t<<n), where q is an odd prime, q is of size of a polynomial of n like n 3  and elements of F q  are represented by integers in the range [−(q−1)/2, (q−1)/2)], and an error distribution κ n     2    to be a distribution over n×n matrix over F q ; and selecting by the central server a secret n×n matrix S as the secret master key, where S is selected as a small element following certain error distribution κ n     2   ;   (2) selecting by the central server a random element M following uniform distribution, but making sure that M has an inverse: when the central server could not find one first time, it tries again till it finds one; then computing by the central server
   M 1 =MS+te, 
 where e is small following certain error distribution κ n     2   ; 
   (3) then publicizing by the central server M and M 1  as the master public key;   (4) assigning by the central server for each user indexed by i an public ID as A i , where A i  is small following certain error distribution κ n     2   , and the central server has can generate A i  from information that can identify the user i;   (5) processing by a processor and giving by the central server for each user, namely, the User i, a secret key:
   S i =SA i +tM −1 e i , 
 where e i 's entries are small following the error distribution κ; 
   (6) then establishing by anyone using the ID, A i , and the master public key, a new public key for the user with ID A i , which is given as the pair (A i , B i ), where
   A i =M 
   and 
   B i =M 1 A i =MSA i +teA i , 
 and using by anyone as the public key to encrypt any message use the MLWE encryption system. 
   
     
     
       14. The method according to  claim 13 , wherein q is a polynomial function of degree 2 or higher, or a similar function, κ n     2    is the a distribution that each component are independent and each component follow certain error distribution like the discrete error distribution κ σ , namely a discrete normal distribution over F q  center around 0 with standard deviation approximately √{square root over (n)} or a similar distribution. 
     
     
       15. The method according to  claim 7 , wherein the matrices is rectangular as long as the matrix multiplication is compatible and the parameters are adjusted accordingly. 
     
     
       16. The method according to  claim 13 , wherein the matrices are replaced with elements of the ring R q =F q [x]/f(x) with f(x)=x n +1 and the parameters is adjusted accordingly. 
     
     
       17. The method according to  claim 13 , wherein several central servers to work together to build a distributed IBE system. 
     
     
       18. The method according to  claim 13 , wherein the procedure is extended further to build a hierarchical IBE system, where each user servers as a lower level central server. 
     
     
       19. The method according to  claim 13 , wherein the matrices are replaced with elements of the ring R q =F q [x]/f(x) with f(x)=x n +1, the parameters is adjusted accordingly, and the polynomial elements used are selected in the form of f(x)=Πf i (x)+g(x), where each f i , g(x) is a sparse matrix with very few terms terms none-zero. 
     
     
       20. A method of deriving a shared key between a first networked computer and a second networked computer over an open communication channel, the method comprising:
 receiving, from a key distribution system, an exchange matrix Ei of a matrix size n rows by the matrix size n columns, wherein the key distribution system has selected:
 a finite field F comprising a first prime number q of elements, such that entries of Ei are in F; and 
 a whole number t, wherein the whole number t is less than the matrix size n; 
   determining a key matrix Ki resulting from multiplying the exchange matrix Ei and a transpose of a respective public ID matrix of the second networked computer; and   applying a rounding method to each entry of the key matrix Ki to generate the shared key.   
     
     
       21. The method of claim 20, wherein the rounding method comprises:
 determining an interval matrix according to values of the entries of the key matrix Ki by:
 determining a plurality of numbered intervals of elements of the finite field F; 
 determining, for each entry of the key matrix Ki, a numbered interval of the plurality of numbered intervals the value of the entry belongs to; and 
 assigning, for each entry of the key matrix Ki, each respective determined numbered interval to an entry of the interval matrix corresponding to the entry of the key matrix Ki; and 
   sending, to the another networked computer, the interval matrix; and   applying each entry in the interval matrix to round each corresponding entry of the key matrix Ki to generate the shared key.   
     
     
       22. The method of claim 20, wherein the rounding method comprises:
 determining a plurality of numbered intervals of elements of the finite field F;   receiving an interval matrix from the another networked computer; and   applying each entry in the interval matrix to round each corresponding entry of the key matrix Ki to generate the shared key.   
     
     
       23. The method of claim 20, wherein the rounding method comprises:
 determining an interval matrix according to values of the entries of the key matrix Ki by:
 determining a plurality of numbered intervals of elements of the finite field F; 
 determining, for each entry of the key matrix Ki, a numbered interval of the plurality of numbered intervals the value of the entry of the key matrix Ki belongs to; and 
 assigning, for each entry of the key matrix Ki, each respective determined numbered interval to an entry of the interval matrix corresponding to the entry of the key matrix Ki; and 
   for the entry of the key matrix Ki, if an interval value in the corresponding entry of the interval matrix does not correspond to a first numbered interval of the plurality of numbered intervals:
 adding, to the value of the entry in the key matrix Ki, a fixed value V of elements of a numbered interval, of the plurality of numbered intervals, corresponding to the interval value to form a sum; 
 determining a first residue of the sum modulo the first prime number q; and 
 determining a second residue of the first residue modulo the whole number t; 
   for the entry of the key matrix Ki, if the corresponding value in the interval matrix does correspond to the first number of the interval numbers:
 determining a second residue of the first residue modulo the whole number t. 
   
     
     
       24. The method of claim 23, wherein each numbered interval assigned to the interval matrix comprises a value of zero or one. 
     
     
       25. The method of claim 23, wherein the first numbered interval comprises an interval of approximately half of the elements of the finite field F. 
     
     
       26. The method of claim 23, wherein the first numbered interval comprises elements comprising values in the range [−(the first prime number q−1)/4, (the first prime number q−1)/4]. 
     
     
       27. The method of claim 23, wherein the fixed value V comprises (the first prime number q−1)/2. 
     
     
       28. The method of claim 20, wherein the rounding method comprises:
 determining a plurality of numbered intervals of elements of the finite field F;   receiving an interval matrix from the networked computer;   for the entry of the key matrix Ki, if an interval value in the corresponding entry of the interval matrix does not correspond to a first numbered interval of the plurality of numbered intervals:
 adding, to the value of the entry in the key matrix Ki, a fixed value V of elements of a numbered interval, of the plurality of numbered intervals, corresponding to the interval value to form a sum; 
 determining a first residue of the sum modulo the first prime number q; and 
 determining a second residue of the first residue modulo the whole number t; 
   for the entry of the key matrix Ki, if the corresponding value in the interval matrix does correspond to the first number of the interval numbers:
 determining a second residue of the first residue modulo the whole number t. 
   
     
     
       29. The method of claim 28, wherein each numbered interval assigned to the interval matrix comprises a value of zero or one. 
     
     
       30. The method of claim 28, wherein the first numbered interval comprises an interval of approximately half of the elements of the finite field F. 
     
     
       31. The method of claim 28, wherein the first numbered interval comprises elements comprising values in the range [−(the first prime number q−1)/4, (the first prime number q−1)/4]. 
     
     
       32. The method of claim 28, wherein the fixed value V comprises (the first prime number q−1)/2. 
     
     
       33. A method of deriving a shared key for a networked computer with another networked computer, the method comprising:
 receiving, from a key distribution system, an exchange matrix Ej of a matrix size n rows by the matrix size n columns, wherein the key distribution system has selected:
 a finite field F comprising a first prime number q of elements, such that entries of Ej are in F; and 
 a whole number t, wherein the whole number t is less than the matrix size n; 
   determining a key matrix Kj resulting from multiplying a public ID matrix of the another networked computer and a transpose of the exchange matrix Ej; and   applying a rounding method to each entry of the key matrix Kj to generate the shared key.   
     
     
       34. The method of claim 33, wherein the rounding method comprises:
 determining an interval matrix according to values of the entries of the key matrix Kj by:
 determining a plurality of numbered intervals of elements of the finite field F; 
 determining, for each entry of the key matrix Kj, a numbered interval of the plurality of numbered intervals the value of the entry belongs to; and 
 assigning, for each entry of the key matrix Kj, each respective determined numbered interval to an entry of the interval matrix corresponding to the entry of the key matrix Kj; and 
   sending, to the another networked computer, the interval matrix; and   applying each entry in the interval matrix to round each corresponding entry of the key matrix Kj to generate the shared key.   
     
     
       35. The method of claim 33, wherein the rounding method comprises:
 determining a plurality of numbered intervals of elements of the finite field F;   receiving an interval matrix from the another networked computer; and   applying each entry in the interval matrix to round each corresponding entry of the key matrix Kj to generate the shared key.   
     
     
       36. The method of claim 33, wherein the rounding method comprises:
 determining an interval matrix according to values of the entries of the key matrix Kj by:
 determining a plurality of numbered intervals of elements of the finite field F; 
 determining, for each entry of the key matrix Kj, a numbered interval of the plurality of numbered intervals the value of the entry of the key matrix Kj belongs to; and 
 assigning, for each entry of the key matrix Kj, each respective determined numbered interval to an entry of the interval matrix corresponding to the entry of the key matrix Kj; and 
   for the entry of the key matrix Kj, if an interval value in the corresponding entry of the interval matrix does not correspond to a first numbered interval of the plurality of numbered intervals:
 adding, to the value of the entry in the key matrix Kj, a fixed value V of elements of a numbered interval, of the plurality of numbered intervals, corresponding to the interval value to form a sum; 
 determining a first residue of the sum modulo the first prime number q; and 
 determining a second residue of the first residue modulo the whole number t; 
   for the entry of the key matrix Kj, if the corresponding value in the interval matrix does correspond to the first number of the interval numbers:
 determining a second residue of the first residue modulo the whole number t. 
   
     
     
       37. The method of claim 36, wherein each numbered interval assigned to the interval matrix comprises a value of zero or one. 
     
     
       38. The method of claim 36, wherein the first numbered interval comprises an interval of approximately half of the elements of the finite field F. 
     
     
       39. The method of claim 36, wherein the first numbered interval comprises elements comprising values in the range [−(the first prime number q−1)/4, (the first prime number q−1)/4]. 
     
     
       40. The method of claim 36, wherein the fixed value V comprises (the first prime number q−1)/2. 
     
     
       41. The method of claim 33, wherein the rounding method comprises:
 determining a plurality of numbered intervals of elements of the finite field F;   receiving an interval matrix from the networked computer;   for the entry of the key matrix Kj, if an interval value in the corresponding entry of the interval matrix does not correspond to a first numbered interval of the plurality of numbered intervals:
 adding, to the value of the entry in the key matrix Kj, a fixed value V of elements of a numbered interval, of the plurality of numbered intervals, corresponding to the interval value to form a sum; 
 determining a first residue of the sum modulo the first prime number q; and 
 determining a second residue of the first residue modulo the whole number t; 
   for the entry of the key matrix Kj, if the corresponding value in the interval matrix does correspond to the first number of the interval numbers:
 determining a second residue of the first residue modulo the whole number t. 
   
     
     
       42. The method of claim 41, wherein each numbered interval assigned to the interval matrix comprises a value of zero or one. 
     
     
       43. The method of claim 41, wherein the first numbered interval comprises an interval of approximately half of the elements of the finite field F. 
     
     
       44. The method of claim 41, wherein the first numbered interval comprises elements comprising values in the range [−(the first prime number q−1)/4, (the first prime number q−1)/4]. 
     
     
       45. The method of claim 41, wherein the fixed value V comprises (the first prime number q−1)/2. 
     
     
       46. An encryption key authority system comprising:
 a central server in communication with a plurality of users,   the central server comprising at least one processor; and a non-transitory computer-readable storage medium in operable communication with the processor, wherein the computer-readable storage medium comprising computer-executable instructions that, when executed, cause the at least one processor to:   select a matrix size n and a finite field F comprising a first prime number q of elements, and an error distribution K over the finite field F, wherein the first prime number q comprises a value approximately equal to a polynomial of the matrix size;   generating a master key matrix S comprising values of random elements of the finite field F chosen according to the selected error distribution K, wherein the master key matrix S is a matrix and wherein a size of the master key matrix S comprises the matrix size n rows by the matrix size n columns;   select a whole number t, wherein the whole number t is less than the matrix size n;   select a first random matrix M comprising values of random elements of the finite field F chosen according to a uniform distribution, wherein the first random matrix M is selected such that an inverse of the first random matrix M exists;   select a master error matrix e comprising values of elements in the finite field F chosen according to the selected error distribution K, wherein a size of the master error matrix e comprises the matrix size n rows by the matrix size n columns;   generate a product matrix resulting from multiplying the first random matrix M and the master key matrix S;   generate a scalar error matrix resulting from multiplying the whole number t and the master error matrix e;   generate a master public key pair comprising the first random matrix M and a second random matrix M1 resulting from adding the scalar error matrix to the respective product matrix;   generate a first respective ID matrix Ai for each of a plurality of users, wherein each first respective ID matrix Ai comprises values of elements in the finite field F chosen according to the selected error distribution K, wherein a size of the first respective ID matrix Ai comprises the matrix size n rows by the matrix size n columns;   determine a respective secret key matrix Si for each of the plurality of users based on the master public key pair and the first respective ID matrix Ai for each of the plurality of users; and   send, to each of the plurality of users, the respective secret key matrix Si.   
     
     
       47. The system of claim 46, wherein the at least one processor are distributed throughout a network. 
     
     
       48. The system of claim 46, wherein a user of the plurality of users acts as an encryption key authority for a hierarchical child key distribution system. 
     
     
       49. The system of claim 46, wherein each matrix comprises an element of a ring of the form R q =F q [x]/f(x), wherein f(x)=x n +1. 
     
     
       50. The system of claim 49, wherein polynomial elements are selected in the form of [IIf i (x)]+g(x), wherein g(x) and each f i (x) comprise a sparse polynomial with few non-zero terms. 
     
     
       51. The system of claim 46, wherein the first prime number q is a polynomial function of degree two or higher of the matrix size n, and wherein the error distribution K is a distribution such that each matrix entry is independent and each matrix entry follows a discrete normal distribution over the finite field F, centered around zero, with a standard deviation of approximately a square root of the matrix size n. 
     
     
       52. The system of claim 46, wherein the respective secret key matrix Si for each of the plurality of users is determined by:
 determining a respective product matrix resulting from multiplying the master key matrix S and the first respective ID matrix Ai;   selecting a respective error matrix ei comprising values of elements in the finite field F chosen according to the selected error distribution K, wherein a size of the respective error matrix ei comprises the matrix size n rows by the matrix size n columns;   determining a respective scalar matrix resulting from multiplying the whole number t and the inverse of the random matrix M times the respective error matrix ei; and   adding the respective scalar error matrix to the respective product matrix.   
     
     
       53. A method of a networked computer encrypting a message between a first networked computer and a second networked computer, the method comprising:
 determining, at the first networked computer, a public matrix pair comprising a first matrix M and a second matrix M1;   receiving, at the first networked computer, an ID matrix Ai of the second networked computer;   determining a key matrix pair for the second networked computer, wherein the key matrix pair comprises the first matrix M and a second public matrix Bi, wherein the second public matrix Bi comprises a matrix resulting from multiplying the second matrix M1 and the ID matrix Ai; and   applying the key matrix pair to encrypt the message to the second networked computer; and   sending the encrypted message to the second networked computer.