Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Bounded Distance Decoding, Lattice-based Cryptography, Cryptanalysis.

Date: received 13 Aug 2021

Contact author: sasha lapiga at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210816:131506 (All versions of this report)

Short URL: ia.cr/2021/1052


[ Cryptology ePrint archive ]