DIGITAL SIGNATURE SYSTEM, COMMUNICATION DEVICE, DIGITAL SIGNATURE METHOD, AND PROGRAM

摘要

PROBLEM TO BE SOLVED: To realize a one-time signature that is safe and capable of reducing signature length while restraining increase in size of a public key table and an amount of calculation required for verification of a signature.SOLUTION: A digital signature system comprises a first communication device including signature generation means for generating a signature to be added to a message, and a second communication device including signature verification means for verifying the signature added to the message. The signature generation means and the signature verification means divide each bit of a hush value obtained from the message into a first type bit used for a table index to determine entry of a secret key table and a public key table, and a second type bit used for a depth index to determine the number of repetitions of a unidirectional function, and use a secret key or a public key obtained from the secret key table or the public key table on the basis of the first bit and the number of repetitions of the unidirectional function determined based on the second type bit to generate or verify a signature.