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 for establishing a shared key between two parties, Party A and Party B, over an open communication channel, comprising:
 selecting, by Party A and Party B, a matrix row size r, a matrix column size c and a finite field F comprising a first prime number q of elements, wherein the first prime number q comprises a value approximately equal to a polynomial of the matrix row size or column size;   selecting, by Party A and Party B, an error distribution K over the finite field F;   generating, by Party A and Party B, a public matrix M comprising values of random elements of the finite field F in accordance with a uniform distribution, wherein a size of the public matrix M comprises the matrix row size r rows by the matrix column size c columns;   selecting, by Party A and Party B, a whole number t, wherein the whole number t is less than the matrix row size r or matrix column size c;   generating, at Party A, entries of a private matrix S comprising values of elements in the finite field F chosen according to the selected error distribution K, wherein a size of the private matrix S comprises the matrix column size c rows by a selected number Sc columns;   selecting, at Party A, entries of an 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 error matrix e comprises the matrix row size r rows by the selected number Sc columns;   determining, at Party A, a product matrix resulting from multiplying the public matrix M times the private matrix;   determining, at Party A, a scalar error matrix resulting from multiplying the whole number t times the error matrix e;   determining, at Party A, a first exchange matrix Ma resulting from adding the scalar error matrix to the product matrix;   sending the first exchange matrix Ma to Party B in exchange for a second exchange matrix Mb;   determining, at Party A, a key matrix Ka resulting from multiplying a transpose of the private matrix S times the second exchange matrix Mb; and   applying, at Party A, a rounding method to each entry of the key matrix Ka to generate the shared key.   
     
     
       21. The method of claim 20, wherein the error matrix e comprises values of elements in the finite field F chosen according to a second error distribution that is not the selected error distribution K. 
     
     
       22. The method of claim 20, wherein the rounding method comprises:
 determining an interval matrix according to values of the entries of the key matrix Ka by:   determining a plurality of numbered intervals of elements of the finite field F;   determining, for each entry of the key matrix Ka, 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 Ka, each respective determined numbered interval to an entry of the interval matrix corresponding to the entry of the key matrix Ka; and   sending, to the networked computer, the interval matrix; and   applying each entry in the interval matrix to round each corresponding entry of the key matrix Ka to generate the shared key.   
     
     
       23. 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; and   applying each entry in the interval matrix to round each corresponding entry of the key matrix Ka to generate the shared key.   
     
     
       24. The method of claim 20, wherein the rounding method comprises, at Party A:
 determining an interval matrix according to values of the entries of the key matrix Ka by:   determining a plurality of numbered intervals of elements of the finite field F;   determining, for each entry of the key matrix Ka, a numbered interval of the plurality of numbered intervals the value of the entry of the key matrix Ka belongs to; and   assigning, for each entry of the key matrix Ka, each respective determined numbered interval to an entry of the interval matrix corresponding to the entry of the key matrix Ka; and   for the entry of the key matrix Ka, 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 Ka, 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 Ka, 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.   
     
     
       25. The method of claim 24, wherein each numbered interval assigned to the interval matrix comprises a value of zero or one. 
     
     
       26. The method of claim 24, wherein the first numbered interval comprises an interval of approximately half of the elements of the finite field F. 
     
     
       27. The method of claim 24, 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]. 
     
     
       28. The method of claim 24, wherein the fixed value V comprises (the first prime number q−1)/2. 
     
     
       29. 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 Ka, 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 Ka, 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 Ka, 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.   
     
     
       30. The method of claim 29, wherein each numbered interval assigned to the interval matrix comprises a value of zero or one. 
     
     
       31. The method of claim 29, wherein the first numbered interval comprises an interval of approximately half of the elements of the finite field F. 
     
     
       32. The method of claim 29, 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]. 
     
     
       33. The method of claim 29, wherein the fixed value V comprises (the first prime number q−1)/2. 
     
     
       34. The method of claim 20, wherein the first prime number q comprises a value approximately equal to a cube of the matrix row size r or the matrix column size c. 
     
     
       35. The method of claim 20, wherein the error distribution K comprises a discrete normal distribution over the finite field F having a standard deviation approximately equal to a square root of the matrix row size r or the matrix column size c. 
     
     
       36. The method of claim 20, wherein the error distribution K comprises a Gaussian distribution. 
     
     
       37. The method of claim 20, wherein the finite field F comprises elements with values comprising [−(the first prime number q−1)/2, (the first prime number q−1)2]. 
     
     
       38. The method of claim 20, wherein the matrix row sizer equals the matrix column size c. 
     
     
       39. The method of claim 38, wherein each matrix comprises an element of a ring of the form R q =F q [x]/f(x), wherein f(x)=x r +1. 
     
     
       40. The method of claim 39, 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. 
     
     
       41. The method of claim 20, wherein the first prime number q is a polynomial function of degree two or higher of the matrix row size r or the matrix column size c, 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 row sizer or the matrix column size c.   
     
     
       42. A method for establishing a shared key between two parties, Party A and Party B, over an open communication channel, comprising:
 selecting, by Party A and Party B, a matrix row size r, a matrix column size c and a finite field F comprising a first prime number q of elements, wherein the first prime number q comprises a value approximately equal to a polynomial of the matrix row size or column size:   selecting, by Party A and Party B, an error distribution K over the finite field F;   generating, by Party A and Party B, a public matrix M comprising values of random elements of the finite field F in accordance with a uniform distribution, wherein a size of the public matrix M comprises the matrix row size r rows by the matrix column size c columns;   selecting, by Party A and Party B, a whole number t, wherein the whole number t is less than the matrix row size r or matrix column size c;   generating, at Party A, entries of a private matrix S comprising values of elements chosen according to the selected error distribution K, wherein a size of the private matrix S comprises the matrix row size r rows by a selected number Sc columns;   selecting, at Party A, entries of an error matrix e comprising values of elements chosen according to the selected error distribution K, wherein a size of the error matrix e comprises the matrix column size c rows by the selected number Sc columns;   determining, at Party A, a product matrix resulting from multiplying a transpose of the public matrix M times the private matrix S;   determining, at Party A, a scalar error matrix resulting from multiplying the whole number t times the error matrix e;   determining, at Party A, a first exchange matrix Ma resulting from adding the scalar error matrix to the product matrix;   sending the first exchange matrix Ma to Party B, in exchange for a second exchange matrix Mb;   determining, at Party A, a key matrix Ka resulting from multiplying the second exchange matrix Mb times the private matrix S;   applying, at Party A, a rounding method to each entry of the key matrix Ka to generate the shared key.   
     
     
       43. The method of claim 42, wherein the error matrix e comprises values of elements in the finite field F chosen according to a second error distribution that is not the selected error distribution K. 
     
     
       44. The method of claim 42, wherein the rounding method comprises:
 determining an interval matrix according to values of the entries of the key matrix Ka by:   determining a plurality of numbered intervals of elements of the finite field F;   determining, for each entry of the key matrix Ka, 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 Ka, each respective determined numbered interval to an entry of the interval matrix corresponding to the entry of the key matrix Ka; and   sending, to the networked computer, the interval matrix; and   applying each entry in the interval matrix to round each corresponding entry of the key matrix Ka to generate the shared key.   
     
     
       45. The method of claim 42, 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; and   applying each entry in the interval matrix to round each corresponding entry of the key matrix Ka to generate the shared key.   
     
     
       46. The method of claim 42, wherein the rounding method comprises, at Party A:
 determining an interval matrix according to values of the entries of the key matrix Ka by:   determining a plurality of numbered intervals of elements of the finite field F;   determining, for each entry of the key matrix Ka, a numbered interval of the plurality of numbered intervals the value of the entry of the key matrix Ka belongs to; and   assigning, for each entry of the key matrix Ka, each respective determined numbered interval to an entry of the interval matrix corresponding to the entry of the key matrix Ka; and   for the entry of the key matrix Ka, 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 Ka, 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 Ka, 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.   
     
     
       47. The method of claim 46, wherein each numbered interval assigned to the interval matrix comprises a value of zero or one. 
     
     
       48. The method of claim 46, wherein the first numbered interval comprises an interval of approximately half of the elements of the finite field F. 
     
     
       49. The method of claim 46, 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]. 
     
     
       50. The method of claim 46, wherein the fixed value V comprises (the first prime number q−1)/2. 
     
     
       51. The method of claim 42, wherein the rounding method comprises, at Party A:
 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 Ka, 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 Ka, 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 Ka, 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.   
     
     
       52. The method of claim 51, wherein each numbered interval assigned to the interval matrix comprises a value of zero or one. 
     
     
       53. The method of claim 51, wherein the first numbered interval comprises an interval of approximately half of the elements of the finite field F. 
     
     
       54. The method of claim 51, 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]. 
     
     
       55. The method of claim 51, wherein the fixed value V comprises (the first prime number q−1)/2. 
     
     
       56. The method of claim 42, wherein the first prime number q comprises a value approximately equal to a cube of the matrix row size r or the matrix column size c. 
     
     
       57. The method of claim 42, wherein the error distribution K comprises a discrete normal distribution over the finite field F having a standard deviation approximately equal to a square root of the matrix row size r or the matrix column size c. 
     
     
       58. The method of claim 42, wherein the error distribution K comprises a Gaussian distribution. 
     
     
       59. The method of claim 42, wherein the finite field F comprises elements with values comprising [−(the first prime number q−1)/2, (the first prime number q−1)/2]. 
     
     
       60. The method of claim 42, wherein the matrix row sizer equals the matrix column size c. 
     
     
       61. The method of claim 60, wherein each matrix comprises an element of a ring of the form R q =F q [x]/f(x), wherein f(x)=x r +1. 
     
     
       62. The method of claim 61, 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. 
     
     
       63. The method of claim 42, wherein the first prime number q is a polynomial function of degree two or higher of the matrix row size r or the matrix column size c, 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 row sizer or the matrix column size c.   
     
     
       64. A key distribution system for generating a shared key between users, comprising:
 a central server in open 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;   generate a master key matrix S comprising values of random elements of the finite field F in accordance with a uniform distribution, wherein the master key matrix S is selected to be a symmetric 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;   generate a respective ID matrix for each of a plurality of users, wherein each respective ID matrix comprises values of elements in the finite field F chosen according to the selected error distribution K, wherein a size of the ID matrix comprises the matrix size n rows by the matrix size n columns;   generate a respective error matrix e for each of the plurality of users, wherein each respective error matrix e comprises values of elements in the finite field F chosen according to the selected error distribution K, wherein a size of the respective error matrix e comprises the matrix size n rows by the matrix size n columns;   determine a respective product matrix for each of the plurality of users resulting from multiplying the respective ID matrix by the master key matrix S;   determine a respective scalar error matrix for each of the plurality of users resulting from multiplying the whole number t times the respective error matrix e;   determine a respective exchange matrix E for each of the plurality of users resulting from adding the respective scalar error matrix to the respective product matrix;   send to each of the plurality of users the respective exchange matrix E, such that a User A and a User B of the plurality of users each generate the shared key based on the respective exchange matrices for each user.   
     
     
       65. The system of claim 64, 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. 
     
     
       66. The system of claim 65, 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. 
     
     
       67. The system of claim 64, 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. 
     
     
       68. The system of claim 64, wherein the error matrix e comprises values of elements in the finite field F chosen according to a second error distribution that is not the selected error distribution K. 
     
     
       69. The system of claim 64, wherein the first prime number q comprises a value approximately equal to a cube of the matrix size n. 
     
     
       70. The system of claim 64, wherein the error distribution K comprises a discrete normal distribution over the finite field F having a standard deviation approximately equal to a square root of the matrix size n. 
     
     
       71. The system of claim 64, wherein the error distribution K comprises a Gaussian distribution. 
     
     
       72. The system of claim 64, wherein the finite field F comprises elements with values comprising [−(the first prime number q−1)/2, (the first prime number q−1)/2].