Publication

Better Algorithms for LWE and LWR

Related publications (45)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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

A non-stationary stochastic ensemble generator for radar rainfall fields based on the short-space Fourier transform

Nikola Besic, Urs Martin Germann, Daniele Nerini

In this paper we present a non-stationary stochastic generator for radar rainfall fields based on the short-space Fourier transform (SSFT). The statistical properties of rainfall fields often exhibit significant spatial heterogeneity due to variability in ...

Copernicus GmbH2017

Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling

Divesh Aggarwal

We give a randomized 2^{n+o(n)}-time and space algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional Euclidean lattices. This improves on the previous fastest algorithm: the deterministic O(4^n)-time and O(2^n)-space algorithm of Miccian ...

ACM2015

Bringing Theory Closer to Practice in Post-quantum and Leakage-resilient Cryptography

Alexandre Raphaël Duc

Modern cryptography pushed forward the need of having provable security. Whereas ancient cryptography was only relying on heuristic assumptions and the secrecy of the designs, nowadays researchers try to make the security of schemes to rely on mathematical ...

EPFL2015

Adaptation and Awareness in Robot Ensembles: Scenarios and Algorithms

Francesco Mondada, Michael Bonani

This chapter presents a disaster recovery scenario that has been used throughout the ASCENS project as a reference to coordinate the study of distributed algorithms for robot ensembles. We first introduce the main traits and open problems in the design of ...

Springer2015

Centrality of trees for capacitated -center

Ola Nils Anders Svensson, Hyung Chan An, Aditya Bhaskara

We consider the capacitated -center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) locations (called centers) and assign each ...

Springer Heidelberg2015

A sensor is a device that detects or measures a physical property and records, indicates, or otherwise responds to it. In other words, a sensor allows us to interact with the surrounding environment, by measuring qualitatively or quantitatively a given phe ...

EPFL2014

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

, ,

We consider the capacitated k-center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) k locations (called centers) and assign e ...

Springer2014

Modified parallel code-phase search for acquisition in presence of sign transition

Pierre-André Farine, Cyril Botteron, Jérôme Leclère

One of the method to have a fast acquisition of GNSS signals is the parallel code-phase search, which uses the fast Fourier transform (FFT) to perform the correlation. A problem with this method is the potential sign transition that can happen between two ...

2013