PROBLEM TO BE SOLVED: To provide a safe tagged disposable signature scheme in a short time based on an existing partial disposable signature scheme.SOLUTION: A tag key generation device 2 generates a tag tag=(opk,Enc(epk,osk)) by generating a disposable verification key opk and a disposable secret key osk on the basis of a disposable key generation algorithm of a partial disposable signature scheme, and generating ciphertext Enc(epk,osk) by encrypting the generated disposable secret key osk using a public key epk. A signature device 3 generates the disposable secret key osk by decoding a ciphertext Enc(epk,osk) included in the tag tag=(opk,Enc(epk,osk)) using a secret key esk, and generates a signature &sgr; for a message M on the basis of the signature algorithm of the partial disposable signature scheme using the generated disposable secret key osk.
展开▼