Recent developments have been made in the construction of cryptosystems with security based on the hardness of the lattice isomorphism problem (LIP). Due to lattice conjectures, one may expect in the future that breaking such schemes is computationally harder than most current lattice-based cryptosystems. To the best of our knowledge, there have not been any attempts to concretely instantiate a key encapsulation mechanism (KEM) based on LIP. In this work, we propose the first instance of such a KEM, following the framework of Ducas and van Woerden (EUROCRYPT 2022), using simple lattices. We present a randomness extractor derived from a hash function based on the short integer solution problem; define a concrete set of parameters for instantiating the scheme; provide a rigorous security estimation of an attacker trying to decode an encapsulated key through reductions to hard lattice problems; and use well-known methods to convert the IND-CPA secure KEM into an IND-CCA2 secure KEM, comparing the latter with other modern lattice-based KEMs. The resulting security is estimated under the assumption that an adversary cannot efficiently solve related instances of LIP, which is a consequence of the lack of cryptanalysis towards identifying isomorphism between lattices.
Recent developments have been made in the construction of cryptosystems with security based on the hardness of the lattice isomorphism problem (LIP). Due to lattice conjectures, one may expect in the future that breaking such schemes is computationally harder than most current lattice-based cryptosystems. To the best of our knowledge, there have not been any attempts to concretely instantiate a key encapsulation mechanism (KEM) based on LIP. In this work, we propose the first instance of such a KEM, following the framework of Ducas and van Woerden (EUROCRYPT 2022), using simple lattices. We present a randomness extractor derived from a hash function based on the short integer solution problem; define a concrete set of parameters for instantiating the scheme; provide a rigorous security estimation of an attacker trying to decode an encapsulated key through reductions to hard lattice problems; and use well-known methods to convert the IND-CPA secure KEM into an IND-CCA2 secure KEM, comparing the latter with other modern lattice-based KEMs. The resulting security is estimated under the assumption that an adversary cannot efficiently solve related instances of LIP, which is a consequence of the lack of cryptanalysis towards identifying isomorphism between lattices.
The Lattice Isomorphism Problem (LIP) is an emerging foundation for post-quantum cryptography thanks to the pioneering work of Ducas and van Woerden (EUROCRYPT '22). That work lays the foundation for LIP in cryptography with a zero-knowledge proof of knowledge (ZKPoK), a key-encapsulation mechanism, and a digital signature scheme which is further developed into the efficient signature Hawk (ASIACRYPT '22) using structured lattices. However, as compared to the development of lattice-based cryptography from the Short Integer Solution (SIS) and Learning with Errors (LWE) problems, LIP-based cryptography is yet to cover a rich variety of functionalities beyond the two basic ones: encrypting and digitally signing messages. This work is an effort to extend the landscape of LIP-based cryptography from the above basic primitives to more advanced ones by adapting techniques used in SIS-based and LWE-based primitives to LIP. We provide a public-key encryption (PKE) which encrypts plaintexts of integral vectors, and it comes with a zero-knowledge proof of plaintext knowledge. We use this PKE as a commitment scheme in the construction of a ZKPoK for quadratic relations, so this ZKPoK has a straightline extractor naturally. Using the same ZKPoK in non-interactive mode by Fiat-Shamir transformation, we introduce the first LIP-based blind signature scheme which is the blinded version of the digital signatures of Ducas and van Woerden. The security of our scheme stems from a new one-more Close Vector Problem (omCVP) assumption. This assumption is arguably an analogue of the one-more-SIS assumption by Agrawal et al. (CCS '22) and the one-more Short Vector Problem in Hawk signatures. To ensure confidence in omCVP, we provide a cryptanalysis attempt and convince that our parameter choice is in the safe zone.
The hardness of the lattice isomorphism problem (LIP) is a new lattice-based assumption used in asymmetric cryptography.However, there is yet to be a standard-model IND-CCA2secure public-key encryption scheme based on LIP.One promising candidate for such a scheme is the combination of an existing LIP-based IND-CPA-secure key encapsulation mechanism (KEM) by Ducas and van Woerden with the 𝑘-repetition framework by Rosen and Segev to construct an IND-CCA2-secure KEM.In this thesis, we provide strong evidence for our claim that this combination cannot be securely realized due to inherent qualities of LIP that prevent correlation across multiple ciphertexts of the KEM with independent public keys.We dub the sum of these qualities the Lattice Incompatibility Problem.Our analysis is extensive and provides insight into several fundamental properties of average-case LIP instances and their coefficient vectors.Additionally, we establish formal requirements for any other combination of an IND-CPA-secure asymmetric encryption scheme with 𝑘-repetition and demonstrate that this combination cannot be black-box for arbitrary IND-CPA-secure schemes.As part of our empirical evaluations, we also present a description, proof of correctness, and implementation of a sampling algorithm for the discrete Gaussian distribution on arbitrary quadratic forms that avoids taking the Cholesky decomposition for improved numerical stability.i Zusammenfassung Die Schwierigkeit des Gitterisomorphismusproblems (LIP) wird als neue gitterbasierte Annahme zur Konstruktion von asymmetrischer Kryptographie genutzt.Jedoch gibt es bis jetzt noch kein gegen adaptive aktive Angreifer sicheres asymmetrisches Verschlüsselungsverfahren, das auf der Schwierigkeit von LIP beruht.Ein möglicher Kandidat für ein solches Verfahren entsteht durch die Kombination aus einem existierenden LIP-basierten Schlüsselenkapsulierungsmechanismus (KEM) von Ducas und Woerden zusammen mit dem 𝑘-Wiederholungs-Rahmenwerk von Rosen und Segev, die zu einem entsprechend gegen solche Angreifer sicherem KEM führen könnte.In dieser Arbeit präsentieren wir starke Argumente dafür, dass diese Kombination durch inhärente Merkmale von LIP, die eine Korrelation über mehrere Chiffrate des KEMs mit unabhängigen öffentlichen Schlüsseln verhindern, nicht auf sichere Art realisierbar ist.Wir bezeichnen die Summe dieser Eigenschaften als das Gitterinkompatibilitätsproblem.Unsere Analyse ist umfänglich und zeigt einige grundlegende Eigenschaften durchschnittlicher LIP-Instanzen und ihrer Koeffizientenvektoren auf.Zusätzlich geben wir formale Anforderungen an, die für jede Kombination eines gegen passive Angreifer sicheren asymmetrischen Verschlüsselungsverfahrens mit der 𝑘-Wiederholung erforderlich sind.Wir demonstrieren zudem, dass diese Kombination nicht generisch für beliebige Verfahren umgesetzt werden kann.Weiter stellen wir als Teil unserer empirischen Evaluationen einen Algorithmus samt Beschreibung, Korrektheitsbeweis und Implementierung vor, der Stichproben der diskreten Gauß-Verteilung über beliebigen quadratischen Formen zieht, ohne dabei die Cholesky-Zerlegung der Form zu ermitteln, was zu verbesserter numerischer Stabilität führt.
The invention of public-key cryptography (PKC) by Diffie and Hellman in 1976 is one of two milestones marking the beginning of modern cryptography. The security of a PKC system requires that it should be infeasible to compute the private key from a given public key, which in turn is typically guaranteed by the difficulty in solving some cryptographic-friendly mathematical problems. Among those problems, the integer factorization and discrete logarithm problems play pivotal roles in the development of public-key cryptography. In particular, the assumption that there is no polynomial time (classical) algorithm that solves the above two problems constitutes the basis for the security of almost all currently used public-key cryptosystems, such as RSA and ElGamal. However, Shor [1] found an efficient quantum solving algorithm for the integer factorization and discrete logarithm problems in 1994, which would destroy the security basis for most real deployed PKC systems if large-scale quantum computers become available. The rapid development of quantum technology in recent years suggests that we are getting closer to the quantum crisis of current PKC systems. As a response to the quantum crisis, the research community has made many efforts to post-quantum cryptography (PQC) that are believed to resist quantum computer attacks. Lattice-based cryptography is one of the main directions in this area, and has become the most promising PQC candidate for standardization. The research of lattice-based cryptography dates back to the seminal work of Ajtai [2], which first based the security of cryptographic primitives on the difficulty of solving some lattice problems such as the approximate shortest vector problem and the closest vector problem. After more than two decades of development, lattice-based cryptography has gained substantial progress. In theory, we have witnessed the construction of many powerful cryptographic primitives that were not known before. In practice, the public key size of lattice-based cryptosystems has been significantly reduced from several gigabytes to a few kilobytes. For current applications and standardization, key exchanges, public-key encryptions (PKEs) and signatures are the most desired lattice-based cryptosystems, where the first two are often used to ensure information secrecy, while the last provides information authentication. Note that public-key encryptions are equivalent to two-round key exchanges, also known as the key encapsulation mechanism (KEM). In the following, we focus on lattice-based PKEs/KEMs. The design principle of lattice-based PKEs/KEMs follows two approaches: a trapdoor one-way function and an approximate commutative one-way function. In the first approach, a trapdoor one-way function f and its trapdoor f−1 are generated as the public key and private key. A plaintext m is encrypted as c = f(m), and the ciphertext is decrypted as m = f−1(c). The NTRU scheme and its variants follow such an approach. In the second approach, an approximate commutative function fs and a random input a are generated, the public key is (a, b = fs(a)) and the private key is s. A plaintext m is encrypted as c1 = gr(a), c2 = gr(b) + E(m), where r is a random element, g is an approximate commutative one-way function and E is the encoding of an error-correction code. The ciphertext (c1, c2) is decrypted as m = D(c2 − fs(c1)), where D is the decoding of an error-correction code. The correctness of decryption is guaranteed by the approximate commutative property (gr(b) = gr(fs(a)) ≈ fs(gr(a)) = fs(c1)) and the error-correction code. Learning with errors (LWE) problem-based PKE/KEM schemes and their variants follow such an approach. The standardization of PQC has received substantial support from national funding agencies, such as the European Union projects PQCrypto and SAFEcrypto. The USA National Institute of Standard and Technology (NIST) started the post-quantum standardization project in 2012, organized a worldwide ‘competition’ in 2016 and plans to deliver draft standards before 2024. After two rounds of evaluation, seven schemes were accepted as the round-three candidates on 22 July 2020, of which five are lattice-based schemes. In 2017, the International organization for standardization started a study project of post-quantum cryptography named SD8. Most LWE-based PKE schemes such as Kyber and LAC follow the Lindner-Peikert framework [3] up to the choices of ring structure, noise distribution and parameters. As the size of noise in lattice-based PKEs/EKMs is typically larger than the lower bits of the ciphertext, many schemes often artificially drop a few lower bits to optimize the practical performance without significantly increasing the final decryption noise. Kyber [4] is one of the most promising PKE/KEM candidates in the NIST PQC standardization, whose security is provably based on the difficulty of so-called module LWE (MLWE) problems. The use of MLWE allowed Kyber to obtain additional flexibility and security advantages, while keeping the same efficiency as those based on the ring-LWE problems. The strategy of dropping some lower bits is used to compress both the public-key and ciphertext sizes. For a targeted 128-bit quantum security, the public-key and ciphertext sizes of Kyber is around a single kilobyte. LAC [5] uses several techniques to reduce the modulus as small as possible: it uses a byte-level modulus, embeds powerful error-correcting codes to maximize the noise-modulus rate, provides a different style of modulus to avoid potential attacks for special polynomial ring structures and optimizes the polynomial multiplication algorithm of the bit-level secret and noise. Based on these techniques, LAC reduces the public key to 544–1056 bytes and the ciphertext to 664–1464 bytes. Meanwhile, it achieves similar computational performance compared with NTT technique schemes. By observing the asymmetries in lattice-based cryptosystems, Zhang and Yu et al. [6] proposed asymmetric MLWE and asymmetric MSIS problems, which yield further size-optimized KEMs and signature schemes to those from standard counterparts. Compared to the seven NIST round-three candidates at Category III security, their KEM scheme has parameters (public key + ciphertext size) smaller than Classic McEliece, CRYSTALS-Kyber, NTRU and Saber; their signature scheme has parameters (public key + signature size) smaller than CRYSTALS-Dilithium and Rainbow, but slightly larger than FALCON, where CRYSTALS-Kyber, NTRU, Saber, CRYSTALS-Dilithium and FALCON are lattice-based schemes. One important application of lattice-based PKEs/KEMs is to build authenticated key exchange (AKE), which could provide additional authentication to the established session key. There are several generic ways to construct AKE from lattice-based PKEs/KEMs. In the PKE setting, Xue and Lu et al. [7] proposed a more compact KEM-based framework via a new primitive named ‘2-key KEM’, which shares some item between different ciphertexts. In the only password setting, Zhang and Yu [8] presented a two-round PAKE framework from the splittable-PKEs that can be instantiated from lattices. The only known AKE that does not rely on lattice-based PKEs/KEMs was given in Ref. [9], which has two-round messages and provides implicit authentication. This work was supported by the National Natural Science Foundation of China (6197239 to X.L.; 62022018 and 61932019 to J.Z.) and the National Key Research and Development Program of China (2018YFB0804105 to J.Z.). Conflict of interest statement. None declared.
The NTRU lattice is a promising candidate to construct practical cryptosystems, in particular key encapsulation mechanism (KEM), resistant to quantum computing attacks. Nevertheless, there are still some inherent obstacles to NTRU-based KEM schemes in having integrated performance, taking security, bandwidth, error probability, and computational efficiency \emph{as a whole}, that is as good as and even better than their \{R,M\}LWE-based counterparts. In this work, we solve this problem by presenting a new family of NTRU-based KEM schemes, referred to as CTRU and CNTR. By bridging low-dimensional lattice codes and high-dimensional NTRU-lattice-based cryptography with careful design and analysis, to the best of our knowledge CTRU and CNTR are the first NTRU-based KEM schemes with scalable ciphertext compression via only one \emph{single} ciphertext polynomial, and are the first that could outperform \{R,M\}LWE-based KEM schemes in integrated performance. For instance, compared to Kyber that is currently the only standardized KEM by NIST, on the recommended parameter set CNTR-768 has about 12% smaller ciphertext size while encapsulating 384-bit keys compared to the fixed 256-bit key size of Kyber, security strengthened by (8,7) bits for classical and quantum security respectively, and significantly lower error probability (2−230 of CNTR-768 vs. 2−164 of Kyber-768). In comparison with the state-of-the-art AVX2 implementation of Kyber-768, CNTR-768 is faster by 1.9X in KeyGen, 2.6X in Encaps, and 1.2X in Decaps, respectively. When compared to the NIST Round 3 finalist NTRU-HRSS, our CNTR-768 has about 15% smaller ciphertext size, and the security is strengthened by (55,49) bits for classical and quantum security respectively. As for the AVX2 implementation, CNTR-768 is faster than NTRU-HRSS by 19X in KeyGen, 2.3X in Encaps, and 1.6X in Decaps, respectively.
Key encapsulation mechanism (KEM) is an important key distribution mechanism that not only allows both sender and receiver to safely share a random session key, but also can be mainly applied to construct a hybrid public key encryption scheme. In this paper, we give an positive answer to the question of if it is possible to build an efficient KEM over lattices. More precisely, we design an efficient KEM scheme in standard model based on ideal lattices. We prove that the proposed scheme captures indistinguishability against active chosen ciphertext attacks (IND-CCA) under the ring learning with errors problem, or more formally, IND-CCA security. Compared with the current CCA secure KEM schemes based on lattices in the standard model, our scheme has shorter public key, secret key and encapsulation ciphertext. In addition, our KEM scheme realizes IND-CCA security in the standard model.
Rapid advances in quantum computing, together with the announcement by the National Institute of Standards and Technology (NIST) to define new standards for digitalsignature, encryption, and key-establishment protocols, have created significant interest in post-quantum cryptographic schemes. This paper introduces Kyber (part of CRYSTALS - Cryptographic Suite for Algebraic Lattices - a package submitted to NIST post-quantum standardization effort in November 2017), a portfolio of post-quantum cryptographic primitives built around a key-encapsulation mechanism (KEM), based on hardness assumptions over module lattices. Our KEM is most naturally seen as a successor to the NEWHOPE KEM (Usenix 2016). In particular, the key and ciphertext sizes of our new construction are about half the size, the KEM offers CCA instead of only passive security, the security is based on a more general (and flexible) lattice problem, and our optimized implementation results in essentially the same running time as the aforementioned scheme. We first introduce a CPA-secure public-key encryption scheme, apply a variant of the Fujisaki-Okamoto transform to create a CCA-secure KEM, and eventually construct, in a black-box manner, CCA-secure encryption, key exchange, and authenticated-key-exchange schemes. The security of our primitives is based on the hardness of Module-LWE in the classical and quantum random oracle models, and our concrete parameters conservatively target more than 128 bits of postquantum security.