Blind unanticipated 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 for said corresponding first keys that would produce the same said first messages with different correspondences between the original messages and the first messages.

Claim 4

A method as in claim 2 wherein said first keys are chosen from a distribution so that said at least two choices for said first keys are possible.

Claim 7

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

Claim 8

A method as in claim 5 wherein said first keys are chosen from a distribution so that said at least two choices for said first keys are possible.

Claim 11

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

Claim 12

A method as in claim 8 wherein said first keys are chosen substantially independently from a distribution so that said at least two choices for said first keys are possible.

Claim 15

A method as in claim 10 wherein, for substantially any at least two of said original messages, there exist 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 16

A method as in claim 11 wherein said first keys are chosen from a distribution so that said two choices for said first keys are possible.

Claim 17

A method as in claim 10 wherein at least two distinct said generators are used in said blinding and corresponding said unblinding of at least one of said original digital messages.

Claim 18

A method as in claim 13 wherein one of said generators is the multiplicative inverse of unity.

Claim 19

The method of claim 10 further comprising the step of testing a set of generators to determine whether they generate a group containing said original messages.

Claim 20

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

Claim 21

The method of claim 16 further comprising the step of storing a message between said signing step and said checking step.

Claim 22

The method of claim 1, 4, 7, or 10 further comprising a re-blinding step that, responsive to at least one of said first keys, transforms an unblinded signed message into a blinded signed message.

Claim 23

A method as described in claim 1, 4, 7, or 10 wherein: said blinding step transforms an original message m in an RSA system with public modulus n using a first key comprised of k1 through kr, with r≧1, and known generators g 1 through g r to produce first message t described by t≡mg.sub.1.sup.k1 g.sub.2.sup.k2 . . . g.sub.r.sup.kr (mod n); said signing step transforms said first message t using secret signing key di to produce second message t' described by t≡t.sup.di (mod n); and said unblinding step transforms said second message t' using said first key comprised of k1 through kr and using known signed forms of said generators g 1 through g r to produce said third message m'j described by m'.sub.i ≡t'g.sub.1.sup.-dik1 g.sub.2.sup.-dik2 . . . g.sub.r.sup.-dikr (mod n).

Claim 24

The method of claim 19 wherein at least one of said generators g j is -1.

Claim 25

The method of claim 19 further comprising the step of testing a set of generators to determined whether they generate a group containing said original messages.

Claim 26

The method of claim 19 wherein at least one said first key is chosen substantially uniformly from an interval whose size is at least a substantially large multiple of n.

Claim 27

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 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 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, without anticipating which of a set of corresponding signing keys will be used to sign each first message; means for signing each of said first messages by a signer party applying a public key digital signature being one member of said set of secret signing keys to produce a corresponding plurality of 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 corresponding secret key of said signing step; said means for said blinding including means used by said supplier parties wherein said first keys are used so as to make said signer party without the corresponding first keys unable to readily determine the correspondence between individual messages within said plurality of third messages and individual messages within said plurality of first messages; and wherein the number of members of said set of signing keys potentially unblindable by said unblinding step is being substantially unlimited in practice.

Claim 28

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 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 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, without anticipating which of a set of corresponding signing keys will be used to sign each first message; means for signing each of said first messages by a signer party applying a public key digital signature being one member of said set of secret signing keys to produce a corresponding plurality of 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 corresponding secret key of said signing step; said means for said blinding including means used by said supplier parties wherein said first keys are used so as to make said signer party without the corresponding first keys unable to readily determine the correspondence between individual messages within said plurality of third messages and individual messages within said plurality of first messages; and wherein the number of members of said set of signing keys potentially unblindable by said unblinding step is being substantially unlimited in practice.

Claim 29

Apparatus in claim 23 wherein, for substantially any at least two of said original messages, there exist at least two possible choices for said corresponding first keys that would produce the same said first messages with different correspondences between the original messages and the first messages.

Claim 30

Apparatus as in claim 24 wherein said means for blinding includes means for choosing said first keys from a distribution so that said at least two choices for said first keys are possible.

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 comprising: means for blinding a plurality of original digital messages m i by use of plural first keys to produce a corresponding plurality of blinded first messages t i ; means for applying a public key digital signature to each of said first digital messages t i , using one key d j of a plurality of secret signing keys, to produce a corresponding plurality of signed digital second messages t' ij ; means for unblinding said plurality of signed digital second messages in a way depending at least in part on said plural first keys to produce a corresponding plurality of unblinded digital third messages m' ij having validity which can be checked by using a public checking key e j corresponding to said secret signing key d j ; wherein said first keys are provided by said means for blinding so as to make substantially computationally infeasible substantial linking, even using the secret signing keys, of individual messages within an unblinded signed digital third message set to the individual messages of its corresponding antecedent original digital message set; and at least one of said means for blinding and means for unblinding include means performing an amount of computation which grows less than linearly with respect to the number of secret signing keys useable in the system.

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 comprising: means for blinding a plurality of original digital messages m i by use of plural first keys to produce a corresponding plurality of blinded first messages t i ; means for applying a public key digital signature to each of said first digital messages t i , using one key d j of a plurality of secret signing keys, to produce a corresponding plurality of signed digital second messages t' ij ; means for unblinding said plurality of signed digital second messages in a way depending at least in part on said plural first keys to produce a corresponding plurality of unblinded digital third messages m' ij having validity which can be checked by using a public checking key e j corresponding to said secret signing key d j ; wherein said first keys are provided by said means for blinding so as to make substantially computationally infeasible substantial linking, even using the secret signing keys, of individual messages within an unblinded signed digital third message set to the individual messages of its corresponding antecedent original digital message set; and at least one of said means for blinding and means for unblinding include means performing an amount of computation which grows less than linearly with respect to the number of secret signing keys useable in the system.

Claim 33

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

Claim 34

Apparatus as in claim 27 wherein said means for blinding chooses said first keys from a distribution so that said at least two choices for said first keys are possible.

Claim 35

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 comprising: means for blinding a plurality of original digital messages m i by use of plural first keys to produce a corresponding plurality of blinded first messages t i ; means for applying a public key digital signature, using one key d j of a plurality of secret signing keys, to each of said first digital messages t i to produce a corresponding plurality of signed digital second messages t' ij ; means for unblinding said plurality of signed digital second messages in a way depending at least on said plural first keys to produce a corresponding plurality of unblinded digital third messages m' ij having validity which can be checked by using a public checking key e j corresponding to said secret signing key d j ; wherein said first keys are provided by said means for blinding so as to make substantially computationally infeasible substantial linking, even using the secret signing keys, of individual messages within an unblinded signed digital third message set to the individual messages of its corresponding antecedent original digital message set; and wherein at least one of said means for blinding and unblinding include means for performing an amount of computation that does not grow once the number of secret signing keys useable in the system reaches some threshold.

Claim 36

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 comprising: means for blinding a plurality of original digital messages m i by use of plural first keys to produce a corresponding plurality of blinded first messages t i ; means for applying a public key digital signature, using one key d j of a plurality of secret signing keys, to each of said first digital messages t i to produce a corresponding plurality of signed digital second messages t' ij ; means for unblinding said plurality of signed digital second messages in a way depending at least on said plural first keys to produce a corresponding plurality of unblinded digital third messages m' ij having validity which can be checked by using a public checking key e j corresponding to said secret signing key d j ; wherein said first keys are provided by said means for blinding so as to make substantially computationally infeasible substantial linking, even using the secret signing keys, of individual messages within an unblinded signed digital third message set to the individual messages of its corresponding antecedent original digital message set; and wherein at least one of said means for blinding and unblinding include means for performing an amount of computation that does not grow once the number of secret signing keys useable in the system reaches some threshold.

Claim 37

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

Claim 38

Apparatus as in claim 30 wherein said means for blinding chooses said first keys substantially independently from a distribution so that said at least two choices for said first keys are possible.

Claim 39

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 comprising: means for blinding a plurality of original digital messages responsive to first keys to produce corresponding blinded first digital messages, said blinding including for each said original digital message at least forming a product including said original digital message and at least one generator and generators appearing in said product being raised to powers depending on at least one of said first keys; means for signing each of said first messages by applying a public key digital signature transformation thereto to produce a corresponding plurality of digital second messages, said signing including at least raising to a power depending on a secret signing key; means for unblinding said plurality of second messages by transforming each at least by forming a product including a multiplicative inverse of a signed form of said at least one generator raised to a power depending on at least one of 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 at least one secret signing key, said products, multiplicative inverses and raising to powers all being in a finite structure where they are defined; and said means for blinding including means using separate 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 40

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 comprising: means for blinding a plurality of original digital messages responsive to first keys to produce corresponding blinded first digital messages, said blinding including for each said original digital message at least forming a product including said original digital message and at least one generator and generators appearing in said product being raised to powers depending on at least one of said first keys; means for signing each of said first messages by applying a public key digital signature transformation thereto to produce a corresponding plurality of digital second messages, said signing including at least raising to a power depending on a secret signing key; means for unblinding said plurality of second messages by transforming each at least by forming a product including a multiplicative inverse of a signed form of said at least one generator raised to a power depending on at least one of 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 at least one secret signing key, said products, multiplicative inverses and raising to powers all being in a finite structure where they are defined; and said means for blinding including means using separate 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 41

Apparatus as in claim 32 wherein, for substantially any at least two of said original messages, there exist 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 42

Apparatus as in claim 33 wherein said means for blinding includes means for choosing said first keys from a distribution so that said two choices for said first keys are possible.

Claim 43

Apparatus as in claim 32 wherein said means for blinding and means for unblinding use at least two distinct said generators in said blinding and corresponding said unblinding of at least one of said original digital messages.

Claim 44

Apparatus as in claim 35 wherein one of said generators is the multiplicative inverse of unity.

Claim 45

Apparatus as in claim 32 further comprising means for testing a set of generators to determine whether they generate a group containing said original messages.

Claim 46

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

Claim 47

Apparatus as in claim 38 further comprising means for storing a message between said signing step and said checking step.

Claim 48

Apparatus as in claim 23, 26, 29 or 32 further comprising means for re-blinding, responsive to at least one of said first keys, to transform an unblinded signed message into a blinded signed message.

Claim 49

Apparatus as described in claim 23, 26, 29 or 32 wherein: said means for blinding transforms an original message m in an RSA system with public modulus n using a first key comprised of k1 through kr, with r≧1, and known generators g 1 through g r to produce first message t described by t≡mg.sub.1.sup.k1 g.sub.2.sup.k2 . . . g.sub.r.sup.kr (mod n); said means for signing transforms said first message t using secret signing key di to produce second message t' described by t≡t.sup.di (mod n); and said means for unblinding transforms said second message t' using said first key comprised of k1 through kr and using known signed forms of said generators g 1 through g r to produce said third message m'j described by m'.sub.i ≡t'g.sub.1.sup.-dik1 g.sub.2.sup.-dik2 . . . g.sub.r.sup.-dikr (mod n).

Claim 50

Apparatus as in claim 41 wherein at least one of said generators g j is -1.

Claim 51

Apparatus as in claim 41 further comprising means for testing a set of generators to determined whether they generate a group containing said original messages.

Claim 52

Apparatus as in claim 41 wherein said means for blinding includes means for choosing at least one said first key substantially uniformly from an interval whose size is at least a substantially large multiple of n.