### 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.

Available format(s)
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
lattice techniquesBounded Distance DecodingMinkowski's bound
Contact author(s)
cecile pierrot @ inria fr
History
Short URL
https://ia.cr/2018/146

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.