A Digital Signature Scheme Based on NP-Complete Lattice Problems

Shunichi HAYASHI  Mitsuru TADA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A   No.5   pp.1253-1264
Publication Date: 2008/05/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.5.1253
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Cryptography and Information Security
NP-complete problem,  lattice,  identification scheme,  signature scheme,  

Full Text: PDF(220KB)>>
Buy this Article

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.