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 lattice-based public-key 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 Fujisaki-Okamoto transform [PKC:FujOka99] to obtain an IND-CCA secure public-key encryption scheme. Our IND-CCA key encapsulation mechanism (KEM) is obtained via a transform of Dent [IMA:Dent03]. This provides improved communication efficiency over using our IND-CCA public-key encryption scheme directly as a KEM; we also give a tight security proof for our IND-CCA 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 lattice-based schemes are already generally faster than current public-key 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 Ring-LWE 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].¹ The scheme also bears some resemblance to the scheme in [EPRINT:Peikert14], although we adopt a completely different approach to ciphertext compression and producing IND-CCA 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 side-channel 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 Ring-LWE and LWE sits the Module-LWE [Langlois:2015:WCA] problem. As recently shown in [EPRINT:AlbDeo17], this problem is polynomial-time equivalent to Ring-LWE with a large modulus. Such large modulus Ring-LWE instances are distinguished from our Ring-LWE instances by the module-rank required to solve them. That is, while the Ring-LWE 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:

• Power-of-two Cyclotomics: These are relatively well studied and admit very efficient implementations.

• Safe-Prime Cyclotomics: These are almost as good as power-of-two 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 safe-prime 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 non-trivial subfields of the cyclotomic field $\mathbf{Q}[X]/\Phi_p(X)$. By contrast, the presence of subfield towers in the power-of-two 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 Ring-LWE. In summary, for added flexibility and to allow a more conservative choice of field, we give the option of using safe-prime cyclotomics.

The use of safe-primes 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 safe-prime fields offers a nice compromise between efficiency and protection against potential future attacks. In addition, using safe-prime 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 power-of-two rings to be secure, and they are more efficient in this case. We only offer the safe-prime variant if subfield attacks are a concern, and to offer additional flexibility in terms of parameter choices.

Cryptographic Structure

We offer IND-CPA and IND-CCA variants of a public-key encryption scheme. The IND-CCA variant is based on the Fujisaki-Okamoto transform [PKC:FujOka99]. Our choice of this methodology for achieving IND-CCA security is that it permits a tight security proof. We also offer IND-CPA and IND-CCA variants of a KEM construction, with the IND-CCA variant being built using a construction of Dent [IMA:Dent03 Table 5] applied to our IND-CPA public-key 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.

: The different LIMA schemes.

The first two schemes in Table [table-lima-schemes] 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 “power-of-two” setting and four in the “safe-prime” 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.

: Parameter sets for use with LIMA.

Note that for LIMA-sp 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 LIMA-sp 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.²

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 constant-time.

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 IND-CPA 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 IND-CPA KEM.³ 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

Footnotes