Copyright © 2008 The Institute of Electronics, Information and Communication Engineers
Regular Section -- Papers -- Cryptography and Information Security |
A Digital Signature Scheme Based on NP-Complete Lattice Problems
1 The author is with the Graduate School of Science and Technology, Chiba University, Chiba-shi, 263-8522 Japan. E-mail: shunichihayashi{at}graduate.chiba-u.jp, 2 The author is with the Institute of Media and Information Technology, Chiba University, Chiba-shi, 263-8522 Japan. E-mail: m.tada{at}faculty.chiba-u.jp
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.
Key Words: NP-complete problem, lattice, identification scheme, signature scheme
Manuscript received January 4, 2007. Manuscript revised November 12, 2007.
References
[1] M. Ajtai, "The shortest vector problem in L2 is NP-hard for randomized reductions," Proc. STOC'98, ACM, 1998. [2] M. Bellare and P. Rogaway, "Random oracles are practical: A paradigm for designing efficient protocols," Proc. ACM CCS'93, ACM, 1993. [3] M. Bellare and P. Rogaway, "The exact security of digital signatures — How to sign with RSA and Rabin," Proc. EUROCRYPT'96, LNCS 1070, Springer, 1996. [4] J. Buchmann, A. May, and U. Vollmer, "Perspectives for cryptographic long-term security," Commun. ACM, vol.49, no.9, pp.50–55, 2006. [5] J.Y. Cai and A. Nerurkar, "Approximating the SVP to within a factor (1 + 1/dim [6] R. Cramer and V. Shoup, "Signature schemes based on the strong RSA assumption," ACM Trans. Inform. Syst. Security, vol.3, no.3, pp.161–185, 2000. [7] U. Feige and A. Shamir, "Witness indistinguishable and witness hiding protocols," Proc. STOC'90, ACM, 1990. [8] A. Fiat and A. Shamir, "How to prove yourself: Practical solutions to identification and signature problems," Proc. CRYPTO'86, LNCS 263, Springer, 1987. [9] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979. [10] O. Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, 2001. [11] O. Goldreich and S. Goldwasser, "On the limits of nonapproximability of lattice problems," J. Comput. Syst. Sci., vol.60, no.3, pp.540–563, 2000. [12] O. Goldreich, S. Goldwasser, and S. Halevi, "Public-key cryptosystems from lattice reduction problems," Proc. CRYPTO'97, LNCS 1294, Springer, 1997. [13] S. Hayashi and M. Tada, "New NP-complete problems associated with lattices," IEICE Trans. Fundamentals, vol.E90-A, no.5, pp.941–948, May 2007. [14] J. Hoffstein, N. Howgrave-Graham, J. Pipher, J.H. Silverman, and W. Whyte, "NTRUSign: Digital signatures using the NTRU lattice," Proc. CT-RSA 2003, LNCS 2612, Springer, 2003. [15] J. Hoffstein, J. Pipher, and J.H. Silverman, "NTRU: A ring-based public key cryptosystem," Proc. ANTS-III, LNCS 1423, Springer, 1998. [16] D. Micciancio, "The shortest vector in a lattice is hard to approximate to within some constant," SIAM J. Comput., vol.30, no.6, pp.2008–2035, 2001. [17] D. Micciancio and S. Goldwasser, Complexity of Lattice Problems: A Cryptographic Perspective, Kluwer Academic Publishers, 2002. [18] D. Micciancio and S. Vadhan, "Statistical zero-knowledge proofs with efficient provers: Lattice problems and more," Proc. CRYPTO 2003, LNCS 2729, Springer, 2003. [19] NIST, "Secure hash standard," Federal Information Processing Standards Publications, 2002. [20] NIST, "Digital signature standard," Federal Information Processing Standards Publications, 2000. [21] K. Ohta and T. Okamoto, "On concrete security treatment of signatures derived from identification," Proc. CRYPTO'98, LNCS 1462, Springer, 1998. [22] T. Okamoto, "Provably secure and practical identification schemes and corresponding signature schemes," Proc. CRYPTO'92, LNCS 740, Springer, 1993. [23] T. Okamoto, K. Tanaka, and S. Uchiyama, "Quantum public-key cryptosystems," Proc. CRYPTO 2000, LNCS 1880, Springer, 2000. [24] T. Okamoto and H. Yamamoto, Modern Cryptography, Sangyo-Tosho, 1997. [25] D. Pointcheval and G. Poupard, "A new NP-complete problem and public-key identification," Des. Codes Cryptogr., vol.28, pp.5–31, 2003. [26] G. Poupard and J. Stern, "Security analysis of a practical "on the fly" authentication and signature generation," Proc. EUROCRYPT'98, LNCS 1403, Springer, 1998. [27] G. Poupard and J. Stern, "On the fly signatures based on factoring," Proc. ACM CCS'99, ACM, 1999. [28] C.P. Schnorr, "Efficient signature generation by smart cards," J. Cryptol., vol.4, pp.161–174, 1991. [29] A. Shamir, "An efficient identification scheme based on permuted kernels (extended abstract)," Proc. CRYPTO'89, LNCS 435, Springer, 1990. [30] P.W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer," SIAM J. Comput., vol.26, pp.1484–1509, 1997. [31] J. Stern, "Designing identification schemes with keys of short size," Proc. CRYPTO'94, LNCS 839, Springer, 1994. [32] J. Stern, "A new paradigm for public key identification," IEEE Trans. Inf. Theory, vol.42, no.6, pp.1757–1768, 1996. [33] P. van Emde Boas, "Another NP-complete partition problem and the complexity of computing short vectors in a lattice," Technical Report 81-04, University of Amsterdam, 1981.
) is NP-hard under randomized reductions," J. Comput. Syst. Sci., vol.59, pp.221–239, 1999.
CiteULike 
Connotea 
Del.icio.us What's this?
This Article 
Abstract
Full Text (PDF)
Alert me when this article is cited
Alert me if a correction is posted
Services
Email this article to a friend
Similar articles in this journal
Alert me to new issues of the journal
Add to My Personal Archive
Download to citation manager
Request Permissions
Google Scholar
Articles by HAYASHI, S.
Articles by TADA, M.
Social Bookmarking
What's this?