About LIMA
Note: This is Version 1.1 of the LIMA specification which includes a number of optimizations and minor corrections over the first specification. We also include different parameter choices, which are enabled by some of our minor modifications.
We introduce LIMA (LattIce MAthematics), a set of latticebased publickey encryption and key encapsulation mechanisms, offering chosen plaintext security and chosen ciphertext security options. LIMA mixes conservative, standard and boring design choices with some efficiency improvements and flexibility. These factors are exhibited in its genesis: it is based on the ring variant [EC:LyuPeiReg10] of the LWE problem [STOC:Regev05] and on the encryption construction in [RSA:LinPei11]. We use the FujisakiOkamoto transform [PKC:FujOka99] to obtain an INDCCA secure publickey encryption scheme. Our INDCCA key encapsulation mechanism (KEM) is obtained via a transform of Dent [IMA:Dent03]. This provides improved communication efficiency over using our INDCCA publickey encryption scheme directly as a KEM; we also give a tight security proof for our INDCCA KEM.
Thus our basic building blocks use highly respected and well studied cryptographic components. Our preference for “boring and simple” is illustrated by the fact that while our construction is efficient, other constructions such as [EPRINT:BDKLLS17] achieve higher encryption and decryption speeds. However, run times for latticebased schemes are already generally faster than current publickey schemes and thus we view optimizing run times as being less important compared to simplicity.
Mathematical Structure
For efficiency we use a ring variant. Encryption based on RingLWE has been extensively studied in the literature [ACISP:BaiGal14; EC:LyuPeiReg10; EC:LyuPeiReg13; CMVRCPV15]. The core component is essentially the Lyubashevsky et al. scheme [EC:LyuPeiReg10], or (equivalently) the BGV [BraGenVai14] homomorphic encryption scheme, with the message being in the upper bits as opposed to the lower bits. This is sometimes referred to as the FV scheme [EPRINT:FanVer12].^{1} The scheme also bears some resemblance to the scheme in [EPRINT:Peikert14], although we adopt a completely different approach to ciphertext compression and producing INDCCA variants. A lot of prior research has been conducted not only into the basic scheme, but also into implementation aspects [CHES:LSRGKV15; CHES:RVMCV14], including protecting against sidechannel attacks [CHES:RRVV15].
We opted for the ring variant of LWE to reduce the ciphertext size and to increase performance compared to LWE. In between RingLWE and LWE sits the ModuleLWE [Langlois:2015:WCA] problem. As recently shown in [EPRINT:AlbDeo17], this problem is polynomialtime equivalent to RingLWE with a large modulus. Such large modulus RingLWE instances are distinguished from our RingLWE instances by the modulerank required to solve them. That is, while the RingLWE problem considered here requires one to find unusually short vectors in a module of rank three, this dimension is bigger in constructions such as [EPRINT:BDKLLS17]. At present, it is unclear if any loss of security is implied by using smaller module rank for ranks $> 1$.
We offer two forms of ring to use within the LIMA system:

Poweroftwo Cyclotomics: These are relatively well studied and admit very efficient implementations.

SafePrime Cyclotomics: These are almost as good as poweroftwo cyclotomics in terms of the ring geometry, but are slightly less efficient.
The reasons for offering the second option for the ring are twofold. Firstly, using safeprime cyclotomics allows us to create a more flexible parameter space in terms of the ring dimension. Secondly, recall that a prime $p$ is called “safe” if $p=2 \cdot p’+1$ for another prime $p’$. This implies that there are only two nontrivial subfields of the cyclotomic field $\mathbf{Q}[X]/\Phi_p(X)$. By contrast, the presence of subfield towers in the poweroftwo case raises the question of whether this could leave open routes for attack such as those in [CheJeoLee16; C:AlbBaiDuc16]. While it was shown soon after that towers of subfields are not required for these attacks to succeed [EC:KirFou17], it appears prudent to hedge against possible future attacks regardless. For example, [EC:BBVLV17] shows that, for some fields, the presence of subfields can lead to a much easier lattice problem. We stress, however, that none of these subfield attacks are currently applicable to RingLWE. In summary, for added flexibility and to allow a more conservative choice of field, we give the option of using safeprime cyclotomics.
The use of safeprimes appears to mitigate the possibility of attacks via subfields, but it also avoids the complex ring geometry associated with picking fields with large Galois group, such as the choice made in [EPRINT:BCLV16]. Thus, we believe that using safeprime fields offers a nice compromise between efficiency and protection against potential future attacks. In addition, using safeprime cyclotomics allows us, with a little extra work, to be able to still use FFTs to evaluate the main polynomial products involved in the operation of our schemes. Thus, we think safe prime cyclotomic fields offer a good compromise between the benefits of the use of two power cyclotomics and fields defined by polynomials with large Galois groups.
We stress that we consider our schemes instantiated with the poweroftwo rings to be secure, and they are more efficient in this case. We only offer the safeprime variant if subfield attacks are a concern, and to offer additional flexibility in terms of parameter choices.
Cryptographic Structure
We offer INDCPA and INDCCA variants of a publickey encryption scheme. The INDCCA variant is based on the FujisakiOkamoto transform [PKC:FujOka99]. Our choice of this methodology for achieving INDCCA security is that it permits a tight security proof. We also offer INDCPA and INDCCA variants of a KEM construction, with the INDCCA variant being built using a construction of Dent [IMA:Dent03 Table 5] applied to our INDCPA publickey encryption scheme. Dent’s transformation did not have a tight security proof, so in [ES:AOPPS17] we also provide a new proof that is tight in our specific context. We note that a related but more generic tight reduction was recently given in [EPRINT:HofHovKil17].
Ignoring parameter sizes for the moment, this document therefore defines eight possible configurations for LIMA, as listed in the table below.
Name  Ring Variant  Functionality  Security 

LIMA2pEncCPA  TwoPower  Encryption  INDCPA 
LIMAspEncCPA  SafePrime  Encryption  INDCPA 
LIMA2pKEMCPA  TwoPower  Key Encapsulation  INDCPA 
LIMAspKEMCPA  SafePrime  Key Encapsulation  INDCPA 
LIMA2pEncCCA  TwoPower  Encryption  INDCCA 
LIMAspEncCCA  SafePrime  Encryption  INDCCA 
LIMA2pKEMCCA  TwoPower  Key Encapsulation  INDCCA 
LIMAspKEMCCA  SafePrime  Key Encapsulation  INDCCA 
: The different LIMA schemes.
The first two schemes in Table [tablelimaschemes] should not be used (without care) in any application. The third and fourth schemes should also be used with care, but are included here as they are mentioned in the NIST call as being potentially desirable in some key exchange applications.
All the LIMA schemes are derived from a base encryption algorithm EncCPASub
which can result in decryption failures. In particular EncCPASub
could make a choice of randomness that produces in a ciphertext which results in a decryption failure (or even decrypts to the wrong message).
This is a standard problem in lattice based schemes and can cause problems in operation and in security proofs.
Our parameters are chosen to ensure that this happens with negligible probability.
We define six parameter sets to be used in conjunction with the eight different LIMA schemes. Two of these parameter sets are in the “poweroftwo” setting and four in the “safeprime” setting. This yields a total of 28 different schemes, with this flexibility enabling scaling to larger messages spaces and/or increased security levels. The seven parameter sets are shown in the table below.
Scheme  $N$  $q$ 

LIMA2p  512  18433 
LIMA2p  1024  40961 
LIMA2p  2048  40961 
LIMAsp  1018  12521473 
LIMAsp  1306  48181249 
LIMAsp  1822  44802049 
LIMAsp  2062  16900097 
: Parameter sets for use with LIMA.
Note that for LIMAsp parameter sets, the larger value of $q$ is to enable the FFT to be efficiently computed via Bluestein’s algorithm. This places some requirements on the value of $q$. Using the FFT also means that ring multiplication can be more easy implemented on highly parallel processors such as GPUs. Another option in the LIMAsp case would have been to abandon the usage of the FFT methods and use smaller values of $q$. This, however, would have come at the expense of an estimated slowdown by a factor of about two.^{2}
Random Seeds
All random seeds/coins for our algorithms are passed through a NIST approved XOF, from NIST SP 800 185 [NIST:SP800185]. This means we do not pass the seeds/coins through a DRBG first, as recommended by NIST (in the FAQ related to this call).
The XOF output is used to generate random finite field elements, symmetric keys, and (importantly for us) samples from a distribution somewhat close to a Gaussian distribution. For this latter task we adopt a method suggested in [USENIX:ADPS16], which is both efficient (in software and hardware) and constanttime.
Ciphertext Compression
All ciphertexts are compressed in the sense of ignoring coefficients of the “message carrying component” which contains no information about the message. Further compression can be obtained by Huffman encoding the ring elements.
In the case of our INDCPA KEM, a further form of compression is possible by utilizing the reconciliation approach of [EPRINT:Peikert14]. We did not use this for two reasons. Firstly, it is only applicable to the INDCPA KEM.^{3} Secondly, there is some concern in the community over patenting of reconciliation mechanisms, and we wanted to avoid uncertainties arising from unresolved issues relating to the licensing of patents.
Intellectual Property
To our knowledge, the algorithms contained in this proposal are not covered by any intellectual property constraints.
The implementations provided in this proposal were written by Valery Osheter, Guy Peer and Nigel P. Smart.
References
Albrecht, Martin R., and Amit Deo. 2017. “Large Modulus RingLWE >= ModuleLWE.” Cryptology ePrint Archive, Report 2017/612.
Albrecht, Martin R., Shi Bai, and Léo Ducas. 2016. “A Subfield Lattice Attack on Overstretched NTRU Assumptions  Cryptanalysis of Some FHE and Graded Encoding Schemes.” In CRYPTO 2016, Part I , edited by Matthew Robshaw and Jonathan Katz, 9814:153–78. LNCS. Springer, Heidelberg. doi: 10.1007/9783662530184_6 .
Albrecht, Martin R., Emmanuela Orsini, Kenneth G. Paterson, Guy Peer, and Nigel P. Smart. 2017. “Tightly Secure RingLwe Based Key Encapsulation with Short Ciphertexts.” In Computer Security  ESORICS 2017  22nd European Symposium on Research in Computer Security, Oslo, Norway, September 1115, 2017, Proceedings, Part I , edited by Simon N. Foley, Dieter Gollmann, and Einar Snekkenes, 10492:29–46. Lecture Notes in Computer Science. Springer. doi: 10.1007/9783319664026_4 .
Alkim, Erdem, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. 2016. “PostQuantum Key Exchange  A New Hope.” In 25th USENIX Security Symposium, USENIX Security 16, Austin, Tx, Usa, August 1012, 2016. , edited by Thorsten Holz and Stefan Savage, 327–43. USENIX Association. https://www.usenix.org/conference/usenixsecurity16/ technicalsessions/presentation/alkim .
Bai, Shi, and Steven D. Galbraith. 2014. “Lattice Decoding Attacks on Binary LWE.” In ACISP 14 , edited by Willy Susilo and Yi Mu, 8544:322–37. LNCS. Springer, Heidelberg. doi: 10.1007/9783319083445_21 .
Bauch, Jens, Daniel J. Bernstein, Henry de Valence, Tanja Lange, and Christine van Vredendaal. 2017. “Short Generators Without Quantum Computers: The Case of Multiquadratics.” In EUROCRYPT 2017, Part I , edited by JeanSébastien Coron and Jesper Buus Nielsen, 10210:27–59. LNCS. Springer, Heidelberg.
Bernstein, Daniel J., Chitchanok Chuengsatiansup, Tanja Lange, and Christine van Vredendaal. 2016. “NTRU Prime.” Cryptology ePrint Archive, Report 2016/461.
Bos, Joppe, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, and Damien Stehlé. 2017. “CRYSTALS – Kyber: A CCASecure ModuleLatticeBased KEM.” Cryptology ePrint Archive, Report 2017/634.
Brakerski, Zvika, Craig Gentry, and Vinod Vaikuntanathan. 2014. “(Leveled) Fully Homomorphic Encryption Without Bootstrapping.” TOCT 6 (3): 13:1–13:36. doi: 10.1145/2633600 .
Chen, Donald Donglong, Nele Mentens, Frederik Vercauteren, Sujoy Sinha Roy, Ray C. C. Cheung, Derek Pao, and Ingrid Verbauwhede. 2015. “HighSpeed Polynomial Multiplication Architecture for RingLWE and SHE Cryptosystems.” IEEE Trans. on Circuits and Systems 62I (1): 157–66. doi: 10.1109/TCSI.2014.2350431 .
Cheon, Jung Hee, Jinhyuck Jeong, and Changmin Lee. 2016. “An Algorithm for Ntru Problems and Cryptanalysis of the Ggh Multilinear Map Without a LowLevel Encoding of Zero.” LMS Journal of Computation and Mathematics 19 (A). London Mathematical Society: 255–66. doi: 10.1112/S1461157016000371 .
Dent, Alexander W. 2003. “A Designer’s Guide to KEMs.” In 9th Ima International Conference on Cryptography and Coding , edited by Kenneth G. Paterson, 2898:133–51. LNCS. Springer, Heidelberg.
Fan, Junfeng, and Frederik Vercauteren. 2012. “Somewhat Practical Fully Homomorphic Encryption.” Cryptology ePrint Archive, Report 2012/144.
Fujisaki, Eiichiro, and Tatsuaki Okamoto. 1999. “How to Enhance the Security of PublicKey Encryption at Minimum Cost.” In PKC’99 , edited by Hideki Imai and Yuliang Zheng, 1560:53–68. LNCS. Springer, Heidelberg.
Hofheinz, Dennis, Kathrin Hövelmanns, and Eike Kiltz. 2017. “A Modular Analysis of the FujisakiOkamoto Transformation.” Cryptology ePrint Archive, Report 2017/604.
Kirchner, Paul, and PierreAlain Fouque. 2017. “Revisiting Lattice Attacks on Overstretched NTRU Parameters.” In EUROCRYPT 2017, Part I , edited by JeanSébastien Coron and Jesper Buus Nielsen, 10210:3–26. LNCS. Springer, Heidelberg.
Langlois, Adeline, and Damien Stehlé. 2015. “WorstCase to AverageCase Reductions for Module Lattices.” Designs, Codes & Cryptography 75 (3): 565–99. doi: http://dx.doi.org/10.1007/s1062301499384 .
Lindner, Richard, and Chris Peikert. 2011. “Better Key Sizes (and Attacks) for LWEBased Encryption.” In CTRsa 2011 , edited by Aggelos Kiayias, 6558:319–39. LNCS. Springer, Heidelberg.
Liu, Zhe, Hwajeong Seo, Sujoy Sinha Roy, Johann Großschädl, Howon Kim, and Ingrid Verbauwhede. 2015. “Efficient RingLWE Encryption on 8Bit AVR Processors.” In CHES 2015 , edited by Tim Güneysu and Helena Handschuh, 9293:663–82. LNCS. Springer, Heidelberg. doi: 10.1007/9783662483244_33 .
Lyubashevsky, Vadim, Chris Peikert, and Oded Regev. 2010. “On Ideal Lattices and Learning with Errors over Rings.” In EUROCRYPT 2010 , edited by Henri Gilbert, 6110:1–23. LNCS. Springer, Heidelberg.
———. 2013. “A Toolkit for RingLWE Cryptography.” In EUROCRYPT 2013 , edited by Thomas Johansson and Phong Q. Nguyen, 7881:35–54. LNCS. Springer, Heidelberg. doi: 10.1007/9783642383489_3 .
NIST National Institute for Standards and Technology. 2016. “SHA3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash.”
Peikert, Chris. 2014. “Lattice Cryptography for the Internet.” Cryptology ePrint Archive, Report 2014/070.
Regev, Oded. 2005. “On Lattices, Learning with Errors, Random Linear Codes, and Cryptography.” In 37th Acm Stoc , edited by Harold N. Gabow and Ronald Fagin, 84–93. ACM Press.
Reparaz, Oscar, Sujoy Sinha Roy, Frederik Vercauteren, and Ingrid Verbauwhede. 2015. “A Masked RingLWE Implementation.” In CHES 2015 , edited by Tim Güneysu and Helena Handschuh, 9293:683–702. LNCS. Springer, Heidelberg. doi: 10.1007/9783662483244_34 .
Footnotes

We do not use any homomorphic properties in this document, we just mention this to show the theoretical pedigree and prior analysis of our approach. ↩

In this case we would recommend using Karatsuba multiplication to multiply the ring elements, as opposed to coordinate wise multiplication in the FFT domain. ↩

In [EPRINT:Peikert14] a method of obtaining an INDCCA secure KEM is given, but it is less efficient than ours. ↩