In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices.[1] Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example, cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign.

Ideal lattices also form the basis for quantum computer attack resistant cryptography based on the Ring Learning with Errors.[2] These cryptosystems are provably secure under the assumption that the shortest vector problem (SVP) is hard in these ideal lattices.

Introduction

edit

In general terms, ideal lattices are lattices corresponding to ideals in rings of the form   for some irreducible polynomial   of degree  .[1] All of the definitions of ideal lattices from prior work are instances of the following general notion: let   be a ring whose additive group is isomorphic to   (i.e., it is a free  -module of rank  ), and let   be an additive isomorphism mapping   to some lattice   in an  -dimensional real vector space (e.g.,  ). The family of ideal lattices for the ring   under the embedding   is the set of all lattices  , where   is an ideal in  [3]

Definition

edit

Notation

edit

Let   be a monic polynomial of degree  , and consider the quotient ring  .

Using the standard set of representatives  , and identification of polynomials with vectors, the quotient ring   is isomorphic (as an additive group) to the integer lattice  , and any ideal   defines a corresponding integer sublattice  .

An ideal lattice is an integer lattice   such that   for some monic polynomial   of degree   and ideal  .

edit

It turns out that the relevant properties of   for the resulting function to be collision resistant are:

  •   should be irreducible.
  • the ring norm   is not much bigger than   for any polynomial  , in a quantitative sense.

The first property implies that every ideal of the ring   defines a full-rank lattice in   and plays a fundamental role in proofs.

Lemma: Every ideal   of  , where   is a monic, irreducible integer polynomial of degree  , is isomorphic to a full-rank lattice in  .

Ding and Lindner[4] gave evidence that distinguishing ideal lattices from general ones can be done in polynomial time and showed that in practice randomly chosen lattices are never ideal. They only considered the case where the lattice has full rank, i.e. the basis consists of   linear independent vectors. This is not a fundamental restriction because Lyubashevsky and Micciancio have shown that if a lattice is ideal with respect to an irreducible monic polynomial, then it has full rank, as given in the above lemma.

Algorithm: Identifying ideal lattices with full rank bases

Data: A full-rank basis  
Result: true and  , if   spans an ideal lattice with respect to  , otherwise false.

  1. Transform   into HNF
  2. Calculate  ,  , and  
  3. Calculate the product  
  4. if only the last column of P is non-zero then
  5. set   to equal this column
  6. else return false
  7. if   for   then
  8. use CRT to find   and  
  9. else return false
  10. if   then
  11. return true,  
  12. else return false

where the matrix M is

 

Using this algorithm, it can be seen that many lattices are not ideal lattices. For example, let   and  , then

 

is ideal, but

 

is not.   with   is an example given by Lyubashevsky and Micciancio.[5]

Performing the algorithm on it and referring to the basis as B, matrix B is already in Hermite Normal Form so the first step is not needed. The determinant is  , the adjugate matrix

 
 

and finally, the product   is

 

At this point the algorithm stops, because all but the last column of   have to be zero if   would span an ideal lattice.

Use in cryptography

edit

Micciancio[6] introduced the class of structured cyclic lattices, which correspond to ideals in polynomial rings  , and presented the first provably secure one-way function based on the worst-case hardness of the restriction of Poly(n)-SVP to cyclic lattices. (The problem γ-SVP consists in computing a non-zero vector of a given lattice, whose norm is no more than γ times larger than the norm of a shortest non-zero lattice vector.) At the same time, thanks to its algebraic structure, this one-way function enjoys high efficiency comparable to the NTRU scheme   evaluation time and storage cost). Subsequently, Lyubashevsky and Micciancio[5] and independently Peikert and Rosen[7] showed how to modify Micciancio's function to construct an efficient and provably secure collision resistant hash function. For this, they introduced the more general class of ideal lattices, which correspond to ideals in polynomial rings  . The collision resistance relies on the hardness of the restriction of Poly(n)-SVP to ideal lattices (called Poly(n)-Ideal-SVP). The average-case collision-finding problem is a natural computational problem called Ideal-SIS, which has been shown to be as hard as the worst-case instances of Ideal-SVP. Provably secure efficient signature schemes from ideal lattices have also been proposed,[1][8] but constructing efficient provably secure public key encryption from ideal lattices was an interesting open problem.

The fundamental idea of using LWE and Ring LWE for key exchange was proposed and filed at the University of Cincinnati in 2011 by Jintai Ding and provided a state of the art description of a quantum resistant key exchange using Ring LWE. The paper[9] appeared in 2012 after a provisional patent application was filed in 2012. In 2014, Peikert[10] presented a key transport scheme following the same basic idea of Ding's, where the new idea of sending additional signal for rounding in Ding's construction is also utilized. A digital signature using the same concepts was done several years earlier by Vadim Lyubashevsky in, "Lattice Signatures Without Trapdoors."[11] Together, the work of Peikert and Lyubashevsky provide a suite of Ring-LWE based quantum attack resistant algorithms with the same security reductions.

Efficient collision resistant hash functions

edit

The main usefulness of the ideal lattices in cryptography stems from the fact that very efficient and practical collision resistant hash functions can be built based on the hardness of finding an approximate shortest vector in such lattices.[1] Independently constructed collision resistant hash functions by Peikert and Rosen,[7] as well as Lyubashevsky and Micciancio, based on ideal lattices (a generalization of cyclic lattices), and provided a fast and practical implementation.[3] These results paved the way for other efficient cryptographic constructions including identification schemes and signatures.

Lyubashevsky and Micciancio[5] gave constructions of efficient collision resistant hash functions that can be proven secure based on worst case hardness of the shortest vector problem for ideal lattices. They defined hash function families as: Given a ring  , where   is a monic, irreducible polynomial of degree   and   is an integer of order roughly  , generate   random elements  , where   is a constant. The ordered  -tuple   determines the hash function. It will map elements in  , where   is a strategically chosen subset of  , to  . For an element  , the hash is  . Here the size of the key (the hash function) is  , and the operation   can be done in time   by using the Fast Fourier Transform (FFT) [citation needed], for appropriate choice of the polynomial  . Since   is a constant, hashing requires time  . They proved that the hash function family is collision resistant by showing that if there is a polynomial-time algorithm that succeeds with non-negligible probability in finding   such that  , for a randomly chosen hash function  , then a certain problem called the “shortest vector problem” is solvable in polynomial time for every ideal of the ring  .

Based on the work of Lyubashevsky and Micciancio in 2006, Micciancio and Regev[12] defined the following algorithm of hash functions based on ideal lattices:

  • Parameters: Integers   with  , and vector f  .
  • Key:   vectors   chosen independently and uniformly at random in  .
  • Hash function:   given by  .

Here   are parameters, f is a vector in   and   is a block-matrix with structured blocks  .

Finding short vectors in   on the average (even with just inverse polynomial probability) is as hard as solving various lattice problems (such as approximate SVP and SIVP) in the worst case over ideal lattices, provided the vector f satisfies the following two properties:

  • For any two unit vectors u, v, the vector [F∗u]v has small (say, polynomial in  , typically   norm.
  • The polynomial   is irreducible over the integers, i.e., it does not factor into the product of integer polynomials of smaller degree.

The first property is satisfied by the vector   corresponding to circulant matrices, because all the coordinates of [F∗u]v are bounded by 1, and hence  . However, the polynomial   corresponding to   is not irreducible because it factors into  , and this is why collisions can be efficiently found. So,   is not a good choice to get collision resistant hash functions, but many other choices are possible. For example, some choices of f for which both properties are satisfied (and therefore, result in collision resistant hash functions with worst-case security guarantees) are

  •   where   is prime, and
  •   for   equal to a power of 2.

Digital signatures

edit

Digital signatures schemes are among the most important cryptographic primitives. They can be obtained by using the one-way functions based on the worst-case hardness of lattice problems. However, they are impractical. A number of new digital signature schemes based on learning with errors, ring learning with errors and trapdoor lattices have been developed since the learning with errors problem was applied in a cryptographic context.

Their direct construction of digital signatures based on the complexity of approximating the shortest vector in ideal (e.g., cyclic) lattices.[8] The scheme of Lyubashevsky and Micciancio[8] has worst-case security guarantees based on ideal lattices and it is the most asymptotically efficient construction known to date, yielding signature generation and verification algorithms that run in almost linear time.[12]

One of the main open problems that was raised by their work is constructing a one-time signature with similar efficiency, but based on a weaker hardness assumption. For instance, it would be great to provide a one-time signature with security based on the hardness of approximating the Shortest Vector Problem (SVP) (in ideal lattices) to within a factor of  .[8]

Their construction is based on a standard transformation from one-time signatures (i.e. signatures that allow to securely sign a single message) to general signature schemes, together with a novel construction of a lattice based one-time signature whose security is ultimately based on the worst-case hardness of approximating the shortest vector in all lattices corresponding to ideals in the ring   for any irreducible polynomial  .

Key-Generation Algorithm: Input:  , irreducible polynomial   of degree  .

  1. Set  ,  ,  
  2. For all positive  , let the sets   and   be defined as:
  such that  
  such that  
  1. Choose uniformly random  
  2. Pick a uniformly random string  
  3. If   then
  4. Set  
  5. else
  6. Set   to the position of the first 1 in the string  
  7. end if
  8. Pick   independently and uniformly at random from   and   respectively
  9. Signing Key:  . Verification Key:  

Signing Algorithm:

Input: Message   such that  ; signing key  

Output:  

Verification Algorithm:

Input: Message  ; signature  ; verification key  

Output: “ACCEPT”, if   and  

“REJECT”, otherwise.

The SWIFFT hash function

edit

The hash function is quite efficient and can be computed asymptotically in   time using the Fast Fourier Transform (FFT) over the complex numbers. However, in practice, this carries a substantial overhead. The SWIFFT family of hash functions defined by Micciancio and Regev[12] is essentially a highly optimized variant of the hash function above using the (FFT) in  . The vector f is set to   for   equal to a power of 2, so that the corresponding polynomial   is irreducible. Let   be a prime number such that   divides  , and let   be an invertible matrix over   to be chosen later. The SWIFFT hash function maps a key   consisting of   vectors chosen uniformly from   and an input   to   where   is as before and  . Multiplication by the invertible matrix   maps a uniformly chosen   to a uniformly chosen  . Moreover,   if and only if  . Together, these two facts establish that finding collisions in SWIFFT is equivalent to finding collisions in the underlying ideal lattice function  , and the claimed collision resistance property of SWIFFT is supported by the connection to worst case lattice problems on ideal lattices.

The algorithm of the SWIFFT hash function is:

  • Parameters: Integers   such that   is a power of 2,   is prime,   and  .
  • Key:   vectors   chosen independently and uniformly at random in  .
  • Input:   vectors  .
  • Output: the vector  , where   is the component-wise vector product.

Learning with errors (LWE)

edit

Learning with errors (LWE) problem has been shown to be as hard as worst-case lattice problems and has served as the foundation for many cryptographic applications. However, these applications are inefficient because of an inherent quadratic overhead in the use of LWE. To get truly efficient LWE applications, Lyubashevsky, Peikert and Regev[3] defined an appropriate version of the LWE problem in a wide class of rings and proved its hardness under worst-case assumptions on ideal lattices in these rings. They called their LWE version ring-LWE.

Let  , where the security parameter   is a power of 2, making   irreducible over the rationals. (This particular   comes from the family of cyclotomic polynomials, which play a special role in this work).

Let   be the ring of integer polynomials modulo  . Elements of   (i.e., residues modulo  ) are typically represented by integer polynomials of degree less than  . Let   be a sufficiently large public prime modulus (bounded by a polynomial in  ), and let   be the ring of integer polynomials modulo both   and  . Elements of   may be represented by polynomials of degree less than  -whose coefficients are from  .

In the above-described ring, the R-LWE problem may be described as follows. Let   be a uniformly random ring element, which is kept secret. Analogously to standard LWE, the goal of the attacker is to distinguish arbitrarily many (independent) ‘random noisy ring equations’ from truly uniform ones. More specifically, the noisy equations are of the form  , where a is uniformly random and the product   is perturbed by some ‘small’ random error term, chosen from a certain distribution over  .

They gave a quantum reduction from approximate SVP (in the worst case) on ideal lattices in   to the search version of ring-LWE, where the goal is to recover the secret   (with high probability, for any  ) from arbitrarily many noisy products. This result follows the general outline of Regev's iterative quantum reduction for general lattices,[13] but ideal lattices introduce several new technical roadblocks in both the ‘algebraic’ and ‘geometric’ components of the reduction. They[3] used algebraic number theory, in particular, the canonical embedding of a number field and the Chinese Remainder Theorem to overcome these obstacles. They got the following theorem:

Theorem Let   be an arbitrary number field of degree  . Let   be arbitrary, and let the (rational) integer modulus   be such that  . There is a probabilistic polynomial-time quantum reduction from  -  to  -  , where  .

In 2013, Guneysu, Lyubashevsky, and Poppleman proposed a digital signature scheme based on the Ring Learning with Errors problem.[14] In 2014, Peikert presented a Ring Learning with Errors Key Exchange (RLWE-KEX) in his paper, "Lattice Cryptography for the Internet."[10] This was further developed by the work of Singh.[15]

Ideal-LWE

edit

Stehle, Steinfeld, Tanaka and Xagawa[16] defined a structured variant of LWE problem (Ideal-LWE) to describe an efficient public key encryption scheme based on the worst case hardness of the approximate SVP in ideal lattices. This is the first CPA-secure public key encryption scheme whose security relies on the hardness of the worst-case instances of  -Ideal-SVP against subexponential quantum attacks. It achieves asymptotically optimal efficiency: the public/private key length is   bits and the amortized encryption/decryption cost is   bit operations per message bit (encrypting   bits at once, at a   cost). The security assumption here is that  -Ideal-SVP cannot be solved by any subexponential time quantum algorithm. It is noteworthy that this is stronger than standard public key cryptography security assumptions. On the other hand, contrary to the most of public key cryptography, lattice-based cryptography allows security against subexponential quantum attacks.

Most of the cryptosystems based on general lattices rely on the average-case hardness of the Learning with errors (LWE). Their scheme is based on a structured variant of LWE, that they call Ideal-LWE. They needed to introduce some techniques to circumvent two main difficulties that arise from the restriction to ideal lattices. Firstly, the previous cryptosystems based on unstructured lattices all make use of Regev's worst-case to average-case classical reduction from Bounded Distance Decoding problem (BDD) to LWE (this is the classical step in the quantum reduction from SVP to LWE). This reduction exploits the unstructured-ness of the considered lattices, and does not seem to carry over to the structured lattices involved in Ideal-LWE. In particular, the probabilistic independence of the rows of the LWE matrices allows to consider a single row. Secondly, the other ingredient used in previous cryptosystems, namely Regev's reduction from the computational variant of LWE to its decisional variant, also seems to fail for Ideal-LWE: it relies on the probabilistic independence of the columns of the LWE matrices.

To overcome these difficulties, they avoided the classical step of the reduction. Instead, they used the quantum step to construct a new quantum average-case reduction from SIS (average-case collision-finding problem) to LWE. It also works from Ideal-SIS to Ideal-LWE. Combined with the reduction from worst-case Ideal-SVP to average-case Ideal-SIS, they obtained the a quantum reduction from Ideal-SVP to Ideal-LWE. This shows the hardness of the computational variant of Ideal-LWE. Because they did not obtain the hardness of the decisional variant, they used a generic hardcore function to derive pseudorandom bits for encryption. This is why they needed to assume the exponential hardness of SVP.

Fully homomorphic encryption

edit

A fully homomorphic encryption (FHE) scheme is one which allows for computation over encrypted data, without first needing to decrypt. The problem of constructing a fully homomorphic encryption scheme was first put forward by Rivest, Adleman and Dertouzos[17] in 1978, shortly after the invention of RSA by Rivest, Adleman and Shamir.[18]

An encryption scheme   is homomorphic for circuits in   if, for any circuit  ,

given  ,  , and  ,

it holds that  .

  is fully homomorphic if it is homomorphic for all circuits of size   where   is the scheme's security parameter.

In 2009, Gentry[19] proposed the first solution to the problem of constructing a fully homomorphic encryption scheme. His scheme was based on ideal lattices.

See also

edit

References

edit
  1. ^ a b c d Lyubashevsky, Vadim (2008). "Lattice-Based Identification Schemes Secure Under Active Attacks" (PDF). Public Key Cryptography – PKC 2008. Lecture Notes in Computer Science. Vol. 4939. pp. 162–179. doi:10.1007/978-3-540-78440-1_10. ISBN 978-3-540-78439-5.
  2. ^ Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010). "On Ideal Lattices and Learning with Errors over Rings". In Gilbert, Henri (ed.). Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science. Vol. 6110. pp. 1–23. CiteSeerX 10.1.1.297.6108. doi:10.1007/978-3-642-13190-5_1. ISBN 978-3-642-13189-9.
  3. ^ a b c d Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010). "On Ideal Lattices and Learning with Errors over Rings". Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science. Vol. 6110. pp. 1–23. doi:10.1007/978-3-642-13190-5_1. ISBN 978-3-642-13189-9.
  4. ^ Jintai Ding and Richard Lindner. Identifying Ideal Lattices. In Cryptology ePrint Archive, Report 2007/322, 2007.
  5. ^ a b c Lyubashevsky, Vadim; Micciancio, Daniele (2006). "Generalized Compact Knapsacks Are Collision Resistant" (PDF). Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 4052. pp. 144–155. doi:10.1007/11787006_13. ISBN 978-3-540-35907-4.
  6. ^ Micciancio, Daniele (2007). "Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions". Computational Complexity. 16 (4): 365–411. doi:10.1007/s00037-007-0234-9.
  7. ^ a b Peikert, Chris; Rosen, Alon (2006). "Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices" (PDF). Theory of Cryptography. Lecture Notes in Computer Science. Vol. 3876. pp. 145–166. doi:10.1007/11681878_8. ISBN 978-3-540-32731-8. Archived from the original (PDF) on 2012-10-16.
  8. ^ a b c d Lyubashevsky, Vadim; Micciancio, Daniele (2008). "Asymptotically Efficient Lattice-Based Digital Signatures" (PDF). Theory of Cryptography. Lecture Notes in Computer Science. Vol. 4948. pp. 37–54. doi:10.1007/978-3-540-78524-8_3. ISBN 978-3-540-78523-1.
  9. ^ Ding, Jintai; Xie, Xiang; Lin, Xiaodong (2012). A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem (PDF).
  10. ^ a b Peikert, Chris (2014-10-01). "Lattice Cryptography for the Internet". In Mosca, Michele (ed.). Post-Quantum Cryptography. Lecture Notes in Computer Science. Vol. 8772. Springer International Publishing. pp. 197–219. CiteSeerX 10.1.1.800.4743. doi:10.1007/978-3-319-11659-4_12. ISBN 978-3-319-11658-7. S2CID 8123895.
  11. ^ Lyubashevsky, Vadim (2012). "Lattice Signatures without Trapdoors" (PDF). Advances in Cryptology – EUROCRYPT 2012. Lecture Notes in Computer Science. Vol. 7237. pp. 738–755. doi:10.1007/978-3-642-29011-4_43. ISBN 978-3-642-29010-7.
  12. ^ a b c Micciancio, Daniele; Regev, Oded (2009). "Lattice-based Cryptography" (PDF). Post-Quantum Cryptography. pp. 147–191. doi:10.1007/978-3-540-88702-7_5. ISBN 978-3-540-88701-0. Archived from the original (PDF) on 2011-07-23.
  13. ^ Regev, Oded (2009). "On lattices, learning with errors, random linear codes, and cryptography" (PDF). Journal of the ACM. 56 (6): 1–40. arXiv:2401.03703. doi:10.1145/1568318.1568324. Archived from the original (PDF) on 2010-12-06.
  14. ^ Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). "Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems" (PDF). Cryptographic Hardware and Embedded Systems – CHES 2012. Lecture Notes in Computer Science. Vol. 7428. pp. 530–547. doi:10.1007/978-3-642-33027-8_31. ISBN 978-3-642-33026-1. Archived from the original (PDF) on 2014-05-18.
  15. ^ Singh, Vikram (2015). "A Practical Key Exchange for the Internet using Lattice Cryptography". Cryptology ePrint Archive.
  16. ^ Stehlé, Damien; Steinfeld, Ron; Tanaka, Keisuke; Xagawa, Keita (2009). "Efficient Public Key Encryption Based on Ideal Lattices: (Extended Abstract)" (PDF). Advances in Cryptology – ASIACRYPT 2009. Lecture Notes in Computer Science. Vol. 5912. pp. 617–635. doi:10.1007/978-3-642-10366-7_36. ISBN 978-3-642-10365-0.
  17. ^ Rivest, R.; Adleman, L.; Dertouzos, M. (1978). "On data banks and privacy homomorphisms" (PDF). In Foundations of Secure Computation. Academic Press. pp. 169–180.
  18. ^ Rivest, R. L.; Shamir, A.; Adleman, L. (1978). "A method for obtaining digital signatures and public-key cryptosystems". Communications of the ACM. 21 (2): 120–126. doi:10.1145/359340.359342. hdl:1721.1/148910.
  19. ^ Gentry, Craig (2009). "Fully homomorphic encryption using ideal lattices". Proceedings of the forty-first annual ACM symposium on Theory of computing. pp. 169–178. doi:10.1145/1536414.1536440. ISBN 978-1-60558-506-2.