Oblivious key-value stores and amplification for private set intersection
Many recent private set intersection (PSI) protocols encode input sets as polynomials. We
consider the more general notion of an oblivious key-value store (OKVS), which is a data …
consider the more general notion of an oblivious key-value store (OKVS), which is a data …
The general sieve kernel and new records in lattice reduction
Abstract We propose the General Sieve Kernel (G6K, pronounced/e. si. ka/), an abstract
stateful machine supporting a wide variety of lattice reduction strategies based on sieving …
stateful machine supporting a wide variety of lattice reduction strategies based on sieving …
Does the dual-sieve attack on learning with errors even work?
L Ducas, LN Pulles - Annual International Cryptology Conference, 2023 - Springer
Abstract Guo and Johansson (ASIACRYPT 2021), and MATZOV (tech. report 2022) have
independently claimed improved attacks against various NIST lattice candidates by adding a …
independently claimed improved attacks against various NIST lattice candidates by adding a …
Shortest vector from lattice sieving: a few dimensions for free
L Ducas - Annual International Conference on the Theory and …, 2018 - Springer
Asymptotically, the best known algorithms for solving the Shortest Vector Problem (SVP) in a
lattice of dimension n are sieve algorithms, which have heuristic complexity estimates …
lattice of dimension n are sieve algorithms, which have heuristic complexity estimates …
Quantum algorithms for attacking hardness assumptions in classical and post‐quantum cryptography
JF Biasse, X Bonnetain, E Kirshanova… - IET Information …, 2023 - Wiley Online Library
In this survey, the authors review the main quantum algorithms for solving the computational
problems that serve as hardness assumptions for cryptosystem. To this end, the authors …
problems that serve as hardness assumptions for cryptosystem. To this end, the authors …
Advanced lattice sieving on GPUs, with tensor cores
In this work, we study GPU implementations of various state-of-the-art sieving algorithms for
lattices (Becker-Gama-Joux 2015, Becker-Ducas-Gama-Laarhoven 2016, Herold …
lattices (Becker-Gama-Joux 2015, Becker-Ducas-Gama-Laarhoven 2016, Herold …
Estimating quantum speedups for lattice sieves
MR Albrecht, V Gheorghiu, EW Postlethwaite… - Advances in Cryptology …, 2020 - Springer
Quantum 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 …
lattice based cryptographic constructions. In this work we provide a heuristic, non …
Progressive lattice sieving
T Laarhoven, A Mariano - International Conference on Post-Quantum …, 2018 - Springer
Most algorithms for hard lattice problems are based on the principle of rank reduction: to
solve a problem in ad-dimensional lattice, one first solves one or more problem instances in …
solve a problem in ad-dimensional lattice, one first solves one or more problem instances in …
Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs
A Lombardi, V Vaikuntanathan - Annual International Cryptology …, 2020 - Springer
Abstract The Fiat-Shamir transform is a methodology for compiling a (public-coin) interactive
proof system for a language L into a non-interactive argument system for L. Proving security …
proof system for a language L into a non-interactive argument system for L. Proving security …
Improved Algorithms for the Approximate k-List Problem in Euclidean Norm
G Herold, E Kirshanova - IACR International Workshop on Public Key …, 2017 - Springer
We present an algorithm for the approximate k-List problem for the Euclidean distance that
improves upon the Bai-Laarhoven-Stehlé (BLS) algorithm from ANTS'16. The improvement …
improves upon the Bai-Laarhoven-Stehlé (BLS) algorithm from ANTS'16. The improvement …