A Digital Signature Scheme Based on NP-Complete Lattice Problems
S. HAYASHI, M. TADA · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2008
In [13], we proposed new decision problems related to lattices, and proved their NP-completeness. In this paper, we present a new public-key identification scheme and a digital signature scheme based on one of the problems in [13]. We also prove the security of our schemes under certain assumptions, and analyze the efficiency of ours.