41 research outputs found
G6K: Lattice Sieving Tool
No full textG6K is a C++ and Python library that implements several Sieve algorithms to be used in more advanced lattice reduction tasks. It follows the stateful machine framework from:
Martin R. Albrecht and Léo Ducas and Gottfried Herold and Elena Kirshanova and Eamonn W. Postlethwaite and Marc Stevens, The General Sieve Kernel and New Records in Lattice Reduction.
The article is available in this repository and on eprint
G6K
No full textG6K is a C++ and Python library that implements several Sieve algorithms to be used in more advanced lattice reduction tasks. It follows the stateful machine framework from:
Martin R. Albrecht and Léo Ducas and Gottfried Herold and Elena Kirshanova and Eamonn W. Postlethwaite and Marc Stevens, The General Sieve Kernel and New Records in Lattice Reduction.
The article is available in this repository and on eprint
G6K-GPU-Tensor
No full textG6K is an open-source C++ and Python (2) library that implements several Sieve algorithms to be used in more advanced lattice reduction tasks. It follows the stateful machine framework from:
Martin R. Albrecht and Léo Ducas and Gottfried Herold and Elena Kirshanova and Eamonn W. Postlethwaite and Marc Stevens, The General Sieve Kernel and New Records in Lattice Reduction.
The main source is available in fplll/g6k
This fork expands the G6K implementation with GPU, and in particular Tensor Core, accelerated sieves, and is accompanied by the work:
Léo Ducas, Marc Stevens, Wessel van Woerden, Advanced Lattice Sieving on GPUs, with Tensor Cores, Eurocrypt 2021 (eprint).
</p
G6K-GPU-Tensor
No full textG6K is an open-source C++ and Python (2) library that implements several Sieve algorithms to be used in more advanced lattice reduction tasks. It follows the stateful machine framework from:
Martin R. Albrecht and Léo Ducas and Gottfried Herold and Elena Kirshanova and Eamonn W. Postlethwaite and Marc Stevens, The General Sieve Kernel and New Records in Lattice Reduction.
The main source is available in fplll/g6k
This fork expands the G6K implementation with GPU, and in particular Tensor Core, accelerated sieves, and is accompanied by the work:
Léo Ducas, Marc Stevens, Wessel van Woerden, Advanced Lattice Sieving on GPUs, with Tensor Cores, Eurocrypt 2021 (eprint).
</p
On the Success Probability of Solving Unique SVP via BKZ
No full textAs lattice-based key encapsulation, digital signature, and fully homomorphic encryption schemes near standardisation, ever more focus is being directed to the precise estimation of the security of these schemes. The primal attack reduces key recovery against such schemes to instances of the unique Shortest Vector Problem (uSVP). Dachman-Soled et al. (Crypto 2020) recently proposed a new approach for fine-grained estimation of the cost of the primal attack when using Progressive BKZ for lattice reduction. In this paper we review and extend their technique to BKZ 2.0 and provide extensive experimental evidence of its accuracy. Using this technique we also explain results from previous primal attack experiments by Albrecht et al. (Asiacrypt 2017) where attacks succeeded with smaller than expected block sizes. Finally, we use our simulators to reestimate the cost of attacking the three lattice KEM finalists of the NIST Post Quantum Standardisation Process
Finding short integer solutions when the modulus is small
No full textWe present cryptanalysis of the inhomogenous short integer solution (ISIS) problem for anomalously small moduli by exploiting the geometry of BKZ reduced bases of -ary lattices.
We apply this cryptanalysis to examples from the literature where taking such small moduli has been suggested. A recent work [Espitau–Tibouchi–Wallet–Yu, CRYPTO 2022] suggests small versions of the lattice signature scheme FALCON and its variant MITAKA.
For one small parametrisation of FALCON we reduce the estimated security against signature forgery by approximately 26 bits. For one small parametrisation of MITAKA we successfully forge a signature in seconds
Quantum Algorithms for the Approximate <i>k</i>-List Problem and their Application to Lattice Sieving
No full textThe Shortest Vector Problem (SVP) is one of the mathematical foundations of lattice based cryptography. Lattice sieve algorithms are amongst the foremost methods of solving SVP. The asymptotically fastest known classical and quantum sieves solve SVP in a -dimensional lattice in 2^{\const d + \smallo(d)} time steps with 2^{\const' d + \smallo(d)} memory for constants . In this work, we give various quantum sieving algorithms that trade computational steps for memory.We first give a quantum analogue of the classical -Sieve algorithm [Herold--Kirshanova--Laarhoven, PKC'18] in the Quantum Random Access Memory (QRAM) model, achieving an algorithm that heuristically solves SVP in time steps using memory. This should be compared to the state-of-the-art algorithm [Laarhoven, Ph.D Thesis, 2015] which, in the same model, solves SVP in time steps and memory. In the QRAM model these algorithms can be implemented using \poly(d) width quantum circuits.Secondly, we frame the -Sieve as the problem of -clique listing in a graph and apply quantum -clique finding techniques to the -Sieve. Finally, we explore the large quantum memory regime by adapting parallel quantum search [Beals et al., Proc. Roy. Soc. A'13] to the -Sieve and giving an analysis in the quantum circuit model. We show how to heuristically solve SVP in time steps using quantum memory
A Novel Power-Sum PRG with Applications to Lattice-Based zkSNARKs
No full textzkSNARK is a cryptographic primitive that allows a prover to prove to a resource constrained verifier, that it has indeed performed a specified non-deterministic computation correctly, while hiding private witnesses. In this work we focus on lattice based zkSNARK, as this serves two important design goals. Firstly, we get post-quantum zkSNARK schemes with O(\log (\mbox{Circuit size})) sized proofs (without random oracles) and secondly,
the easy verifier circuit allows further bootstrapping by arbitrary (zk)SNARK schemes that offer additional or complementary properties. However, this goal comes with considerable challenges. The only known lattice-based bilinear maps are obtained using multi-linear maps of Garg, Gentry, and Halevi 2013 (GGH13), which have undergone considerable cryptanalytic attacks, in particular annihilation attacks.
In this work, we propose a (level-2) GGH13-encoding based zkSNARK which we show to be secure in the weak-multilinear map model of Miles-Sahai-Zhandry assuming a novel pseudo-random generator (PRG). We argue that the new PRG assumption is plausible based on the well-studied Newton\u27s identity on power-sum polynomials, as well as an analysis of hardness of computing Grobner bases for these polynomials. The particular PRG is designed for efficient implementation of the zkSNARK.
Technically, we leverage the 2-linear instantiation of the GGH13 graded encoding scheme to provide us with an analogue of bilinear maps and adapt the Groth16 (Groth, Eurocrypt 2016) protocol, although with considerable technical advances in design and proof. The protocol is non-interactive in the CRS model
Estimating quantum speedups for lattice sieves
No full textQuantum variants of lattice sieve algorithms are routinely used to assess the security of lattice based cryptographic constructions. In this work we provide a heuristic, non-asymptotic, analysis of the cost of several algorithms for near neighbour search on high dimensional spheres. These algorithms are key components of lattice sieves. We design quantum circuits for near neighbour search algorithms and provide software that numerically optimises algorithm parameters according to various cost metrics. Using this software we estimate the cost of classical and quantum near neighbour search on spheres. For the most performant near neighbour search algorithm that we analyse we find a small quantum speedup in dimensions of cryptanalytic interest. Achieving this speedup requires several optimistic physical and algorithmic assumptions
