Publications associées à Problème de réseau

Geometric Considerations in Lattice Programming

We provide faster algorithms and fine-grained reductions for lattice problems in general norms. ...

EPFL2023

A Gapless Post-quantum Hash Proof System in the Hamming Metric

A hash proof system (HPS) is a form of implicit proof of membership to a language. Out of the very few existing post-quantum HPS, most are based on languages of ciphertexts of code-based or lattice-based cryptosystems and inherently suffer from a gap cause ...

2023

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

A new method for lattice reduction using directional and hyperplanar shearing

Cyril Cayron

A geometric method of lattice reduction based on cycles of directional and hyperplanar shears is presented. The deviation from cubicity at each step of the reduction is evaluated by a parameter called 'basis rhombicity' which is the sum of the absolute val ...

INT UNION CRYSTALLOGRAPHY2022

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

Revisiting Multivariate Ring Learning with Errors and Its Applications on Lattice-Based Cryptography

Juan Ramón Troncoso-Pastoriza

The “Multivariate Ring Learning with Errors” problem was presented as a generalization of Ring Learning with Errors (RLWE), introducing efficiency improvements with respect to the RLWE counterpart thanks to its multivariate structure. Nevertheless, the rec ...

2021

Shortest-support multi-spline bases for generalized sampling

Michaël Unser, Alexis Marie Frederic Goujon, Shayan Aziznejad, Alireza Naderi

Generalized sampling consists in the recovery of a function f, from the samples of the responses of a collection of linear shift-invariant systems to the input f . The reconstructed function is typically a member of a finitely generated integer-shift invar ...

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, Subhadeep Banik, Hamid Nejatollahi

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

Matthias Schymura, Christoph Hunkenschröder

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

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

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

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

Avalanches in dry and saturated disordered media at fracture in shear and mixed mode scenarios

Jean-François Molinari, Enrico Milanese, Okan Yilmaz

We investigate shear and mixed mode fracture scenarios in inhomogeneous dry and fully saturated porous media with a 2D central force lattice model. For the fully saturated case we adopt the extended Biot's theory. The bars of the lattice break only under t ...

Elsevier2017

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

Multilevel Design Understanding: From Specification to Logic Invited Paper

Mathias Soeken

We present an outline of the field of Multilevel Design Understanding by first defining and motivating the related problems, and then describing the key issues which must be addressed in future research. ...

Assoc Computing Machinery2016

On lattice codes for Gaussian interference channels

Michael Christoph Gastpar, Jingge Zhu

The usefulness of lattice codes is investigated for two-user Gaussian interference channels (IC). A coding scheme based on the compute-and-forward technique is shown to achieve the capacity region of the Gaussian IC under strong interference. The proposed ...

2015

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

A Lattice Reduction-Aided MIMO Channel Equalizer in 90 nm CMOS Achieving 720 Mb/s

Andreas Peter Burg, Carl Christian Sten Dominic Senning

In this paper, a VLSI implementation of a complete MIMO channel equalization ASIC based on lattice reduction-aided linear detection is presented. The architecture performs preprocessing steps at channel rate and low-complexity linear data detection at symb ...

Ieee-Inst Electrical Electronics Engineers Inc2014

Compute-and-Forward: Finding the Best Equation

Michael Christoph Gastpar, Saeid Sahraei

Compute-and-Forward is an emerging technique to deal with interference. It allows the receiver to decode a suitably chosen integer linear combination of the transmitted messages. The integer coefficients should be adapted to the channel fading state. Optim ...

2014