Paper 2018/146

Polynomial Time Bounded Distance Decoding near Minkowski’s Bound in Discrete Logarithm Lattices

Léo Ducas and Cécile Pierrot

Abstract

We propose a concrete family of dense lattices of arbitrary dimension n in which the lattice Bounded Distance Decoding (BDD) problem can be solved in deterministic polynomial time. This construction is directly adapted from the Chor-Rivest cryptosystem (1988). The lattice construction needs discrete logarithm computations that can be made in deterministic polynomial time for well-chosen parameters. Each lattice comes with a deterministic polynomial time decoding algorithm able to decode up to large radius. Namely, we reach decoding radius within O(log n) Minkowski’s bound, for both l1 and l2 norms.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
lattice techniquesBounded Distance DecodingMinkowski's bound
Contact author(s)
cecile pierrot @ inria fr
History
2018-02-08: received
Short URL
https://ia.cr/2018/146
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/146,
      author = {Léo Ducas and Cécile Pierrot},
      title = {Polynomial Time Bounded Distance Decoding near Minkowski’s Bound in Discrete Logarithm Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2018/146},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/146}},
      url = {https://eprint.iacr.org/2018/146}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.