LLL on the Average Nguyen, Phong Q.; Stehlé, Damien
Algorithmic Number Theory,
2006
Book Chapter, Conference Proceeding
Recenzirano
Despite their popularity, lattice reduction algorithms remain mysterious in many ways. It has been widely reported that they behave much more nicely than what was expected from the worst-case proved ...bounds, both in terms of the running time and the output quality. In this article, we investigate this puzzling statement by trying to model the average case of lattice reduction algorithms, starting with the celebrated Lenstra-Lenstra-Lovász algorithm (L3). We discuss what is meant by lattice reduction on the average, and we present extensive experiments on the average case behavior of L3, in order to give a clearer picture of the differences/similarities between the average and worst cases. Our work is intended to clarify the practical behavior of L3 and to raise theoretical questions on its average behavior.
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.
ModFalcon: Compact Signatures Based On Module-NTRU Lattices Chuengsatiansup, Chitchanok; Prest, Thomas; Stehlé, Damien ...
Proceedings of the 15th ACM Asia Conference on Computer and Communications Security,
10/2020
Conference Proceeding
Lattices lead to promising practical post-quantum digital signatures, combining asymptotic efficiency with strong theoretical security guarantees. However, tuning their parameters into practical ...instantiations is a delicate task. On the one hand, NIST round~2 candidates based on Lyubashevsky's design (such as dilithium and qtesla) allow several tradeoffs between security and efficiency, but at the expense of a large bandwidth consumption. On the other hand, the hash-and-sign falcon signature is much more compact and is still very efficient, but it allows only two security levels, with large compactness and security gaps between them. We introduce a new family of signature schemes based on the falcon design, which relies on module lattices. Our concrete instantiation enjoys the compactness and efficiency of falcon, and allows an intermediate security level. It leads to the most compact lattice-based signature achieving a quantum security above 128 bits.
Elementary functions such as sin or exp may naively be considered as good generators of random bits: the bit-runs output by these functions are believed to be statistically random most of the time. ...Here we investigate their computational hardness: given a part of the binary expansion of exp x, can one recover x? We describe a heuristic technique to address this type of questions. It relies upon Coppersmith’s heuristic technique — itself based on lattice reduction — for finding the small roots of multivariate polynomials modulo an integer. For our needs, we improve the lattice construction step of Coppersmith’s method: we describe a way to find a subset of a set of vectors that decreases the Minkowski theorem bound, in a rather general setup including Coppersmith-type lattices.
áóá In the present article, we investigate the accuracy of the factor R of the QR factorisation of an LLL-reduced basis. Our main contribution is the first fully rigorous perturbation analysis of the ...R-factor of LLL-reduced matrices under columnwise perturbations.
We show that a specific even unimodular lattice of dimension 80, first investigated by Schulze-Pillot and others, is extremal (i.e., the minimal nonzero norm is 8). This is the third known extremal ...lattice in this dimension. The known part of its automorphism group is isomorphic to SL2(F79), which is smaller (in cardinality) than the two previous examples. The technique to show extremality involves using the positivity of the Θ-series, along with fast vector enumeration techniques including pruning, while also using the automorphisms of the lattice.
PDF
