Paper 2021/1052 Original: eprint.iacr.org/2021/1052 ↗
Comparing Lattice Families for Bounded Distance Decoding near Minkowski’s Bound.
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.
- History
- 2021-08-16: last updated
- 2021-08-16: published
- Short URL
- https://ia.cr/2021/1052
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}