Blind signature systems - Patent Review 4759063

Claims

What is claimed is:

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;

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;

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 signing step; and

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.

2. 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.

3. 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.

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

5. 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.

6. 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.

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 ditial 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 by transforming each responsive to a corresponding first key to produce corresponding digital first messages;

signing each of said first messages by applying a public key digital signature transformation thereto, using at least a secret signing key, to produce a corresponding plurality of digital second messages;

unblinding said plurality of 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 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.

8. 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.

9. 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.

10. 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.

11. 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.

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

13. 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.

14. A method for providing untraceability of value transfers by 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 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 method for processing comprising the steps of:

blinding at least part of each of a plurality of digital original messages responsive to first keys to produce corresponding blinded first digital messages, by each of plural supplier parties;

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;

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;

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;

receiving at least one of said third messages by a checker party, and the checker party checking a public key digital signature related to the corresponding said original message; and

maintaining a record depending on said previously checked third messages and preventing a signature related to the same such third message from being accepted more than once, and providing value in exchange for said signatures accepted.

15. 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.

16. 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.

17. A method as described in claim 15 wherein:

said blinding step transforms original messages m.sub.i using first keys k.sub.i to produce first messages t.sub.i described by

t.sub.i =m.sub.i .multidot.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.sub.i using secret signing key d to produce second messages t'.sub.i described by

t'.sub.i =t.sub.i.sup.d (mod n); and

said unblinding step transforms said second messages t'.sub.i using first keys k.sub.i to produce said third messages m'.sub.i described by

m'.sub.i =m.sub.i.sup.d (mod n).

18. 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'.sub.i including exponentiation to the power e.

19. A method 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 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 elements of said processed digital message set and elements of the corresponding said resulting digital message set to be determined, said method for processing comprising the step of:

transforming at least part of a first input with a first blinding transformation depending on a first secret key to produce a first output;

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;

receiving said second output and developing a third output at least partially responsive to the second output and to a secret signing key;

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 key, to produce a fourth output; and

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.

20. 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.

21. 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.

22. 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.

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

24. 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.

25. 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.

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 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.

27. 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.

28. 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.

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

30. 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.

31. 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.

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

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

34. 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.

35. 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.

36. 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.

37. 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.

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

39. Apparatus as described in claim 37 wherein:

said means for blinding transforms original messages m.sub.i using first keys k.sub.i to produce first messages t.sub.i described by

t.sub.i =m.sub.i .multidot.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.sub.i using secret signing key d to produce second messages t'.sub.i described by

t'.sub.i =t.sub.i.sup.d (mod n); and

said means for unblinding transforms said second messages t'.sub.i using first keys k.sub.i to produce said third messages m'.sub.i described by

m'.sub.i =m.sub.i.sup.d (mod n).

40. 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'.sub.i including exponentiation to the power e.

41. 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.

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to cryptographic systems, and more specifically to systems including public key digital signatures.

2. Description of Prior Art

The concept of digital signatures promises to be an important one in commercial applications of cryptographic techniques. The digital signature concept is quite simple. Suppose a bank wishes to be able to make digital signatures that can be checked by all its customers. The bank develops a mathematical function, and supplies all its customers, and anyone else who cares to know, complete instructions for efficiently computing the function. The trick is, that when the bank developed the function, it included in it a trapdoor. This trapdoor allows the bank to efficiently compute the inverse of the function. Because it is infeasible to compute the inverse of the function without knowing the trapdoor, only the bank can compute the inverse of the function. Thus, if a customer of the bank sees a message that could only have been created by someone who knows how to compute the inverse of the function, then the customer knows that the message must have come from the bank.

The concept of digital signatures was first proposed in the literature by Diffie, et al, in "Multiuser Cryptographic Techniques," AFIPS-Conference Proceedings, Vol, 45, pp. 109-112. The first really practical example functions with the required trapdoor properties were disclosed by Rivest, Shamir and Adelman, in "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM Vol. 21, No. 2, February 1978. This system has become known as "RSA", after its inventors, and remains the most credible candidate for widespread use. It is based on two main ideas. The first is that is relatively easy for someone to create a large number for which only he knows the prime factors. (One way to accomplish this is for the creator to form the number as the product of two suitable sufficiently large primes chosen at random. Such primes are easily found by random trial and error since the density of primes even in the neighborhood of 50 digit numbers is on the order of one percent, and reasonably efficient primality tests are well known in the art.) The second main idea is that knowing the prime factors of the modulus under which exponentiation is performed allows one to produce pairs of exponents that behave as inverses.

In other words, consider the function f(x)=x.sup.e mod n, to be the result of raising x to the power e and then finding the remainder after dividing by n. There may be a number d, such that g(x)=x.sup.d mod n and g(f(x))=f(g(x))=x. If one chooses primes p and q and a suitable e, one can readily compute a corresponding d, simply as the multiplicative inverse of e modulo ((p-1).times.(q-1)), such modular multiplicative inverses to be described. It is thought to be almost impossible to compute d from e and n without knowing p and q, and almost impossible to determine p and q from n. Thus, if e and n are made public, anyone can compute f(x), but only the creator of n can compute the inverse g(x).

There are a variety of ways to use such a "public signature function" and its inverse "secret signature function" to make digital signatures. In general it is not desirable to maintain that any message which results from applying the public signature function is a valid signed message. The reason is that anyone could create a number at random and claim that it was a signature on the message that results when the public signature function is applied. One solution to this problem is to designate some subset of the messages as "valid messages" such that, for example, only one in 10.sup.50 messages is valid. Thus someone would have to apply the public signature function to an average of 5.times.10.sup.49 random messages, (which may not be a credible threat) before obtaining a valid message as a result. (An RSA system with a one-hundred digit modulus would still have 10.sup.50 possible valid messages.) The process of "checking" a digital signature in such a scheme involves applying the public signature function to the digital signature to be checked, and determining whether the resulting number is a member of the set of valid messages.

It is anticipated that a bank may wish to use digital signatures to validate various numbers that are to serve as electronic money. The bank will form digital signatures of valid numbers, and sell them to individuals by charging the individuals' accounts say one dollar for each signed number. These digitally signed numbers might be thought of as electronic bank "notes". An individual can check the digital signature on such a digitally signed note by applying the public signature function of the bank to the note and verifying that the result is a valid message. When the individual wishes to pay for some goods or services, say for example buying something costing one dollar at a shop, the individual gives the digitally signed note to the shop as payment. The shop can then check the digital signature on the note. If the result of the check is positive, then the shop can supply the digital signature to the bank, who can deposit one dollar in the shop's account, after again checking the signature on the note. The bank will also keep a list of the valid numbers which have been previously cleared, to prevent the same one from being used more than once. Of course, many different denominations of such digitally signed bank notes might actually be offered for sale by the bank, each denomination using a different pair of signature functions.

The problems with such payments systems possible under the prior art is that the bank will always be able to know which account a note was withdrawn from and which account it is ultimately deposited to--and this poses serious problems from a personal privacy perspective. As more and more payment transactions become automated, and more and more data associated with transactions is captured electronically, a tremendous amount of data about a person's habits, affiliations, lifestyle, whereabouts and so on could be captured by the bank in electronic form. This places the bank in a position it would rather not be in, because it has to to convince its customers that it handles this data properly, and also because of possible legal exposure, there will be various costs, restrictions on and interference with operating procedures and personnel. The customers of the bank are also placed in an undesirable position, since there may always be some doubt as to how such data is actually being used or might be used in the future.

This example illustrates the need for signature systems that do not allow the signer to trace all things validated with his signature. Many other similar situations, such as notarizations, stocks, bonds, other certificates, credentials, authorizations and so on are also anticipated.

OBJECTS OF THE INVENTION

Accordingly, it is an object of the present invention to provide a system utilizing digital signatures in which the provider of a message for signing can transform the message to be signed into a form which obscures the content of the message, the signer can sign the transformed message and return it to the provider, and the provider can transform the signed message in such a way that the result retains the digital signature property related to the original message content, but the result is not readily associated with the transformed message received by the signer.

Another object of the present invention is to provide a system which can be used in a payment or other type of system as previously described, wherein, for example, the provider may choose a valid bank note message at random, transform it, have it signed in transformed form, and transform it back to a form related to the original note but bearing a digital signature property.

Another object of the invention is to provide a system with the additional property that the security of the system against linking of the transformed messages received by the signer with the signed messages ultimately revealed by the provider does not rely on arguments based on computational infeasibility.

Another object of the invention is to provide additionally the property that if only j things are signed, then no more than j signatures can be developed by the provider(s).

Yet another object of the invention is to allow messages to be transferred through what might be thought of as a series of more than one provider on the way to the signer and returned through a related series of providers.

Still another object of the invention is to provide efficient, economical and practical apparatus and methods fulfilling the other objects of the invention.

Other objects, features, and advantages of the present invention will be appreciated when the present description and appended claims are read in conjunction with the drawing figures.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 shows a combination functional and detailed block diagram of a blind signature system in accordance with the teachings of the present invention.

FIG. 2a shows a block diagram of a single provider user in accordance with the teachings of the present invention.

FIG. 2b shows a block diagram of a first two provider use in accordance with the teachings of the present invention.

FIG. 2c shows a block diagram of a second two provider use in accordance with the teachings of the present invention.

FIG. 3 is a detailed schematic diagram of an exemplary embodiment of a modular inverter.

FIG. 4 is a detailed schematic diagram of an exemplary embodiment of a modular exponentiator.

FIG. 5 is a detailed schematic diagram of an exemplary embodiment of a modular multiplier.

FIG. 6 is a detailed schematic diagram of an exemplary embodiment of a modular subtractor.

FIG. 7 is a detailed schematic diagram of an exemplary embodiment of a modular adder.

BRIEF SUMMARY OF THE INVENTION

In accordance with these and other objects of the present invention, a brief summary of an exemplary embodiment is presented. The concept of blind signatures may be understood by an analogy based on carbon paper lined envelopes. Suppose Alice supplies Bob with a first envelope and a second envelope, each containing a piece of carbon paper facing a blank white slip of paper. Bob signs both envelopes on the outside with identical signatures and returns them to Alice. Alice privately removes the paper slips from the envelopes, each slip now bearing a carbon image of Bob's signature; places the slips in a random order; presents them to Bob; and asks him which slip was in the first envelope. Bob cannot answer with certainty, though he knows each slip was in an envelope he signed, because he does not know which slip was in which envelope.

Turning now to FIG. 2a, one exemplary embodiment will be described in simplified form to introduce some central concepts, but such description should not be taken to limit the scope of the invention, which is described more fully elsewhere in the present specification. Two cryptographic transformation, "blinding" 203 and "unblinding" 204, are shown depending on a secret cryptographic key k. A digital signature transformation 202 is shown, which depends on secret signing information not shown for clarity.

The original message m (corresponding to the blank slip of paper in the analogy above) is first encrypted by blinding transformation 203 (which corresponds with placing the slip in the envelope), resulting in transformed message 6 (corresponding to the slip in the envelope). A digital signature responsive to the transformed message t is then developed by signing transformation 202 (corresponding with Bob signing the outside of the envelope), and is shown as t' (corresponding to the signed envelope). The unblinding transformation 204 takes t' and converts it by use of key k into a variant m' of the original message m which retains a signature property (corresponding to the signed slip removed from the envelope by the party who placed it there).

This entire procedure would normally be repeated more than once, say 1 times, using a fresh key k.sub.j, 1.ltoreq.j.ltoreq.1, each time (just as there were multiple envelopes in the analogy). Thus, a set of signed values {m'.sub.j } is generated (corresponding to a set of signed slips), as well as a set of transformed value {t.sub.j } (corresponding to a set of envelopes). An important property of such a blind signature system is that if the signer knows only the two unordered sets, and not the keys k.sub.j, then the signer is unable to readily determine the correspondence between the elements of the two sets (just as Bob was unable to tell which slip was from which envelope)--even though the signer is assured by the signature property that such a correspondence must exist.

In one embodiment of the present invention, based on the RSA digital signature system as earlier described, the following congruences might hold:

t.ident.[m].times.k.sup.3 (mod n),

t'.ident.[m.times.k.sup.e ].sup.d .ident.m.sup.d .times.k (mod n), and

m'.ident.[m.sup.d .times.k].times.k.sup.-1 .ident.m.sup.d (mod n),

where n is the publicly known modulus and e and d are exemplary public and private signature exponents respectively. The square brackets show the input to the transformation whose output is shown on the left hand side, and thus they define the function of each of the three transformations. The signature property of m' might be checked by anyone with access to the public signing function based on e, simply by forming m'.sup.e mod n and checking whether the result is a valid message m.

GENERAL DESCRIPTION

General descriptions of the functions of some constituent parts of the present invention will now be presented.

Line 155 shows the output of blinding transformation 103 being input to signing transformation 102; line 157 shows the output of signing transformation 102 being input to unblinding transformation 104; line 159 shows the output of unblinding transformation 104 being input to signature checker 105. The method or means whereby such information is transferred as shown by these lines is not essential to the present invention, and may be accomplished in any suitable way. For example, the output and input means may be brought into physical proximity with each other, or they may communicate remotely by any kind of communication network or other technique. The information may be encoded in various forms, some of them cryptographic, and decoded and transformed between codings on its way. Similarly the information may be stored and/or detained in various forms along its way.

The term "party" is used herein to indicate an entity with control over some secret information. In some cases, a party might be a person who knows a secret cryptographic key. It is anticipated that a plurality of people may each know part or all of some key matter, and then they might collectively be thought of as a party. In other cases, a key may normally be known only to apparatus and not people, and the apparatus or the people able to utilize the apparatus may be regarded as parties. Different people may use the same apparatus each with different keys, assuming they all have some trust in the apparatus, and then they might be regarded as separate parties. Thus, for example, signature transformation 102 may be regarded as a step in a method or part of an apparatus, and/or it may be regarded as a party, and it may be called signer 102 or signer party 102.

Key source 123 is shown without inputs and with output 153. The function of key source 123 is to output a value normally at least partially unknown to at least the signer party 102. It is preferred that the output is nearly completely unknown outside the provider 101, and may not even be known to any persons but only to apparatus. The term "secret key" may be used herein to refer to information, such as the output of key source 123, that is normally supposed to be unknown to various parties. Many means and methods are known in the art for generating such keys. One approach uses unpredictable physical phenomena, such as noise in a semiconductor or other electronic component or radioactive decay, or timing of events generated by asynchronous processes, such as humans pushing buttons. Another approach uses algorithmic transform