Undeniable signature systems
First Claim
1. A cryptographic method for forming and checking undeniable signatures where the signatures are called "undeniable" because they can be verified in a protocol between a signing party and a checking party and the signing party is unable to conduct the protocol improperly so as to "deny" the validity of a valid undeniable signature previously issued by the signing party without such improper denial giving at least a probability with at least a known lower bound that the checking party will learn that the signing party has conducted the protocol improperly, the method comprising the steps of:
- forming an undeniable signature from an unsigned message by said signing party using a private key corresponding to a public key, and the resulting undeniable signature being issued to at least one party other than the signing party;
forming at least one challenge by a checking party using a challenge key known to said checking party, the challenge key being unknown to said signing party at least until a response by said signing party is committed to by the signing party, and the challenge at least partially depending on at least one member of a pair having a purported undeniable signature and said unsigned message, and supplying the at least one challenge to said signing party;
transforming at least one said challenge received by said signing party using knowledge of said private key and returning to said checking party the result of the transformation as said response; and
checking at least one said response received by said checking party using values at least depending on said challenge key, to give at least a probability having a known lower bound that the signing party is unable to prevent the checking party from distinguishing between three cases;
(a) that said purported undeniable signature is a valid undeniable signature corresponding both to said public key and to said unsigned message, (b) that the purported undeniable signature is not a valid undeniable signature corresponding both to the public key and to the unsigned message, and (c) that the response by the signing party is an improper response.
19 Assignments
0 Petitions
Accused Products
Abstract
Cryptographic methods and apparatus for forming, checking, blinding, and unblinding of undeniable signatures are disclosed. The validity of such signatures is based on public keys and they are formed by a signing party with access to a corresponding private key, much as with public key digital signatures. A difference is that whereas public key digital signatures can be checked by anyone using the corresponding public key, the validity of undeniable signatures is in general checked by a protocol conducted between a checking party and the signing party. During such a protocol, the signing party may improperly try to deny the validity of a valid signature, but the checking party will be able to detect this with substantially high probability. In case the signing party is not improperly performing the protocol, the checking party is further able to determine with high probability whether or not the signature validly corresponds to the intended message and public key. Blinding can be used while obtaining undeniable signatures, while providing them to other parties, and while checking their validity.
154 Citations
48 Claims
-
1. A cryptographic method for forming and checking undeniable signatures where the signatures are called "undeniable" because they can be verified in a protocol between a signing party and a checking party and the signing party is unable to conduct the protocol improperly so as to "deny" the validity of a valid undeniable signature previously issued by the signing party without such improper denial giving at least a probability with at least a known lower bound that the checking party will learn that the signing party has conducted the protocol improperly, the method comprising the steps of:
-
forming an undeniable signature from an unsigned message by said signing party using a private key corresponding to a public key, and the resulting undeniable signature being issued to at least one party other than the signing party; forming at least one challenge by a checking party using a challenge key known to said checking party, the challenge key being unknown to said signing party at least until a response by said signing party is committed to by the signing party, and the challenge at least partially depending on at least one member of a pair having a purported undeniable signature and said unsigned message, and supplying the at least one challenge to said signing party; transforming at least one said challenge received by said signing party using knowledge of said private key and returning to said checking party the result of the transformation as said response; and checking at least one said response received by said checking party using values at least depending on said challenge key, to give at least a probability having a known lower bound that the signing party is unable to prevent the checking party from distinguishing between three cases; (a) that said purported undeniable signature is a valid undeniable signature corresponding both to said public key and to said unsigned message, (b) that the purported undeniable signature is not a valid undeniable signature corresponding both to the public key and to the unsigned message, and (c) that the response by the signing party is an improper response. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 37, 38, 39, 40, 41, 42, 43, 46, 47, 48)
-
-
14. Cryptographic apparatus for forming and checking undeniable signatures where the signatures are called "undeniable" because they can be verified in a protocol between a signing party and a checking party and the signing party is unable to conduct the protocol improperly so as to "deny" the validity of a valid undeniable signature previously issued by the signing party without such improper denial giving at least a probability with at least a known lower bound that the checking party will learn that the signing party has conducted the protocol improperly, said apparatus comprising:
-
means for forming an undeniable signature from an unsigned message by said signing party using a private key corresponding to a public key, and the resulting undeniable signature being issued to at least on party other than the signing party; means for forming at least one challenge by a checking party using a challenge key known to said checking party, the challenge key being unknown to said signing party at least until a response by said signing party is committed to by the signing party, and the challenge at least partially depending on at least one member of a pair having a purported undeniable signature and said unsigned message, and supplying the at least one challenge to said signing party; means for transforming at least one said challenge received by said signing party using knowledge of said private key and returning to said checking party the result of the transformation as said response; and means for checking at least one said response received by said checking party using values at least depending on said challenge key, to give at least a probability having a known lower bound that the signing party is unable to prevent the checking party from distinguishing between three cases; (a) that said purported undeniable signature is a valid undeniable signature corresponding both to said public key and to said unsigned message, (b) that the purported undeniable signature is not a valid undeniable signature corresponding both to the public key and to the unsigned message, and (c) that the response by the signing party is an improper response. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)
-
-
31. A cryptographic method for forming and checking undeniable signatures where the signatures are called "undeniable" because they can be verified in a protocol between a signing party and a checking party and the signing party is unable to conduct the protocol improperly so as to "deny" the validity of a valid undeniable signature previously issued by the signing party without such improper denial giving at least a probability with at least a known lower bound that the checking party will detect that the signing party has conducted the protocol improperly, the method comprising the steps of:
-
forming at least one challenge by a checking party using a challenge key known to said checking party, the challenge key at least partially unknown to said signing party at least until a response by said signing party is substantially committed to by the signing party, and the challenge at least partially depending on at least one member of the triple consisting of a public key, an undeniable signature and an unsigned message, and supplying the at least one challenge to said signing party; transforming at least one said challenge received by said signing party using knowledge of a private key corresponding to said public key and returning to said checking party the result of the transformation as at least one said response; and checking said at least one response received by said checking party using predetermined values used by the checking party in forming said challenge, whereby the checking party can distinguish with a probability having a lower bound known at least to the checking party between at least two cases;
(a) the signature is invalid, and (b) the response from the signer is improperly formed. - View Dependent Claims (32, 33, 34, 35, 36, 44, 45)
-
Specification