Blind signature systems

Claim 3

A method as in claim 1 wherein, for substantially any at least two of said original messages, there exist at least two possible choices of said corresponding first keys that would produce the same said first messages and where the different choices would produce different correspondences between the original messages and the first messages.

Claim 4

A method as in claim 1 wherein there is a probability distribution for independently choosing said first keys so that it is substantially impossible for said signer party to learn substantially anything about which of said first messages corresponds with which of the second messages based upon (a) the first messages corresponding to at least two such keys, (b) the third messages corresponding to the at least two keys, and (c) said signer party's secret signing key, all taken together.

Claim 5

A method as in claim 3 wherein said first keys are substantially independently chosen from substantially said probability distribution.

Claim 6

A method as in claim 1, 2, 3 or 4 further comprising the step of transferring at least one of said first messages from the corresponding said supplier party to said signer party.

Claim 7

A method as in claim 1, 2, 3 or 4 further comprising the step of transferring at least one of said second message from said signer party back to the corresponding said supplier party.

Claim 10

A method as in claim 7 wherein, for substantially any at least two of said original messages, there exists at least two possible choices for said corresponding first keys that would produce the same said first messages and where the different choices would produce different correspondences between the original messages and the first messages.

Claim 11

A method as in claim 7 wherein there is a probability distribution for independent choice of said first keys so that substantially all pairs of individual said first messages and individual said third messages are substantially equally likely to correspond, thereby providing substantially complete unlinkability.

Claim 12

A method as in claim 9 wherein said first keys are chosen substantially independently from substantially said probability distribution and used in said blinding and unblinding steps.

Claim 13

A method as in claim 1, 2, 3, 4, 7, 8, 9 or 10 further comprising the step of checking the public key digital signature property of at least one of said third messages.

Claim 14

A method as in claim 11 further comprising the step of transferring a said third message to a party for performing said checking.

Claim 15

A method as in claim 11 further comprising the steps of: retaining a record responsive to valid said third messages checked; and searching said record to determine when the same said third message has been recorded previously.

Claim 18

A method as in claim 1, 2, 3, 4, 7, 8, 9, 10 or 14 wherein: said blinding step includes forming a product of at least one of said original messages and a blinding factor derived from a corresponding one of said first keys; and said unblinding step includes forming a product of the corresponding said second message with a multiplicative inverse of a signed form of said first key, in a finite structure where such multiplication and multiplicative inverses are defined.

Claim 19

A method as in claim 15 further comprising the step of checking the public key digital signature property of at least one of said third messages.

Claim 20

A method as described in claim 15 wherein: said blinding step transforms original messages m i using first keys k i to produce first messages t i described by t.sub.i =m.sub.i ·k.sub.i.sup.e (mod n) where is is a public signing exponent, and n is a public key digital signature modulus; said signing step transforms said first messages t i using secret signing key d to produce second messages t' i described by t'.sub.i =t.sub.i.sup.d (mod n); and said unblinding step transforms said second messages t' i using first keys k i to produce said third messages m' i described by m'.sub.i =m.sub.i.sup.d (mod n).

Claim 21

A method as in claim 17 further comprising the step of checking the public key digital signature property of at least one of said third messages m' i including exponentiation to the power e.

Claim 24

Apparatus for processing a plurality of original digital messages by plural provider parties before they are transformed with public key digital signatures by a signer party and for processing the resulting digital messages by the corresponding provider parties after they have been transformed with the public key digital signatures where said processed digital messages are considered to be "blinded" and said resulting digital messages to be "unblinded" because, although the public key digital signatures of said resulting digital messages are checkable using a public key, the signer is unable to determine the correspondence between elements of said processed digital message set and elements of the corresponding said resulting digital message set, said apparatus for processing comprising: means for blinding a plurality of original digital messages by a plurality of corresponding supplier parties transforming each such message at least partially responsive to a corresponding first key to produce corresponding digital first messages; means for signing each of said first messages by a signing party applying a public key digital signature thereto to produce a corresponding plurality of digital second messages; means for unblinding said plurality of second messages by said supplier parties transforming each at least partially responsive to said first keys to produce a corresponding plurality of digital third messages which retain a public key digital signature property related to said original messages and to said means for signing; and said means for blinding by said supplier parties including means for using said first keys so as to make said signer party without the corresponding first keys unable to readily determine the corresponding between individual messages within said plurality of third messages and individual messages within said plurality of first messages.

Claim 25

Apparatus for processing a plurality of original digital messages by plural provider parties before they are transformed with public key digital signatures by a signer party and for processing the resulting digital messages by the corresponding provider parties after they have been transformed with the public key digital signatures where said processed digital messages are considered to be "blinded" and said resulting digital messages to be "unblinded" because, although the public key digital signatures of said resulting digital messages are checkable using a public key, the signer is unable to determine the correspondence between elements of said processed digital message set and elements of the corresponding said resulting digital message set, said apparatus for processing comprising: means for blinding a plurality of original digital messages by a plurality of corresponding supplier parties transforming each such message at least partially responsive to a corresponding first key to produce corresponding digital first messages; means for signing each of said first messages by a signing party applying a public key digital signature thereto to produce a corresponding plurality of digital second messages; means for unblinding said plurality of second messages by said supplier parties transforming each at least partially responsive to said first keys to produce a corresponding plurality of digital third messages which retain a public key digital signature property related to said original messages and to said means for signing; and said means for blinding by said supplier parties including means for using said first keys so as to make said signer party without the corresponding first keys unable to readily determine the corresponding between individual messages within said plurality of third messages and individual messages within said plurality of first messages.

Claim 26

Apparatus as in claim 20 wherein said means for blinding operates so that, for substantially any at least two of said original messages, there exist at least two possible choices of said corresponding first keys that would produce the same said first messages and where the different choices would produce different correspondences between the original messages and the first messages.

Claim 27

Apparatus as in claim 20 wherein said means for blinding operates such that there is a probability distribution for independently choosing said first keys so that it is substantially impossible for said signer party to learn substantially anything about which of said first messages corresponds with which of the second messages based upon (a) the first messages corresponding to at least two such keys, (b) the third messages corresponding to the at least two keys, and (c) said signer party's secret signing key, all taken together.

Claim 28

Apparatus as in claim 22 wherein said means for blinding includes means for substantially independently providing said first keys from substantially said probability distribution.

Claim 29

Apparatus as in claim 22, 21, 22 or 23 further comprising means for transferring at least one of said first messages from the corresponding said supplier party to said signer party.

Claim 30

Apparatus as in claim 22, 21, 22 or 23 further comprising means for transferring at least one of said second messages from said signer party back to the corresponding said supplier party.

Claim 31

Apparatus for processing a plurality of original digital messages before they receive public key digital signatures and for processing the resulting messages after they have received the public key digital signatures where said processed digital messages are considered to be "blinded" and said resulting digital messages to be "unblinded" because, although the public key digital signatures of said resulting digital messages are checkable using a public key, even possession of the public key and of the corresponding secret signing key does not readily allow the correspondence between the elements of said processed digital message set and the elements of the corresponding said resulting digital message set to be determined, said apparatus for processing comprising: means for blinding a plurality of original digital messages by transforming each responsive to a corresponding first key to produce corresponding digital first messages; means for signing each of said first messages by applying a public key digital signature thereto, using at least a secret signing key to produce a corresponding plurality of signed digital second messages; means for unblinding said plurality of signed second messages by transforming each, at least partially responsive to said first keys, to produce a corresponding plurality of signed digital third messages related to said original messages and where the digital signature property derives from said secret signing key; and said means for blinding using said first keys so as to make substantially computationally infeasible substantial linking, even using said secret signing key, of individual messages within said plurality of third messages to individual messages within said plurality of first messages.

Claim 32

Apparatus for processing a plurality of original digital messages before they receive public key digital signatures and for processing the resulting messages after they have received the public key digital signatures where said processed digital messages are considered to be "blinded" and said resulting digital messages to be "unblinded" because, although the public key digital signatures of said resulting digital messages are checkable using a public key, even possession of the public key and of the corresponding secret signing key does not readily allow the correspondence between the elements of said processed digital message set and the elements of the corresponding said resulting digital message set to be determined, said apparatus for processing comprising: means for blinding a plurality of original digital messages by transforming each responsive to a corresponding first key to produce corresponding digital first messages; means for signing each of said first messages by applying a public key digital signature thereto, using at least a secret signing key to produce a corresponding plurality of signed digital second messages; means for unblinding said plurality of signed second messages by transforming each, at least partially responsive to said first keys, to produce a corresponding plurality of signed digital third messages related to said original messages and where the digital signature property derives from said secret signing key; and said means for blinding using said first keys so as to make substantially computationally infeasible substantial linking, even using said secret signing key, of individual messages within said plurality of third messages to individual messages within said plurality of first messages.

Claim 33

Apparatus as in claim 26 wherein said means for blinding operates so that, for substantially any at least two of said original messages, there exists at least two possible choices for said corresponding first keys that would produce the same said first messages and where the different choices would produce different correspondences between the original messages and the first messages.

Claim 34

Apparatus as in claim 26 wherein said means for blinding operates so that there is a probability distribution for independent choice of said first keys so that substantially all pairs of individual said first messages and individual said third messages are substantially equally likely to correspond, thereby providing substantially complete unlinkability.

Claim 35

Apparatus as in claim 28 wherein said means for blinding uses first keys substantially independently chosen substantially from said probability distribution.

Claim 36

Apparatus as in claim 20, 21, 22, 23, 26, 27, 28 or 29 further comprising means for time delaying messages disposed in a communication path to said means for unblinding.

Claim 37

Apparatus as in claim 20, 21, 22, 23, 26, 27, 28 or 29 further comprising means for checking the public key digital signature property of at least one of said third messages.

Claim 38

Apparatus as in claim 31 further comprising means for transferring a said third message to a party for performing said checking.

Claim 39

Apparatus in claim 32 wherein said means for transferring a third message includes means for time delaying such messages.

Claim 40

Apparatus as in claim 31 further comprising: means for retaining a record responsive to valid said third messages checked; and means for searching said record to determine when the same said third message has been recorded previously.

Claim 41

Apparatus for providing untraceability of value transfers by processing a plurality of original digital messages before they receive public key digital signatures and processing the resulting digital messages after they have received the public key digital signatures where said processed digital messages are considered to be "blinded" and said resulting digital messages to be "unblinded" because although the public key digital signatures of said resulting digital messages are checkable using a public key, even possesssion of that public key and of the corresponding secret signing key is substantially insufficient to substantially feasibly determine the correspondence between the elements of said processed digital message set and the elements of the corresponding said resulting digital message set, said apparatus for processing comprising: means for blinding by transforming at least part of each of a plurality of original digital messages responsive to first keys to produce corresponding blinded first digital messages, by each of plural supplier parties; means for receiving said first messages, by a signer party, and the signer party transforming at least two of said first messages, at least partially responsive to signing secret key information of said signer party, to produce second digital messages; means for providing the corresponding said second messages to at least two corresponding said supplier parties in exchange for a transfer of value from such corresponding supplier parties; means for receiving corresponding said second messages by said supplier parties and transforming the corresponding second messages with said first keys to produce corresponding unblinded third digital messages each having a digital signature property related to a corresponding one of said original messages thereby making it infeasible for the signer party to link said first messages with the third messages, without the first keys; means for receiving at least one of said third messages by a checker party and the checker party checking a public key digital signature property related to the corresponding said original messages; and means for maintaining a record depending on said previously checked third messages and preventing a signature related to the same such third messages from being accepted more than once, and for providing value in exchange for said signatures accepted.

Claim 42

Apparatus for providing untraceability of value transfers by processing a plurality of original digital messages before they receive public key digital signatures and processing the resulting digital messages after they have received the public key digital signatures where said processed digital messages are considered to be "blinded" and said resulting digital messages to be "unblinded" because although the public key digital signatures of said resulting digital messages are checkable using a public key, even possesssion of that public key and of the corresponding secret signing key is substantially insufficient to substantially feasibly determine the correspondence between the elements of said processed digital message set and the elements of the corresponding said resulting digital message set, said apparatus for processing comprising: means for blinding by transforming at least part of each of a plurality of original digital messages responsive to first keys to produce corresponding blinded first digital messages, by each of plural supplier parties; means for receiving said first messages, by a signer party, and the signer party transforming at least two of said first messages, at least partially responsive to signing secret key information of said signer party, to produce second digital messages; means for providing the corresponding said second messages to at least two corresponding said supplier parties in exchange for a transfer of value from such corresponding supplier parties; means for receiving corresponding said second messages by said supplier parties and transforming the corresponding second messages with said first keys to produce corresponding unblinded third digital messages each having a digital signature property related to a corresponding one of said original messages thereby making it infeasible for the signer party to link said first messages with the third messages, without the first keys; means for receiving at least one of said third messages by a checker party and the checker party checking a public key digital signature property related to the corresponding said original messages; and means for maintaining a record depending on said previously checked third messages and preventing a signature related to the same such third messages from being accepted more than once, and for providing value in exchange for said signatures accepted.

Claim 43

Apparatus as in claim 35 further comprising means for introducing time delay between reception of said second messages and the sending of said third messages.

Claim 44

Apparatus as in claim 20, 21, 22, 23, 26, 29, 28, 29 or 35 wherein: said means for blinding includes means for forming a product of at least one of said original message and a blinding factor derived from a corresponding one of said first keys; and said means for unblinding includes means for forming a product of the corresponding said second message with a multiplicative inverse of a signed form of said first key, in a finite structure where such multiplication and multiplicative inverses are defined.

Claim 45

Apparatus as in claim 37 further comprising means for checking the public key digital signature property of at least one of said third messages.

Claim 46

Apparatus as described in claim 37 wherein: said means for blinding transforms original messages m i using first keys k i to produce first messages t i described by t.sub.i =m.sub.i ·k.sub.i.sup.e (mod n), where e is a public signing exponent, and n is a public key digital signature modulus; said means for signing transforms said first messages t i using secret signing key d to produce second messages t' i described by t'.sub.i =t.sub.i.sup.d (mod n); and said means for unblinding transforms said second messages t' i using first keys k i to produce said third messages m' i described by m'.sub.i =m.sub.i.sup.d (mod n).

Claim 47

Apparatus as in claim 39 further comprising means for checking the public key digital signature property of at least one of said third messages m' i including exponentiation to the power e.

Claim 48

Apparatus for processing original digital messages before they receive public key digital signatures and for processing the resulting messages after they have received the public key digital signatures where said processed digitial messages are considered to be "blinded" and said resulting digital messages to be "unblinded" because, although the public key digital signatures of said resulting digital messages are checkable using a public key, even possession of the public key and of the corresponding secret signing key does not readily allow the correspondence between elements of said processed digital message set and elements of the corresponding said resulting digital message set to be determined, said apparatus for processing comprising: means for transforming at least part of a first input with a first blinding transformation depending on a first secret key to produce a first output; means for receiving said first output and transforming said first output with a second blinding transformation depending on a second secret key to produce a second output; means for receiving said second output and developing a third output at least partially responsive to the second output and to a secret signing key; means for receiving said third output and transforming the third output with a first unblinding tranformation, depending on a first one of said first and second secret keys, to produce a fourth output; and means for transforming said fourth output with a second unblinding transformation, depending on the remaining one of said first and second secret keys, to produce a fifth output, and the fifth output retaining a digital signature property related to said first input, and said third and the fifth outputs being not readily linkable without the first and second secret keys.

Claim 49

Apparatus for processing original digital messages before they receive public key digital signatures and for processing the resulting messages after they have received the public key digital signatures where said processed digitial messages are considered to be "blinded" and said resulting digital messages to be "unblinded" because, although the public key digital signatures of said resulting digital messages are checkable using a public key, even possession of the public key and of the corresponding secret signing key does not readily allow the correspondence between elements of said processed digital message set and elements of the corresponding said resulting digital message set to be determined, said apparatus for processing comprising: means for transforming at least part of a first input with a first blinding transformation depending on a first secret key to produce a first output; means for receiving said first output and transforming said first output with a second blinding transformation depending on a second secret key to produce a second output; means for receiving said second output and developing a third output at least partially responsive to the second output and to a secret signing key; means for receiving said third output and transforming the third output with a first unblinding tranformation, depending on a first one of said first and second secret keys, to produce a fourth output; and means for transforming said fourth output with a second unblinding transformation, depending on the remaining one of said first and second secret keys, to produce a fifth output, and the fifth output retaining a digital signature property related to said first input, and said third and the fifth outputs being not readily linkable without the first and second secret keys.