Undeniable signature systems

Claim 2

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.

Claim 3

The method according to claim 1, wherein said signing party is unable with said probability having a known lower bound to prevent the checking party from distinguishing between said three cases because of the inability of the signing party to perform certain computations in a predetermined available time period.

Claim 4

The method according to claim 1, wherein said signing party is unable with said probability having a known lower bound to prevent said checking party from distinguishing between said three cases regardless of the computational resources available to the signing party.

Claim 5

The method according to claim 1, wherein said signing party develops said public key and corresponding private key from a substantially randomly chosen seed and the signing party issues the public key making it receivable to said checking party.

Claim 6

The method according to claim 1, wherein said signing party receives substantially said unsigned message from a providing party and the signing party returns said undeniable signature to the providing party.

Claim 7

The method according to claim 5, wherein said providing party supplies said undeniable signature to said checking party and the checking party is distinct from the providing party.

Claim 8

The method according to claim 3, wherein said signing step comprises raising said unsigned message to a signing power derived from said private key, such exponentiation being performed in a finite structure where the inverse of such exponents is unknown.

Claim 9

The method according to claim 1 further including the step of: creating a public key and a corresponding private key, and distributing them so that the private key is known to said signing party and the public key but not the private key is known to a checking party.

Claim 10

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 11

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 message, respectively, by said checking party in

Claim 12

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 13

The method according to claim 9, 10 or 11 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; said blinding step includes the operation of raising the message to be blinded to a power derived from said blinding key; and said unblinding step includes raising the message to be unblinded to a power that acts as an inverse operation to that of said blinding operation.

Claim 15

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.

Claim 16

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.

Claim 17

Apparatus according to claim 14, wherein said lower bound on said probability is known to be at least one half.

Claim 18

Apparatus according to claim 14, wherein said lower bound on said probability is known to be at least one minus a value that is super linear in the size of the challenge message.

Claim 19

Apparatus according to claim 14, wherein said known lower bound on said probability is at least one minus the number of substantially distinct possible challenges.

Claim 20

Apparatus according to claim 14, wherein said means for forming include 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 21

Apparatus according to claim 18, wherein: at least part of said challenge is formed responsive to at least two undeniable signatures by raising the signatures 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 that acts substantially as the 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 undeniable signatures to powers derived from said challenge key.

Claim 22

Apparatus according to claim 19, wherein at least one of said two unsigned messages is a fixed constant and at least one of said two undeniable signatures is at least a part of said public key.

Claim 23

Apparatus according to claim 14, wherein the means for forming, means for transforming, and means for checking perform computations over a group of prime order.

Claim 24

Apparatus according to claim 14, wherein said means for forming includes means for raising said unsigned message to a signing power derived from said private key, such exponentiation being performed in a finite structure where the inverse of such exponents is unknown.

Claim 25

Apparatus according to claims 14 or 22, wherein: at least part of said challenge is formed responsive to at least two unsigned messages by raising the two unsigned messages 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 signing power; and said checking is performed at least in part by raising at least part of said response to powers derived from said challenge key.

Claim 26

Apparatus according to claim 23, wherein at least one of said two unsigned messages is a public constant and at least one of said two undeniable signature is at least a part of said public key.

Claim 27

Apparatus according to claim 14, further including: means for 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 means for unblinding said undeniably signed message returned by said signing party responsive to said blinding key.

Claim 28

Apparatus according to claim 14, further including: means for blinding, responsive to a blinding key, said undeniably signed message and also 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 message, respectively, by said checking party in forming said challenge and in checking said response.

Claim 29

Apparatus according to claim 14, further including: 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 30

Apparatus according to claim 25 wherein: said means for forming 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 blinding means includes means for raising the message to be blinded to a power derived from said blinding key; and said unblinding means 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 31

Apparatus according to claim 25 wherein: said means for forming 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 blinding means includes means for forming a product of at least a first message which is raised to a blinding power 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 32

Apparatus according to claim 14 further 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.

Claim 33

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.

Claim 34

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.

Claim 35

A method according to claim 31 further including the step of: forming an undeniable signature from an unsigned message by said signing party using said private key corresponding to said public key, and the resulting undeniable signature being issued to at least one party other than the signing party.

Claim 36

The method according to claim 31, wherein said signing party is unable with said probability having a known lower bound to prevent the checking party from distinguishing between said two cases because of the inability of the signing party to perform certain computations in a predetermined available time period.

Claim 37

The method according to claim 31, wherein said signing party is unable with said probability having a known lower bound to prevent said checking party from distinguishing between said two cases regardless of the computational resources available to the signing party.

Claim 38

The method according to claim 32, wherein said signing party develops said public key and corresponding private key from a substantially randomly chosen seed and the signing party issues the public key making it receivable to at least said checking party.

Claim 39

The method according to claim 34, wherein said known lower bound on said probability is at least one minus the number of substantially distinct possible challenges.

Claim 41

The method according to claim 37, wherein said lower bound on said probability is known to be at least one minus a value that is more than linear in the size of the challenge message.

Claim 43

The method according to claim 39, wherein said raising to said secret signing power is performed in a finite group.

Claim 44

The method according to claim 40, wherein: at least part of said challenge is formed responsive to at least two undeniable signatures by raising the signatures 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 that acts substantially as the 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 undeniable signatures to powers derived from said challenge key.

Claim 45

The method according to claim 41, wherein at least one of said two unsigned messages is a fixed constant and at least one of said two undeniable signatures is at least a part of said public key.

Claim 47

The method according to claim 31, wherein said response is committed to by said signing party issuing to said checking party the image of said challenge under a substantially one-way function.

Claim 48

The method according to claim 44, wherein said substantially one-way function is substantially injective.

Claim 50

The method according to claim 46, wherein at least one of said two unsigned messages is a public constant and at least one of said two undeniable signatures is at least a part of said public key.

Claim 51

The method according to claim 1 or 31 including the steps of: issuing a public key digital signature by said signing party responsive to at least one said challenge and one said response; and checking said public key digital signature.