Publication

Geometric Considerations in Lattice Programming

Publications associées (28)

Mean value theorems for collections of lattices with a prescribed group of symmetries

Euclidean lattices are mathematical objects of increasing interest in the fields of cryptography and error-correcting codes. This doctoral thesis is a study on high-dimensional lattices with the motivation to understand how efficient they are in terms of b ...

EPFL2024

Hausdorff dimension of fermions on a random lattice

Mattia Guerino Varrone

Geometric properties of lattice quantum gravity in two dimensions are studied numerically via Monte Carlo on Euclidean Dynamical Triangulations. A new computational method is proposed to simulate gravity coupled with fermions, which allows the study of int ...

Elsevier2024

BLOOM: Bimodal Lattice One-out-of-Many Proofs and Applications

Ngoc Khanh Karol Nguyen

We give a construction of an efficient one-out-of-many proof system, in which a prover shows that he knows the pre-image for one element in a set, based on the hardness of lattice problems. The construction employs the recent zero-knowledge framework of Ly ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Approximate CVPp in time 2(0.802n)

Friedrich Eisenbrand, Moritz Andreas Venzin

We show that a constant factor approximation of the shortest and closest lattice vector problem in any l(p)-norm can be computed in time 2((0.802 + epsilon)n). This matches the currently fastest constant factor approximation algorithm for the shortest vect ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2022

On the Mordell-Weil lattice of y(2) = x(3) + bx plus t(3n+1) in characteristic 3

Gauthier Leterrier

We study the elliptic curves given by y(2) = x(3) + bx + t(3n+1) over global function fields of characteristic 3 ; in particular we perform an explicit computation of the L-function by relating it to the zeta function of a certain superelliptic curve u(3) ...

SPRINGER INT PUBL AG2022

Efficient protocols for oblivious linear function evaluation from ring-LWE

Juan Ramón Troncoso-Pastoriza

An oblivious linear function evaluation protocol, or OLE, is a two-party protocol for the function f (x) = ax + b, where a sender inputs the field elements a, b, and a receiver inputs x and learns f (x). OLE can be used to build secret-shared multiplicatio ...

IOS PRESS2022

Formula Normalizations in Verification

Viktor Kuncak, Mario Bucev, Simon Guilloud, Dragana Milovancevic

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...

2023

Almost impossible E_8 and Leech lattices

Maryna Viazovska

We start this short note by introducing two remarkable mathematical objects: the E8E8 root lattice Lambda8Lambda8 in 8-dimensional Euclidean space and the Leech lattice Lambda24Lambda24 in 24-dimensional space. These two lattices stand out among their lat ...

2021

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

b \in \Z^m

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

EPFL2020

Synthesis of Flexible Accelerators for Early Adoption of Ring-LWE Post-quantum Cryptography

Francesco Regazzoni, Hamid Nejatollahi, Subhadeep Banik

The advent of the quantum computer makes current public-key infrastructure insecure. Cryptography community is addressing this problem by designing, efficiently implementing, and evaluating novel public-key algorithms capable of withstanding quantum comput ...

ASSOC COMPUTING MACHINERY2020

On compact representations of Voronoi cells of lattices

Christoph Hunkenschröder, Matthias Schymura

In a seminal work, Micciancio and Voulgaris (SIAM J Comput 42(3):1364-1391, 2013) described a deterministic single-exponential time algorithm for the closest vector problem (CVP) on lattices. It is based on the computation of the Voronoi cell of the given ...

SPRINGER HEIDELBERG2020

Linear Flavour-Wave Theory of SU(N) Lattice Models with Arbitrary Irreducible Representations

Francisco Hyunkyu Kim

This thesis explores various approaches of studying the long-range colour order of antiferromagnetic SU(N) Heisenberg models with the linear flavour-wave theory (LFWT). The LFWT is an extension of the well-known SU(2) spin-wave theory to SU(N), and this se ...

EPFL2019

On compact representations of Voronoi cells of lattices

Christoph Hunkenschröder, Matthias Schymura

In a seminal work, Micciancio & Voulgaris (2010) described a deterministic single-exponential time algorithm for the Closest Vector Problem (CVP) on lattices. It is based on the computation of the Voronoi cell of the given lattice and thus may need exponen ...

SPRINGER INTERNATIONAL PUBLISHING AG2018

Short Stickelberger Class Relations and Application to Ideal-SVP

Benjamin Pierre Charles Wesolowski

The worst-case hardness of finding short vectors in ideals of cyclotomic number fields (Ideal-SVP) is a central matter in lattice based cryptography. Assuming the worst-case hardness of Ideal-SVP allows to prove the Ring-LWE and Ring-SIS assumptions, and t ...

Springer International Publishing Ag2017

LPN in Cryptography : an Algorithmic Study

Sonia Mihaela Bogos

The security of public-key cryptography relies on well-studied hard problems, problems for which we do not have efficient algorithms. Factorization and discrete logarithm are the two most known and used hard problems. Unfortunately, they can be easily solv ...

EPFL2017

Polynomially Solvable Instances of the Shortest and Closest Vector Problems With Applications to Compute-and-Forward

Michael Christoph Gastpar, Saeid Sahraei

A particular instance of the shortest vector problem (SVP) appears in the context of compute-and-forward. Despite the NP-hardness of the SVP, we will show that this certain instance can be solved in complexity order O(nψlog(nψ)) , where ψ=sqrt(P ||h||^2+1) ...

Institute of Electrical and Electronics Engineers2017

A variational investigation of the SU(N) Heisenberg model in antisymmetric irreducible representations

Jérôme Dufour

Motivated by recent experimental progress in the context of ultra-cold multi-colour fermionic atoms in optical lattices, this thesis investigates the properties of the antiferromagnetic SU(N) Heisenberg models with fully antisymmetric irreducible represent ...

EPFL2016

Improved hardness results for unique shortest vector problem

Divesh Aggarwal

The unique shortest vector problem on a rational lattice is the problem of finding the shortest non-zero vector under the promise that it is unique (up to multiplication by -1). We give several incremental improvements on the known hardness of the unique s ...

Elsevier2016

Better Algorithms for LWE and LWR

Serge Vaudenay, Alexandre Raphaël Duc, Florian Tramèr

The Learning With Error problem (LWE) is becoming more and more used in cryptography, for instance, in the design of some fully homomorphic encryption schemes. It is thus of primordial importance to find the best algorithms that might solve this problem so ...

Springer2015

A sieve algorithm based on overlattices

Anja Annemone Becker

In this paper, we present a heuristic algorithm for solving exact, as well as approximate, shortest vector and closest vector problems on lattices. The algorithm can be seen as a modified sieving algorithm for which the vectors of the intermediate sets lie ...

Cambridge Univ Press2014