SIGNATURE GENERATION DEVICE AND SIGNATURE VERIFICATION DEVICE

摘要

A signature generation device (100) is provided with a storage unit (101) in which a polynomial expression of a public key and a secret key are stored, an input unit (102) which receives input of a document to be signed into, a random number generation unit (103) which generates one or more random numbers, a conversion equation generation unit (104) which generates one or more conversion equations, a first calculation unit (105) which calculates each solution associating each conversion equation and each random number with the secret key, a conversion unit (106) which converts the polynomial expression of the public key on the basis of each conversion equation and each random number, thereby obtaining each converted equation, a second calculation unit (107) which calculates a hash value from the document to be signed into and each converted equation, first and second creation units (108, 109) which create each partial data containing "conversion equation and random numbers" or "solution" corresponding to the bit value of the hash value, and a signature generation unit (110) which generates a digital signature containing the document to be signed into, each converted equation, and each partial data.