Problème de réseau

Résumé

En informatique, les problèmes de réseau sont une classe de problèmes d'optimisation sur les réseaux. Conjecturé insoluble, ces problèmes sont au centre de la construction pour sécuriser les réseaux et à la base des crypto-systèmes. Pour des applications dans de tels systèmes cryptographiques, les grilles sur les espaces vectoriels (souvent \mathbb{Q}^n) ou de modules libres (souvent \mathbb{Z}^n) sont généralement considérés. Catégorie:Cryptographie Catégorie:Problème mathématique Catégorie:Cryptographie post-quantique

Source officielle

https://fr.wikipedia.org/wiki/Probl%C3%A8me_de_r%C3%A9seau

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (9)

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (6)

Concepts associés

Chargement

Cours associés (1)

This advanced course will provide students with the knowledge to tackle the design of privacy-preserving ICT systems. Students will learn about existing technologies to prect privacy, and how to evaluate the protection they provide.

Cours associés

Chargement

Séances de cours associées (2)

Séances de cours associées

Chargement

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 in overlattices or translated cosets of overlattices. The key idea is hence no longer to work with a single lattice but to move the problems around in a tower of related lattices. We initiate the algorithm by sampling very short vectors in an overlattice of the original lattice that admits a quasi-orthonormal basis and hence an efficient enumeration of vectors of bounded norm. Taking sums of vectors in the sample, we construct short vectors in the next lattice. Finally, we obtain solution vector(s) in the initial lattice as a sum of vectors of an overlattice. The complexity analysis relies on the Gaussian heuristic. This heuristic is backed by experiments in low and high dimensions that closely reflect these estimates when solving hard lattice problems in the average case. This new approach allows us to solve not only shortest vector problems, but also closest vector problems, in lattices of dimension n in time 2(0.3774n) using memory 2(0.2925n). Moreover, the algorithm is straightforward to parallelize on most computer architectures.

Cambridge Univ Press2014

Chargement

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 Micciancio and Voulgaris (STOC 2010, SIAM J. Comp. 2013). In fact, we give a conceptually simple algorithm that solves the (in our opinion, even more interesting) problem of discrete Gaussian sampling (DGS). More specifically, we show how to sample 2^(n/2) vectors from the discrete Gaussian distribution at any parameter in 2^(n+o(n)) time and space. (Prior work only solved DGS for very large parameters.) Our SVP result then follows from a natural reduction from SVP to DGS. We also show that our DGS algorithm implies a 2^(n+o(n))-time algorithm that approximates the Closest Vector Problem to within a factor of 1.97. In addition, we give a more refined algorithm for DGS above the so-called smoothing parameter of the lattice, which can generate 2^(n/2) discrete Gaussian samples in just 2^(n/2+o(n)) time and space. Among other things, this implies a 2^(n/2+o(n))-time and space algorithm for 1.93-approximate decision SVP.

ACM2015

Chargement

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 shortest vector problem (uSVP) using standard techniques. This includes a deterministic reduction from the shortest vector problem to the uSVP, the NP-hardness of uSVP on (1 + 1/poly(n))-unique lattices, and a proof that the decision version of uSVP defined by Cai [4] is in co-NP for n(1/4)-unique lattices. (C) 2016 Published by Elsevier B.V.

Elsevier2016

Chargement