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 shared key exchange over an open communication channel between a first party Party A and a second party Party B, comprising:
 (1) openly selecting, by the Party A and the 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)]; [−(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 in T 2  and computing the a residue modular q first (into the range of [−(q−1)/4, (q−1)/4]) then the a residue modular t, which gives a the 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 a 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 a 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 a 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 non-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)], [−(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 has 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 matrix:
   E i =A i S+te i , 
 
 
       where e i   E i  is a matrix selected following error distribution κ n     2    and this is kept private for each user; 
       obtaining a secret key shared key between the User i and the User j comprising:
 computing by a process processor 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 =AiStA j   t A i S t A j   t +te j   t =A i SA j   t +te i A j   t =K i ;
 
 
 
       then the two users deriving a the shared key between the two users using the following a simple rounding method, comprising:
 when the User j wants to establish a the shared key with the user User i, collecting by the user User j all the entries (including their positions in the matrix) in K j , including their positions 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 User i, a list of the positions of the entries in the matrix K j  (only the position not the values of the entries themselves) that are randomly selected from the collection collected entries, which is tagged by 0 1, and a list of entries not in the list tagged by 0; 
 then selecting by the user User i the same entries in its own matrix E i ×A j , which gives them User i and User j a shared list of common entry positions, therefore the corresponding entries of the matrix shared key; 
 then computing by each of the users the a residue of the entries modular t lagged by 1 and compute the a residue of the a sum of each of the entries tagged by 0 with (q−1)/2, which build a new identical ordered list of values, their the 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, and κ n     2    is the a distribution that each component are independent and each component follow certain error distribution like the a 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 a 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 User i and User j and are 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 a 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 non-zero. 
     
     
       13. Method, for a central server, 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)], [−(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 a 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 a master public key; 
 (4) assigning, by the central server, for each user indexed by i an and 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 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 public ID, A i , and the master public key, a new public key for the user with public 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 new public key to encrypt any message use the a matrix learning with errors (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, and κ n     2    is the a distribution that each component are independent and each component follow certain error distribution like the a 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 a 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 identity-based encryption (IBE) system. 
     
     
       18. The method according to  claim 13 , wherein the procedure method is extended further to build a hierarchical IBE system, where each user servers serves as a lower level central server. 
     
     
       19. The method according to  claim 13 , wherein the matrices are replaced with elements of the a 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 non-zero.