Blind unanticipated signature systems
First Claim
1. A method 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 method for processing comprising the steps of:
- 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;
signing each of said first messages by a signer party applying a public key digital signature using one member of said set of secret signing keys to produce a corresponding plurality of second messages;
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 blinding step being performed by said supplier parties using said first keys 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
the number of members of said set of signing keys potentially unblindable by said unblinding step being substantially unlimited in practice.
19 Assignments
0 Petitions
Accused Products
Abstract
An improved blind signature system not requiring computation during blinding for anticipating which of a plurality of possible signatures will be made during signing, while still allowing the blinding party to unblind and recover the unanticipated kind of signature on what was blinded. An exemplary embodiment blinds by forming a product including a plurality of generators raised to powers normally secret from the signing party, and unblinds by forming a product with the multiplicative inverse of a signed form of the generators raised to the original powers. Re-blinding allows a signature on a value to be transformed into a signature on a particular blinded form of the value.
-
Citations
44 Claims
-
1. A method 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 method for processing comprising the steps of:
-
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; signing each of said first messages by a signer party applying a public key digital signature using one member of said set of secret signing keys to produce a corresponding plurality of second messages; 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 blinding step being performed by said supplier parties using said first keys 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 the number of members of said set of signing keys potentially unblindable by said unblinding step being substantially unlimited in practice. - View Dependent Claims (2, 3, 16, 17, 18, 19, 20, 21, 22)
-
-
4. A method 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 method for processing comprising the steps of:
-
blinding a plurality of original digital messages mi by use of plural first keys to produce a corresponding plurality of blinded first messages ti ; applying a public key digital signature to each of said first digital messages ti, using one key dj of a plurality of secret signing keys, to produce a corresponding plurality of signed digital second messages t'"'"'ij ; 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 ej corresponding to said secret signing key dj ; said first keys being provided 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 blinding and unblinding steps being performed using an amount of computation which grows less than linearly with respect to the number of secret signing keys useable in the system. - View Dependent Claims (5, 6)
-
-
7. A method 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 method for processing comprising the steps of:
-
blinding a plurality of original digital messages mi by use of plural first keys to produce a corresponding plurality of blinded first messages ti ; applying a public key digital signature, using one key dj of a plurality of secret signing keys, to each of said first digital messages ti to produce a corresponding plurality of signed digital second messages t'"'"'ij ; 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 ej corresponding to said secret signing key dj ; said first keys being provided 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 blinding and unblinding steps being performed using an amount of computation that does not grow once the number of secret signing keys useable in the system reaches some threshold. - View Dependent Claims (8, 9)
-
-
10. A method 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 method for processing comprising the steps of:
-
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; signing each of said first messages by applying a public key digital signature transformation thereto to produce a corresponding plurality of digital second messages, and signing including at least raising to a power depending on a secret signing key; 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 blinding step being performed 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. - View Dependent Claims (11, 12, 13, 14, 15)
-
-
23. 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. - View Dependent Claims (24, 25, 38, 39, 40, 41, 42, 43, 44)
-
-
26. 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 mi by use of plural first keys to produce a corresponding plurality of blinded first messages ti ; means for applying a public key digital signature to each of said first digital messages ti, using one key dj 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 ej corresponding to said secret signing key dj ; 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. - View Dependent Claims (27, 28)
-
-
29. 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 mi by use of plural first keys to produce a corresponding plurality of blinded first messages ti ; means for applying a public key digital signature, using one key dj of a plurality of secret signing keys, to each of said first digital messages ti 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 ej corresponding to said secret signing key dj ; 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. - View Dependent Claims (30, 31)
-
-
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 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. - View Dependent Claims (33, 34, 35, 36, 37)
-
Specification