Mitaka (三鷹): A Simpler, Parallelizable, Maskable Variant
of Falcon
We describe the 三鷹 signature scheme: a new hash-and-sign
scheme over NTRU lattices which can be seen as a variant of
NIST finalist FALCON. It achieves comparable efficiency but is
considerably simpler, online/offline, and easier to
parallelize and protect against side- channels, thus offering
significant advantages from an implementation standpoint. It
is also much more versatile in terms of parameter
selection..
On Gaussian sampling, smoothing parameter and application
to signatures
We present a general framework for polynomial-time lattice
Gaussian sampling. It revolves around a systematic study of
the discrete Gaussian measure and its samplers under
extensions of lattices; we first show that given lattices Λ′ ⊂
Λ we can sample efficiently in Λ if we know how to do so in Λ′
and the quotient Λ/Λ′, regardless of the primitivity of Λ′. As
a direct applications, we tackle the problem of domain
extension and restriction for sampling and propose a sampler
tailored for lattice filtrations, which can be seen as a broad
generalization of the
celebrated Klein’s
sampler.
The nearest-colattice algorithm: time-approximation
tradeoff for approx-CVP
We exhibit a hierarchy of polynomial time algorithms solving
approximate variants of the Closest Vector Problem. Our
contributions is on the one hand a heuristic algorithm
achieving the same distance as HSVP algorithms, and on
the other hand a proven reduction from approximating
the closest vector with a
factor \(\approx n^{\frac32}\beta^{\frac{3n}{2\beta}}\)
to the Shortest Vector Problem in dimension
\(\beta\).
Algebraic and euclidean lattices: optimal lattice
reduction and beyond
We introduce a framework for polynomial time reduction of
lattices over number fields, leveraging their recursive and
symplectic structures.
Implementation page