Cryptology ePrint Archive: Report 2017/1002

On the Closest Vector Problem for Lattices Constructed from Polynomials and Their Cryptographic Applications

Zhe Li and San Ling and Chaoping Xing and Sze Ling Yeo

Abstract: In this paper, we propose new classes of trapdoor functions to solve the bounded distance decoding problem in lattices. Specifically, we construct lattices based on properties of polynomials for which the bounded distance decoding problem is hard to solve unless some trapdoor information is revealed. We thoroughly analyze the security of our proposed functions using state-of-the-art attacks and results on lattice reductions. Finally, we describe how our functions can be used to design quantum-safe encryption schemes with reasonable public key sizes. Our encryption schemes are efficient with respect to key generation, encryption and decryption.

Category / Keywords: trapdoor function, CVP, lattice, polynomial

Date: received 5 Oct 2017, last revised 26 Jul 2021

Contact author: lzonline01 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210726:095244 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]