Undeniable signature systems

Claim 2

A cryptographic method for forming and checking undeniable signatures based on the issuance of a public key by a signing party where the signatures are called "undeniable" because they can be verified in a protocol between a checking party and the signing party in which the signing party is unable to conduct the protocol improperly so as to "deny" the validity of a valid signature without there being at least a substantially high probability that the verifying party will learn that the signing party is conducting the protocol improperly, the method comprising the steps of: creating a public key and a corresponding private key by a signing party and providing the public key to at least a checking party; supplying an unsigned message by a provider party to said signing party; forming an undeniable signature on said unsigned message received by said signing party, at least responsive to said private key corresponding to said public key, and returning the resulting undeniably signed message to said provider party; forming at least one challenge, by a checking party, responsive to a challenge key substantially at least temporarily unknown to said signing party and responsive to at least one member of the pair comprising said undeniably signed message and said unsigned message, and supplying said challenge to said signing party; transforming at least one said challenge received by said signing party at least partially responsive to said private key and returning the result as a response to said checking party; and checking at least one said response received by said checking party responsive both to said challenge key and to at least the other member of said pair comprising said undeniably signed message and said unsigned message, so as to give substantially high certainty in distinguishing between the three cases (a) that the purported undeniably signed message is a valid undeniable signature corresponding both to said public key and to said unsigned message, (b) that the purported undeniably signed message is not a valid undeniable signature corresponding both to said public key and to said unsigned message, and (c) that the response by the signing party is an improper response.

Claim 3

The method of claim 1, wherein said signing step includes raising said unsigned message to a secret signing power derived from said private key, such exponentiation being performed in a finite structure where it is defined.

Claim 4

the method of claim 2, wherein: at least part of said challenge is formed responsive to at least two undeniably signed messages by raising them to powers derived from said challenge key; at least part of said response is formed by raising at least part of said challenge to a power acting as an inverse of said secret signing power; and said checking is performed at least in part by raising the at least two unsigned messages corresponding to said at least two undeniably signed messages to powers derived from said challenge key.

Claim 5

The method of claim 2, wherein: at least part of said challenge is formed responsive to at least two unsigned messages by raising them to powers derived from said challenge key; at least part of said response is formed by raising at least part of said challenge to said secret signing power; and said checking is performed at least in part by raising the at least two undeniably signed messages corresponding to said at least two unsigned messages to powers derived from said secret challenge key.

Claim 6

The method as in claim 1, further comprising the steps of: blinding said unsigned message responsive to a blinding key before providing the resulting blinded unsigned message to said signing party in place of said unsigned message; and unblinding said undeniably signed message returned by said signing party responsive to said blinding key.

Claim 7

The method as in claim 1, further comprising the steps of: blinding, responsive to a blinding key, said undeniably signed message and also said corresponding unsigned message; and using said blinded undeniably signed and said blinded unsigned messages in place of said undeniably signed and said unsigned messages, respectively, by said checking party in forming said challenge and in checking said response.

Claim 8

The method as in claim 1, further comprising the steps of: blinding, responsive to a blinding key, at least part of one of said challenge and said response; and unblinding, responsive to said blinding key, at least part of the other one of said challenge and said response.

Claim 12

Apparatus for forming and checking undeniable signatures based on the issuance of a public key by a signing party where the signatures are called "undeniable" because they can be verified by means for forming and transferring messages between a checking party and the signing party in which the signing party is unable to conduct the transfers improperly so as to "deny" the validity of a valid signature without there being at least a substantially high probability that the verifying party will detect that the signing party is conducting the protocol improperly, the apparatus comprising: means for creating a public key and a corresponding private key by a signing party and for providing the public key to at least a checking party; means for supplying an unsigned message by a provider party to said signing party; means for forming an undeniable signature on said unsigned message received by said signing party, at least responsive to said private key corresponding to said public key, and for returning the resulting undeniably signed message to said provider party; means for forming at least one challenge, by a checking party, responsive to a challenge key substantially at least temporarily unknown to said signing party and responsive to at least one member of the pair comprising said undeniably signed message and said unsigned message, and for supplying said challenge to said signing party; means for transforming at least one said challenge received by said signing party at least partially responsive to said private key and for returning the result as a response to said checking party; and means for checking at least one said response received by said checking party responsive both to said challenge key and to at least the other member of said pair comprising said undeniably signed message and said unsigned message, so as to give substantially high certainty in distinguishing between the three cases (a) that the purported undeniably signed message is a valid undeniable signature corresponding both to said public key and to said unsigned message, (b) that the purported undeniably signed message is not a valid undeniable signature corresponding both to said public key and to said unsigned message, and (c) that the response by the signing party is an improper response.

Claim 13

Apparatus for forming and checking undeniable signatures based on the issuance of a public key by a signing party where the signatures are called "undeniable" because they can be verified by means for forming and transferring messages between a checking party and the signing party in which the signing party is unable to conduct the transfers improperly so as to "deny" the validity of a valid signature without there being at least a substantially high probability that the verifying party will detect that the signing party is conducting the protocol improperly, the apparatus comprising: means for creating a public key and a corresponding private key by a signing party and for providing the public key to at least a checking party; means for supplying an unsigned message by a provider party to said signing party; means for forming an undeniable signature on said unsigned message received by said signing party, at least responsive to said private key corresponding to said public key, and for returning the resulting undeniably signed message to said provider party; means for forming at least one challenge, by a checking party, responsive to a challenge key substantially at least temporarily unknown to said signing party and responsive to at least one member of the pair comprising said undeniably signed message and said unsigned message, and for supplying said challenge to said signing party; means for transforming at least one said challenge received by said signing party at least partially responsive to said private key and for returning the result as a response to said checking party; and means for checking at least one said response received by said checking party responsive both to said challenge key and to at least the other member of said pair comprising said undeniably signed message and said unsigned message, so as to give substantially high certainty in distinguishing between the three cases (a) that the purported undeniably signed message is a valid undeniable signature corresponding both to said public key and to said unsigned message, (b) that the purported undeniably signed message is not a valid undeniable signature corresponding both to said public key and to said unsigned message, and (c) that the response by the signing party is an improper response.

Claim 14

Apparatus as in claim 11, wherein said signing means includes means for raising said unsigned message to a secret signing power derived from said private key, such exponentiation being performed in a finite structure where it is defined.

Claim 15

Apparatus as in claim 12, wherein: at least part of said challenge is formed responsive to at least two undeniably signed messages by means for raising them to powers derived from said challenge key; at least part of said response is formed by means for raising at least part of said challenge to a power acting as an inverse of said secret signing power; and said checking is performed at least in part by means for raising the at least two unsigned messages corresponding to said at least two undeniably signed messages to powers derived from said challenge key.

Claim 16

Apparatus as in claim 12, wherein: at least part of said challenge is formed responsive to at least two unsigned messages by means for raising them to powers derived from said challenge key; at least part of said response is formed by means for raising at least part of said challenge to said secret signing power; and said means for checking includes at least means for raising the at least two undeniably signed messages corresponding to said at least two unsigned messages to powers derived from said secret challenge key.

Claim 17

Apparatus as in claim 11, further comprising: means for blinding said unsigned message responsive to a blinding key before the resulting blinded unsigned message is provided to said signing party in place of said unsigned message; and means for unblinding said undeniably signed message returned by said signing party responsive to said blinding key.

Claim 18

Apparatus as in claim 11, further comprising: means for blinding, responsive to a blinding key, said undeniably signed message and also for blinding said corresponding unsigned message; and means for using said blinded undeniably signed and said blinded unsigned messages in place of said undeniably signed and said unsigned messages, respectively, by said checking party in said means for forming said challenge and for checking said response.

Claim 19

Apparatus as in claim 11, further comprising: means for blinding, responsive to a blinding key, at least part of one of said challenge and said response; and means for unblinding, responsive to said blinding key, at least part of the other one of said challenge and said response.

Claim 20

Apparatus as in claims 15, 16, or 17 wherein: said means for signing includes means for raising said unsigned message to a secret signing power derived from said private key, such exponentiation being performed in a finite structure where it is defined; said means for blinding includes means for raising the message to be blinded to a power derived from said blinding key; and said means for unblinding includes means for raising the message to be unblinded to a power that acts as an inverse operation to that of said blinding operation.

Claim 21

Apparatus as in claims 15, 16, or 17 wherein: said means for signing includes means for raising said unsigned message to a secret signing power derived from said private key, such exponentiation being performed in a finite structure where it is defined; said means for blinding includes means for forming a product of at least a first message raised to a blinding power that is derived from said blinding key times at least a second message to be blinded; and said unblinding means includes means for forming a product of the multiplicative inverse of the undeniably signed form of said first message raised to the blinding power times said second message.

Claim 22

Apparatus as in claims 11, 12, 13, or 14 including: means for issuing a public key digital signature by said signing party responsive to at least one said challenge and one said response; and means for checking said public key digital signature.