Efficient Unconditionally Secure Digital Signatures

Goichiro HANAOKA  Junji SHIKATA  Yuliang ZHENG  Hideki IMAI 

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  Vol.E87-A  No.1  pp.120-130
Publication Date: 2004/01/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Asymmetric Cipher
Keyword: 
digital signature,  unconditional security, 

Full Text: PDF(323.6KB)

Summary: 
Digital signatures whose security does not rely on any unproven computational assumption have recently received considerable attention. While these unconditionally secure digital signatures provide a foundation for long term integrity and non-repudiation of data, currently known schemes generally require a far greater amount of memory space for the storage of secret and public keys than a traditional digital signature. The focus of this paper is on methods for reducing memory requirements of unconditionally secure digital signatures. A major contribution of this paper is to propose two novel unconditionally secure digital signature schemes, one called a symmetric construction and other an asymmetric construction, which require a significantly smaller amount of memory. As a specific example, with a typical parameter setting the required memory size for a user is reduced to be approximately of that in a previously known scheme. Another contribution of the paper is to show an attack on a multireceiver authentication code which was proposed by Safavi-Naini and Wang. A simple method to fix the problem of the multireceiver authentication code is also proposed.