Paper 2021/1052

Comparing Lattice Families for Bounded Distance Decoding near Minkowski’s Bound.

Oleksandra Lapiha

Abstract

In this report we analyse and compare the complexity of solving the Bounded Distance Decoding problem in two families for discrete logarithm lattices. Our algorithm uses the internal structure of the lattice to decode an error close to Minkowski’s bound efficiently. This procedure can be used as a decryption algorithm of an encryption scheme, where the internal structure of the lattice serves as a secret key. In addition, one of these lattices was used in [1] to construct a family of one way functions. We present cryptanalysis of the mentioned scheme and we prove that the stated size of the keys is insufficient for a required security level.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Bounded Distance DecodingLattice-based CryptographyCryptanalysis.
Contact author(s)
sasha lapiga @ gmail com
History
2021-08-16: received
Short URL
https://ia.cr/2021/1052
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1052,
      author = {Oleksandra Lapiha},
      title = {Comparing Lattice Families for Bounded Distance Decoding near Minkowski’s Bound.},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1052},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1052}},
      url = {https://eprint.iacr.org/2021/1052}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.