IACR News item: 11 November 2024
Vadim Lyubashevsky, Gregor Seiler, Patrick Steuer
ePrint Report
The hardness of lattice problems offers one of the most promising
security foundations for quantum-safe cryptography. Basic schemes
for public key encryption and digital signatures are already close to
standardization at NIST and several other standardization bodies,
and the research frontier has moved on to building primitives with
more advanced privacy features. At the core of many such primi-
tives are zero-knowledge proofs. In recent years, zero-knowledge
proofs for (and using) lattice relations have seen a dramatic jump
in efficiency and they currently provide arguably the shortest, and
most computationally efficient, quantum-safe proofs for many sce-
narios. The main difficulty in using these proofs by non-experts
(and experts!) is that they have a lot of moving parts and a lot of
internal parameters depend on the particular instance that one is
trying to prove.
Our main contribution is a library for zero-knowledge and suc-
cinct proofs which consists of efficient and flexible C code under-
neath a simple-to-use Python interface. Users without any back-
ground in lattice-based proofs should be able to specify the lattice
relations and the norm bounds that they would like to prove and the
library will automatically create a proof system, complete with the
intrinsic parameters, using either the succinct proofs of LaBRADOR
(Beullens and Seiler, Crypto 2023) or the linear-size, though smaller
for certain application, proofs of Lyubashevsky et al. (Crypto 2022).
The Python interface also allows for common operations used in
lattice-based cryptography which will enable users to write and pro-
totype their full protocols within the syntactically simple Python
environment.
We showcase some of the library’s usefulness by giving protocol
implementations for blind signatures, anonymous credentials, the
zero-knowledge proof needed in the recent Swoosh protocol (Gaj-
land et al., Usenix 2024), proving knowledge of Kyber keys, and an
aggregate signature scheme. Most of these are the most efficient,
from a size, speed, and memory perspective, known quantum-safe
instantiations.
Additional news items may be found on the IACR news page.