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

Oleksandra Lapiha

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 Decoding Lattice-based Cryptography Cryptanalysis.
Contact author(s): sasha lapiga @ gmail com
History: 2021-08-16: received
Short URL: https://ia.cr/2021/1052
License: 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},
      url = {https://eprint.iacr.org/2021/1052}
}