US4759063A — Blind signature systems
Document text
Research, not advice. Part of the Bitcoin research archive (October 2026). Claims labelled unverified, contested or fringe are reported, not endorsed; statuses of bills and rules are as of the date checked. Government, court and patent records are public domain; the research notes are CC BY 4.0.
United States Patent (19) 11 Patent Number: 4,759,063
Chaum (45) Date of Patent: Jul. 19, 1988
54 BLIND SIGNATURE SYSTEMS David Chaum, Ronald L. Rivest and Alan T. Sherman,
pp. 199-203, Plenum Press.
76 Inventor: David L. Chaum, 14652 Sutton St., "Signature Protocols for RSA and Other Public-Key
Sherman Oaks, Calif. 91306 Cryptosystems', by Dorothy E. Denning, Nov. 1982,
21 Appl. No.: 524,896 Computer Sciences Dept., Purdue University, W. La
fayette, Ind.
22 Filed: Aug. 22, 1983 "Chosen Signature Cryptanalysis of Public Key Cryptosys
51) Int. Cl. ............................................... H04L 9/00 tems', by Richard A. DeMillo & Michael J. Merritt,
52 U.S. C. ........................................ 380/30; 380/44; Oct. 25, 1982. Georgia Institute of Technology, School
380/28; 380/9 of Information & Computer Science.
58) Field of Search ............... 178/22.11, 22.08, 22.09, "Proceedings of the 1983 Symposium on Security and
178/22.14; 380/28, 30, 6, 9, 44 Privacy', Technical Committee of Security and Pri
vacy, IEEE Computer Society, Apr. 1983, Oakland,
56) References Cited Calif.
U.S. PATENT DOCUMENTS Primary Examiner-Salvatore Cangialosi
4,086,634 4/1978 Cook ..................................... 360/60 Assistant Examiner-Aaron J. Lewis
4,200,770 4/1980 Hellman et al. .... Attorney, Agent, or Firm-Larry S. Nixon; Aldo J. Test
4,218,582 8/1980 Hellman et al..... 178/22.11 (57 ABSTRACT
4,308,536 12/1981. Sims, Jr. et al. ...................... 342/71
4,351,982 9/1982 Miller et al. ... . . 178/2.2.11 A cryptographic system allows, in one exemplary use, a
4,405,829 9/1983 Rivest et al. ..................... 178/22.11 supplier to cryptographically transform a plurality of
4,424,414 1/1984 Hellman et al. .................. 178/22.11 messages responsive to secret keys; the transformed
4,458,109 7/1984 Mueller-Schloer .............. 178/22, 16 messages to be digitally signed by a signer; and the
OTHER PUBLICATIONS signed transformed messages returned to the supplier to
be transformed by the supplier, responsive to the same
"A Method for Obtaining Digital Signatures and Pub secret keys, in such a way that a digital signature related
lic-Key Cryptosystems' by Rivest et al., Communica to each original message is developed by the supplier.
tions of the ACM, Feb. 1978, vol. 21 #2. One important property of these systems is that the
"Multiuser Cryptographic Techniques” by Diffie ind signer cannot determine which transformed message
Hellman, AFIPS-Conference Proceedings, vol. 45, received for signing corresponds with which digital
6/8/76, p. 109-112. signature-even though the signer knows that such a
"Chosen Signature Cryptanalysis of the RSA (MIT) Pub correspondence must exist.
lic Key Cryptosystem', by George I. Davida, Oct. 1982.
“Advances in Cryptology Proceedings of Crypto 82", by 41 Claims, 3 Drawing Sheets
U.S. Patent Jul.19, 1988 Sheet 1 of 3 4,759,063
124 O2
153
KEY SOU RCE
126
FIGURE 1
35
353
352 i
3O2 3O
FIGURE 3 3O3
355
2-359
MOD MULTIPLY 358 36O REGISTER 3O6
0
3O4. 357 36
MOD SUBTRACT m ...un-man- REGISTER 3O7
362
U.S. Patent Jul.19, 1988 Sheet 2 of 3 4,759,063
FG.2a
453
U.S. Patent Jul.19, 1988 Sheet 3 of 3 4,759,063
i
REGISTER
ADD
75.3
754. 756
S n
755
FIGURE 7 78, 7.0%
4,759,063 2
1.
from applying the public signature function is a valid
BLND SIGNATURE SYSTEMS signed message. The reason is that anyone could create
a number at random and claim that it was a signature on
BACKGROUND OF THE INVENTION the message that results when the public signature func
1. Field of the Invention tion is applied. One solution to this problem is to desig
This invention relates to cryptographic systems, and nate some subset of the messages as “valid messages'
more specifically to systems including public key digital such that, for example, only one in 100 messages is
signatures. valid. Thus someone would have to apply the public
2. Description of Prior Art signature function to an average of 5X 109 random
The concept of digital signatures promises to be an 10 messages, (which may not be a credible threat) before
important one in commercial applications of crypto obtaining a valid message as a result. (An RSA system
graphic techniques. The digital signature concept is with a one-hundred digit modulus would still have 1050
quite simple. Suppose a bank wishes to be able to make possible valid messages.) The process of "checking” a
digital signatures that can be checked by all its custom digital signature in such a scheme involves applying the
ers. The bank develops a mathematical function, and 15 public signature function to the digital signature to be
supplies all its customers, and anyone else who cares to checked, and determining whether the resulting number
know, complete instructions for efficiently computing is a member of the set of valid messages.
the function. The trick is, that when the bank developed It is anticipated that a bank may wish to use digital
the function, it included in it a trapdoor. This trapdoor 20 signatures to validate various numbers that are to serve
allows the bank to efficiently compute the inverse of the as electronic money. The bank will form digital signa
function. Because it is infeasible to compute the inverse tures of valid numbers, and sell them to individuals by
of the function without knowing the trapdoor, only the charging the individuals' accounts say one dollar for
bank can compute the inverse of the function. Thus, if a each signed number. These digitally signed numbers
customer of the bank sees a message that could only 25 might be thought of as electronic bank "notes'. An
have been created by someone who knows how to
compute the inverse of the function, then the customer individual can check the digital signature on such a
digitally signed note by applying the public signature
knows that the message must have come from the bank. function of the bank to the note and verifying that the
The concept of digital signatures was first proposed result is a valid message. When the individual wishes to
in the literature by Diffie, et al, in "Multiuser Crypto 30 pay for some goods or services, say for example buying
graphic Techniques,” AFIPS-Conference Proceedings, something costing one dollar at a shop, the individual
Vol, 45, pp. 109-112. The first really practical example
functions with the required trapdoor properties were gives the digitally signed note to the shop as payment.
disclosed by Rivest, Shamir and Adelman, in "A The shop can then check the digital signature on the
Method for Obtaining Digital Signatures and Public note. If the result of the check is positive, then the shop
Key Cryptosystems,' Communications of the ACM 35 can supply the digital signature to the bank, who can
Vol. 21, No. 2, February 1978. This system has become deposit one dollar in the shop's account, after again
known as "RSA', after its inventors, and remains the checking the signature on the note. The bank will also
most credible candidate for widespread use. It is based keep a list of the valid numbers which have been previ
on two main ideas. The first is that is relatively easy for ously cleared, to prevent the same one from being used
someone to create a large number for which only he 40 more than once. Of course, many different denomina
knows the prime factors. (One way to accomplish this is tions of such digitally signed bank notes might actually
for the creator to form the number as the product of be offered for sale by the bank, each denomination using
two suitable sufficiently large primes chosen at random. a different pair of signature functions.
Such primes are easily found by random trial and error The problems with such payments systems possible
since the density of primes even in the neighborhood of 45 under the prior art is that the bank will always be able
50 digit numbers is on the order of one percent, and to know which account a note was withdrawn from and
reasonably efficient primality tests are well known in which account it is ultimately deposited to-and this
the art.) The second main idea is that knowing the prime poses serious problems from a personal privacy per
factors of the modulus under which exponentiation is
performed allows one to produce pairs of exponents 50 spective.
come
As more and more payment transactions be
automated, and more and more data associated
that behave as inverses. with transactions is captured electronically, a tremen
In other words, consider the function f(x)=xemod n,
to be the result of raising x to the power e and then dous amount of data about a person's habits, affiliations,
finding the remainder after dividing by n. There may be the bank whereabouts
lifestyle, and so on could be captured by
a number d, such that g(x)=x(mod n and position it would ratherform.
55 in electronic
not
This places the bank in a
be in, because it has to to
g(f(x)=f(g(x)=x. If one chooses primes p and q and a convince its customers that it handles this data prop
suitable e, one can readily compute a corresponding d, erly, and also because of possible legal exposure, there
simply as the multiplicative inverse of e modulo will be various costs, restrictions on and interference
(p-1)X(q-1)), such modular multiplicative inverses with operating procedures and personnel. The custom
to be described. It is thought to be almost impossible to 60 of the bank are also placed in an undesirable posi
computed from e and n without knowing p and q, and ers tion, since there may always be some doubt as to how
almost impossible to determine p and q from n. Thus, if such data is actually being used or might be used in the
e and n are made public, anyone can compute f(x), but
only the creator of n can compute the inverse g(x). future.
There are a variety of ways to use such a "public 65 This example illustrates the need for signature sys
signature function' and its inverse "secret signature tems that do not allow the signer to trace all things
function' to make digital signatures. In general it is not validated with his signature. Many other similar situa
desirable to maintain that any message which results tions, such as notarizations, stocks, bonds, other certifi
4,759,063
3 4.
cates, credentials, authorizations and so on are also BRIEF SUMMARY OF THE INVENTION
anticipated.
OBJECTS OF THE INVENTION In accordance with these and other objects of the
present invention, a brief summary of an exemplary
Accordingly, it is an object of the present invention embodiment is presented. The concept of blind signa
to provide a system utilizing digital signatures in which tures may be understood by an analogy based on carbon
the provider of a message for signing can transform the paper lined envelopes. Suppose Alice supplies Bob with
message to be signed into a form which obscures the a first envelope and a second envelope, each containing
content of the message, the signer can sign the trans a piece of carbon paper facing a blank white slip of
formed message and return it to the provider, and the 10 paper. Bob signs both envelopes on the outside with
provider can transform the signed message in such a identical signatures and returns them to Alice. Alice
way that the result retains the digital signature property privately removes the paper slips from the envelopes,
related to the original message content, but the result is each slip now bearing a carbon image of Bob's signa
not readily associated with the transformed message ture; places the slips in a random order; presents them to
received by the signer. 15 Bob; and asks him which slip was in the first envelope.
Another object of the present invention is to provide Bob cannot answer with certainty, though he knows
a system which can be used in a payment or other type each slip was in an envelope he signed, because he does
of system as previously described, wherein, for exam not know which slip was in which envelope.
ple, the provider may choose a valid bank note message Turning now to FIG. 2a, one exemplary embodiment
at random, transform it, have it signed in transformed 20 will be described in simplified form to introduce some
form, and transform it back to a form related to the central concepts, but such description should not be
original note but bearing a digital signature property. taken to limit the scope of the invention, which is de
Another object of the invention is to provide a system scribed more fully elsewhere in the present specifica
with the additional property that the security of the tion. Two cryptographic transformation, "blinding'
system against linking of the transformed messages re 25 203 and "unblinding' 204, are shown depending on a
ceived by the signer with the signed messages ulti
mately revealed by the provider does not rely on argu secret mation
cryptographic key k. A digital signature transfor
202 is shown, which depends on secret signing
ments based on computational infeasibility. information not shown for clarity.
Another object of the invention is to provide addi
tionally the property that if only j things are signed, 30 slip of paper in message
The original m (corresponding to the blank
then no more than j signatures can be developed by the blinding transformation 203above)
the analogy is first encrypted by
(which corresponds with
provider(s). placing the slip in the envelope), resulting in trans
Yet another object of the invention is to allow mes formed message 6 (corresponding to the slip in the en
sages to be transferred through what might be thought velope). A digital signature responsive to the trans
of as a series of more than one provider on the way to 35 formed message t is then developed by signing transfor
the signer and returned through a related series of pro mation 202 (corresponding with Bob signing the outside
viders.
of the envelope),
Still another object of the invention is to provide the signed envelope). and is shown as t' (corresponding to
efficient, economical and practical apparatus and meth 204 takes t' and convertsThe it by
unblinding transformation
use of key kinto a variant
ods fulfilling the other objects of the invention. m’ of the original message m which retains a signature
Other objects, features, and advantages of the present
invention will be appreciated when the present descrip property (corresponding to the signed slip removed
tion and appended claims are read in conjunction with from the envelope by the party who placed it there).
This entire procedure would normally be repeated
the drawing figures.
45 more than once, say 1 times, using a fresh key ki,
BRIEF DESCRIPTION OF THE DRAWINGS 1SjS1, each time (just as there were multiple envel
FIG. 1 shows a combination functional and detailed opes in the analogy). Thus, a set of signed values (mi)
block diagram of a blind signature system in accordance is generated (corresponding to a set of signed slips), as
with the teachings of the present invention. well as a set of transformed value {t} (corresponding to
a set of envelopes). An important property of such a
FIG. 2a shows a block diagram of a single provider 50 blind
user in accordance with the teachings of the present the two signature system is that if the signer knows only
invention. unordered sets, and not the keys ki, then the
FIG. 2b shows a block diagram of a first two pro signer is unable to readily determine the correspon
vider use in accordance with the teachings of the pres dence between the elements of the two sets (just as Bob
ent invention. 55 was unable to tell which slip was from which en
FIG.2c shows a block diagram of a second two pro ture velope)-even though the signer is assured by the signa
vider use in accordance with the teachings of the pres property that such a correspondence must exist.
ent invention. In one embodiment of the present invention, based on
FIG. 3 is a detailed schematic diagram of an exem the the RSA digital signature system as earlier described,
plary embodiment of a modular inverter. following congruences might hold:
FIG. 4 is a detailed schematic diagram of an exem
plary embodiment of a modular exponentiator.
FIG. 5 is a detailed schematic diagram of an exem
plary embodiment of a modular multiplier.
FIG. 6 is a detailed schematic diagram of an exem 65 m's mixk)x kism (mod n),
plary embodiment of a modular subtractor.
FIG. 7 is a detailed schematic diagram of an exem where n is the publicly known modulus and e and d are
plary embodiment of a modular adder. exemplary public and private signature exponents re
4,759,063 6
5
spectively. The square brackets show the input to the may be generated initially for one, and then retained,
transformation whose output is shown on the left hand possibly in encrypted form, and/or in some protected
side, and thus they define the function of each of the and/or tamper indicating or tamper responding appara
three transformations. The signature property of m' tus. An equivalent approach for the present invention
might be checked by anyone with access to the public would be re-generating the key algorithmically each
signing function based one, simply by forming m' mod time it is needed.
n and checking whether the result is a valid message m. Signature checker 105 is shown as taking its input
GENERAL DESCRIPTION
from the output of unblinding transformation 104, line
159, and producing output 161, shown in the preferred
General descriptions of the functions of some constit 10 embodiment as m. The function of checker 105 is to
uent parts of the present invention will now be pres produce an indication of whether the input value has
ented. the properties of a valid signature. An implicit input is
Line 155 shows the output of blinding transformation the public signature information, shown as e in the pre
103 being input to signing transformation 102; line 157 ferred embodiment. The authenticity of this information
shows the output of signing transformation 102 being 15 forms the basis for the authenticity decision about the
input to unblinding transformation 104; line 159 shows signature input, and thus such information may shown
the output of unblinding transformation 104 being input contained within checker 105. Checker 105 serves a
to signature checker 105. The method or means logical function of indicating whether or not the signa
whereby such information is transferred as shown by ture appears to have been transformed using the secret
these lines is not essential to the present invention, and 20 signature information corresponding to the public sig
may be accomplished in any suitable way. For example, nature information; any means or method performing
the output and input means may be brought into physi this function may be regarded as a signature checker.
cal proximity with each other, or they may communi (Other data may also be output by the checker 105, such
cate remotely by any kind of communication network as parameter values included during formation of the
or other technique. The information may be encoded in 25 signature.)
various forms, some of them cryptographic, and de Various signature means and methods are known or
coded and transformed between codings on its way. would be obvious to those skilled in the art. One
Similarly the information may be stored and/or de method, that of choosing a subset of the domain of the
tained in various forms along its way. signature function as valid messages, has already been
The term "party' is used herein to indicate an entity 30 described. Another approach might not make such a
with control over some secret information. In some restriction, but might instead rely on information addi
cases, a party might be a person who knows a secret tional to the output of the signature function for input to
cryptographic key. It is anticipated that a plurality of the checking function. One-way functions may be
people may each know part or all of some key matter, thought of as public functions without publicly known
and then they might collectively be thought of as a 35 inverses, such functions being well known in the art,
party. In other cases, a key may normally be known such as the public function of an RSA system as earlier
only to apparatus and not people, and the apparatus or described, or those first disclosed by Purdy in "A High
the people able to utilize the apparatus may be regarded Security Log-in Procedure,' Communications of the
as parties. Different people may use the same apparatus ACM, Vol. 17, No. 8, August 1974, p. 442. Suppose the
each with different keys, assuming they all have some range of a one-way function y(x) is the domain of a
trust in the apparatus, and then they might be regarded private signing function g(x), with public signature
as separate parties. Thus, for example, signature trans function inverse f(x). One way to use such functions to
formation 102 may be regarded as a step in a method or form digital signatures is to form a signature, s, as the
part of an apparatus, and/or it may be regarded as a secret signature function of the image of the desired
party, and it may be called signer 102 or signer party 45 message, a, under the one-way function, s—g(y(a)). A
102. signature can be authenticated under such a scheme if
Key source 123 is shown without inputs and with numbers a and s are presented to the checker 105, such
output 153. The function of key source 123 is to output that y(a)=f(s). Notice that if the domain of y is larger
a value normally at least partially unknown to at least than its range, then it serves to compress the matter to
the signer party 102. It is preferred that the output is 50 be signed. Also notice that if the range of y is smaller
nearly completely unknown outside the provider 101, than the domain of g, then all or part of the number a
and may not even be known to any persons but only to may be encoded as the rest of the domain of g. In some
apparatus. The term "secret key” may be used herein to cases a strict one-way property may not be required.
refer to information, such as the output of key source Signing transformation 102 outputs some transforma
123, that is normally supposed to be unknown to various 55 tion of its input which depends on signing information
parties. Many means and methods are known in the art at least secret from the other parties, shown as d in the
for generating such keys. One approach uses unpredict preferred embodiment. Various exemplary signing
able physical phenomena, such as noise in a semicon transformations have been described above, but the
ductor or other electronic component or radioactive function of the signing transformation should be re
decay, or timing of events generated by asynchronous 60 garded as any transformation at least partially respon
processes, such as humans pushing buttons. Another sive to the information to be signed and to secret signing
approach uses algorithmic transformations on other information, such that some suitable checking function
secret information. Of course these two approaches can can be performed meaningfully. The term party, as
readily be combined. The output of the key source is mentioned earlier, may be used when referring to the
shown as input to transformations 103 and 104. The 65 signing transformation 102, and then it would be appro
probability distribution of keys is obviously of interest. priate to say signer 102.
In the preferred embodiment, they are preferably as Blinding transformation 103 takes a message from line
nearly uniformly distributed as practical. The output 151, shown as m in the preferred embodiment, and a
4,759,063
7 8
secret key from line 153. The nature of the source of m used in the signature authentication scheme, as de
is not essential to the present invention, but the particu scribed earlier. One possible explanation for this prop
lar value of m resulting in an actual particular output of erty holding is that a set of 1 signed things can be
blinding transformation 103 received by signer 102 thought of as giving at most 1 equations, and these can
should not normally be revealed to the signer 102 by be solved for at most 1 unknowns.
such a source, as this would allow the correspondence Yet another property of a blind signature system will
to be learned by the signer. The function of blinding be called the inability to "link', which may be under
transformation 103 is to produce output that does not stood as follows. Suppose there are 1 different mes
normally reveal the actual message input to those not in sages, my for 1sjs 1. Each message is the input to a
possession of the secret key k, and to cooperate with the 10 blinding transformation, using key ki, and the result is 1
singing and unblinding transformations, as will be de blinded messages ti (It is not essential whether each
scribed. Thus, the blinding transformation may be message is blinded by a different party, all messages are
thought of as a cryptographic transformation which blinded by the same party, or various parties each blind
hides some message by use of a key, with additional some subset of the messages.) Suppose further that the
properties that allow it to cooperate with the other 15 signer applies the signing transformation to each
transformations. blinded message ti, and returns each transformed mes
Unblinding transformation 104 takes a key from line sages ti to its provider. Further suppose that each pro
153 and a value from the signature transformation 102 vider applies the appropriate unblinding transformation
on line 157, and produces an output shown as line 159. to eacht', yielding a collecton of 1 unique messages m'
The function of unblinding transformation 104 is to 20 each bearing a signature property. Suppose still further
transform its input into a form which "retains a digital that the signer receives an unordered set whose 1 ele
signature property related to original message m'. In ments are exactly the mi, which may be denoted {m'}
other words, a checker 105 should be able to return a for leis 1. Finally, assume that the signer knows only
positive result when supplied output of unblinding the 1 things he has signed, ti, and the set {m'i), and no
transformation 104, and possibly other appropriate in 25 outside information about the provider(s), their keys, or
formation, such result indicating that a signature related information flows from or to the provider(s). The signer
to the original message m has been authenticated. can "link" the things received for signing ti with the
Several possible properties of blind signature systems things known to have the signature property (m'), if
will be described in accordance with the teachings of and only if he can determine with certainty for every
the present invention. 30 element of (m'), the unique ti which corresponds with
One general property of a blind signature scheme is the same message n, under the assumptions above. If
that the blinding transformation should make it difficult, nothing at all can be known about the correspondence,
if not impossible, to determine the message m with under the assumptions above, not even associating dif
certainty from the transformed message t without key k. ferent probabilities with different correspondences,
For the purposes of the present description, this prop 35 then the blind signature system may be said to be "com
erty will be referred to as "hiding', and thus it may be pletely unlinkable.” The term “blinded” may be used to
said that the blinding transformation hides the message. indicate that it is not usually easy to completely link.
In the preferred embodiment, as mentioned earlier, the For example, one m' and one t may be said to be blinded
blinding transformation includes multiplying modulo in from each other without k, if it cannot usually easily be
by ke. Ife is non-zero and fixed and coprime with d(n), determined without k that the two correspond.
and k is chosen from the interval 0 to n-1, then the In the preferred embodiment, as mentioned earlier
signing function g(k)=ke (mod n) is one-to-one and and to be described in detail, it is believed to be possible
onto. If m is coprime with n, then h(m)=g(k)xm (mod to come close to, or in some cases under certain assump
n) is one-to-one and onto. Thus, under the assumptions tions even achieve, complete unlinkability. A possible
of propere, and m coprime with n, a particular value of 45 explanation for this might be that for each possible way
t could correspond with any value of m, with unique to put the 1 items into correspondence, there could exist
suitable k. In a sense then, it is believed that, the security a unique set of values for the keys ki, such that this
of the hiding in the blinding transformation of the pre would be the true correspondence, but assuming each k
ferred embodiment is comparable to that of the so called is chosen so that all values are equally likely, all possible
one-time pad, when GCD(m,n)= GCD(edb(n))=1, and 50 correspondences are equally likely. (Of course the ques
k chosen uniformly from the interval 0 to n-1. Of tion of actual generation of random numbers from a
course, if e is not coprime with d(n) then certain mes perfectly uniform distribution is beyond the scope of the
sages may have no signature; and if it is likely that m is present description.) It is believed that one possible
not coprime with n, then it is likely that someone can explanation of this may be seen by considering the posi
guess a factor of n, or providers could use Euclid's 55 tion of the signer as follows. He has two sets of values:
algorithm to reject any non-coprime m. {t}, and (m'). If he assumes that tycorresponds with
Another property of a blind signature scheme which m", then he can determine the unique k which would
may be important in some anticipated applications will have been used to form ty. This may be accomplished by
be called "conservation of signatures'. This property solving the congruence tyx k=m'u' (mod n), for ky. To
requires that it not usually be easy for someone to con 60 do this, one may first compute the multiplicative inverse
struct a set of transformed messages such that after each of nu modulo n, and assuming that m and n are coprime,
member of the set is signed, more authenticatable signa as mentioned earlier, there is a unique such value. Then
tures can be derived than original members of the set the unique product of this value and ty is formed, mod
were signed. The preferred embodiment, as mentioned ulo n. Finally, the result is raised to the d power modulo
earlier and to be described in detail, is believed to have 65 n, producing a unique result, assuming that e is coprime
this property in practice, when suitable signature au with d(n). Thus, under the assumptions, for every possi
thentication techniques are used, such as when a strong ble way the two sets could be linked, there exists unique
one-way function of suitably large range and domain is choices for the keys ki that would make this the true
4,759,063 10
linking, and, as mentioned above, since the k's are by features, however, in some anticipated applications.
assumption chosen from a uniform distribution, all such Consider the case where one party holds k1 and a sec
choices for the keys k are equally likely, and so all ond holds k2. Both parties become mutually dependent
possible linkings are equally likely. This concept is fur once the signature transformation has been made: the
ther illustrated by numerical examples as will be pres 5 first party requires the cooperation of the second to
ented in the detailed description of the preferred en transform t'12 into m'; similarly, the second party re
bodiment. quires the cooperation of the first to transform t' into
Referring now to FIG. 2, several exemplary modes of m". In the embodiment described above, the second
use in accordance with the teachings of the present party can check that the signer 223 has performed the
invention will be presented. 10 proper function, by checking that ti2=t'12 (mod n).
FIG. 2a shows a mode of use with only a single cryp The first party is in a position to check the signature
tographic blinding and corresponding cryptographic function performed by signer 223 by checking that
unblinding transformation, as mentioned earlier. The t1=t'1' (mod n), but this function is also available to the
message m is transformed by cryptographic blinding single provider party in a single non-signer party mode
transformation 203 into transformed message t, which is 15 of use, but it is anticipated that the signature would
input to signature transformation 202, which transfor normally be checked by the single party by checking
mation depends on secret signing information, now that msn'e (mod n). Notice also that the communica
shown for clarity. The output of the signing transforma tion between the second party and signer 223 in the
tion, t', is input to the unblinding transformation 204, present mode is obscured from the first party. For ex
which transformation depends on key k, and which 20 ample, the second party may be second party to several
transformation produces output m', bearing a signature first parties, and they may not know which of the com
propety related to them. (Notice that blinding transfor munications with signer 223 include their particular
mation 203, signature transformation 202 and unblind values of m. Similarly, the second party may obscure
ing transformation 204 of FIG. 2a correspond with from the signer which of the communications with first
blinding transformation 103, signature transformation 25 party(s) correspond to particular signature transforma
102 and unblinding transformation 104 of FIG. 1, re tions made by signer 223. In some embodiments, such as
spectively.) the preferred embodiment, it may even be the case that
Referring now to FIG. 2b, a first mode of use in cooperation between the first party and signer 223 to
shown with two cryptographic blinding transforma determine the correspondence between communica
tions, two cryptographic unblinding transformations, 30 tions known to one and communications known to the
and two separate keys for these transformations. The other can be thwarted by the second party.
original message m is transformed by blinding transfor Of course the present discussion can readily be gener
mation 221, which transformation depends on key kil, alized to a use based on a plurality of provider parties--
producing output shown at t1, and then supplied as not just two or fewer non-signer parties. In a multiple
input to blinding transformation 222, which transforma 35 provider party use based on the preferred embodiment:
tion depends on key k2, and whose output shown as t1,2. each party performs transformations just as if they were
Signing transformation 223 takes this multiply trans in a single or two non-signer party use as described
formed message as input and produces, in a way de herein; parties may readily check that the signature
pending on secret signing information, not shown for property has been properly applied and transferred by
clarity, output shown as t'12. This output is shown as 40 the signer and those parties on the signer's side; and any
input to unblinding transformation 224, which depends intermediary party is able to thwart attempting linking
on key k2, and produces output shown as t'1. This out even by cooperation of all other parties.
put is input to unblinding transformation 225, which Referring now to FIG. 2c, a second mode of use is
depends on key kl, and which produces output shown shown with two cryptographic blinding transforma
as n' retaining a digital signature property related to m. 45 tions, two cryptographic unblinding transformations,
In one use of this mode based on the preferred em and two keys for these transformations. The original
bodiment, described earlier and to be described in de message m is transformed by blinding transformation
tail, the following congruences might hold: 231, which transformation depends on key ki, produc
50
ing output shown as t1and then supplied as input to
blinding transformation 232, which transformation de
pends on key k2, and whose output is shown as t1,2.
Signing transformation 233 takes this multiply trans
formed message as input and produces, in a way de
pending on secret signing information, not shown for
55 clarity, output shown as t'12. This output is shown as
input to unblinding transformation 234, which depends
m's r'1x k1-1=nd (mod n), on key k1, and produces output shown as t'2. This out
put is input to unblinding transformation 235, which
and the checking function can be based on the congru depends on key k2, and which produces output shown
ence m'esm (mod n). Thus, the blinding transformation 60 as m', retaining a digital signature property.
221 and 225 as well as the unblinding transformation 222 In one embodiment of this mode of use based on the
and 224 are each nearly the same as in the single key preferred embodiment, described earlier and to be de
mode of the preferred embodiment to be described in scribed in detail, the following congruences might hold:
detail.
If only a single party with access to both keyski and 65 t1= mx k1 (mod n),
K2 uses this mode, then it may be equivalent to a single
key use, as in the preferred embodiment. The present t2=st X k2 (mod n),
mode may have additional benefits, advantages and
4,759,063
11 12
r1.2=t2=mix kixk (mod n), the exponentiator 124, in this embodiment, is the digital
r2=t2x k1 = mxk (mod n), signature of its input base from line 155, and appears on
line 157, which is input to modular multiplier 125. The
other multiplicand input to multiplier 125 appears on
line 158, which is the output of modular inverter 126,
and the checking function can be based on the congru such modular inverters to be described. The modular
ence m'e =m (mod n). Thus, the blinding transforma inverter takes its input from the key source 123 men
tion 231 and 235 as well as the unblinding transforma tioned earlier as line 153. The product output of modu
tion 232 and 234 are each nearly the same as in the single 10 lar multiplier 125 appears on line 159, which is base
key mode of of the preferred embodiment to be de input to modular exponentiator 127. The power input to
scribed in detail. exponentiator 127 is shown as e on line 160. The output
Again, little advantage may result if one party uses of exponentiator 127 is shown as m on line 161.
two separate keys. The present mode may have addi The operation of the preferred embodiment shown in
tional benefits, advantages and features, however in 15 FIG. 1 will now be described in detail. A message m is
some anticipated applications. Consider the case where obtained on line 151 by the provider. A key on line 153,
one party hold k1 and a second holds k2, as before. In denoted ask, preferably secret to the provider, is devel
the earlier described first two provider mode of use, the oped by key source 123, and is preferably chosen from
second party could cheat the first party by simply dis the interval 0 to n-1 with each value as nearly equally
carding t1 and supplying some t2 of the second parties' 20 likely as practical. The blinding transformation 103
choice to signer 223. Then the second party could un takes these two inputs, lines 151 and 153, and forms a
blind the resulting t'2 received from signer 223, and blinded message denoted as ton its output line 155, such
obtain the signature property on something chosen only
by the second party, leaving the first party without the that t=mxke (mod n). These functions of the blinding
transformation 103 are accomplished as follows. Modu
expected message bearing the signature property. In the lar exponentiator 122 takes the key k as its base input
present mode, however, if the signer only signs t1,2 from line 153 and takes
25
the public signature key e from
when supplied by the second party, and returns the t'12 line 154, and outputs on line 152 a value congruent
only to the first party, then neither party can cheat the modulo n to ke. Modular multiplier 121 takes this value
other.
from line 152 and forms
Of course both modes shown with two non-signer input m from line 151, and the productthe modulo n product with the
parties can readily be generalized in combination: a on line 155.
30 output appears
message travels through one permutation of the parties Now the signer 102 may obtain the blinded message t
on the way to the signer and through a possibly differ
ent permutation on the way back. The no linking prop from line 155, and will normally output a digital signa
erty is believed to still hold for any single intermediary ture oft on line 157, this output denoted as t', such that
party; the no cheating property holds for a party if no 35 t'=t (mod n), where d is the secret signing exponent of
cheating party is between the party and the signer in at the signer mentioned earlier. These functions of the
least one direction. signer 102 are accomplished as follows modular ex
ponentiator 124 takes its base input from line 155, takes
DETAILED DESCRIPTION OF PREFERRED its power input from line 156, and its output appears on
EMBODIMENT line 157.
Turning now to FIG. 1, a detailed descripton of a Now the provider may perform the unblinding trans
preferred embodiment of the present invention is pres formation, shown as 104. The output of the signer, t',
ented. One party to the system will be referred to as the and the secret key k are inputs to this function and it
"provider', shown as contained in the dashed box. 101. produces, in this embodiment, a digital signature on m,
Another distinguished party in the system is the 45 denoted m', such that m'=md (mod n). This function of
"signer', shown as contained within dashed box 102. A the unblinding transformation is performed as follows.
key source for developing a secret key, preferably con The multiplicative inverse of the secret key k is formed
fidential to the provider, is shown contained within the by the modular inverter 126. Then the produce modulo
provider 101. A secret signing key, d, is shown con n of the multiplicative inverse, shown as kil, and the
tained within signer 102. The provider also contains the 50 signed blinded message t' from line 157 is formed by
ability to perform two transformations. A "blinding' modular multiplier 125, and its output appears on line
transformation 103 and an "unblinding' transformation 159.
104: a checking function 105 is also shown. At some latter time, one or more parties may wish to
The message appears on line 151 as one multiplicand check or authenticate the digital signature m' on the
input to modular multiplier 121, such multipliers to be 55 original message m. This function may be performed by
described. The other multiplicand input to modular checking that m=m', and that m is a valid message, as
multiplier 121 is from line 152, which is the output of described earlier. This function can be performed by the
modular exponentiator 122, such modular exponentia modular exponentiator 127, which takes its base input
tors to be described. The base input to exponentiator from line 159 and its power input from line 160, and
122 appears on line 153, and is the key output from key 60 whose output appears on line 161. A specific example of
source 123, such key sources described earlier. The further checking for valid messages or the like is not
exponent, or as used equivalently herein, the power shown for clarity, but such techniques would be obvi
input to exponentiator 122 is from line 154, and is the ous from the earlier description, and are well known to
public signature exponent shown as e. The product those of ordinary skill in the art. For example, the bi
output of multiplier 121 appears on line 155, which line 65 nary representation of the value on line 161 could be
is the base input to modular exponentiator 124. The split into two halves, and the number considered valid if
exponent to exponentiator 124 is the secret signing key the result of comparing the two halves indicates they
shown as d, which appears on line 156. The output of are identical.
4,759,063 14
13
The following table illustrates the operation of one Euclid's algorithm, and is well known in the art. See
use of the preferred embodiment by associating the Knuth, D. E., "The Art of Computer Programming:
various line numbers in the first row and their symbolic Volume 2/Seminumerical Algorithms,” Addison-Wes
names in the second, with the exemplary values in the ley, 1969, Euclid's algorithm, page 297, exercise 4.5.2
remaining nine data rows. The table uses an RSA sys #15 on page 315, and answer to exercise 4.5.2 #15 on
tem based on primes 29 and 31 chosen by the signer. page 523. Initially register 302 contains n, register 301
The modulus made public by the signer would then be contains the input from line 351, register 306 contains 1,
n=29x31=899. The signer is assumed to have chosen and register 307 contains 0. The operation proceeds
e to be 17, (possibly after checking that synchronously by clock pulses sufficiently spaced to
GCD(17,6(n))=1) and computed its multiplicative in 10 allow all lines to settle between pulses. Clock pulses
verse modulo (b(n)=(29-1)x (31-1)=840, and with occur until the first time that the contents of register 301
the result d=593. Of course such a system is based on are 0. The clock and associated lines, as well zero detec
numbers far too small to be secure. (Finding k1 for the tor for register 301, are not shown for clarity, but would
value of k in the first data row is the subject of an exam be obvious to those skilled in the art from the present
ple of the operation of the modular inverter to be de 15 description. Before the first clock pulse and after each
scribed.) Notice that the first and second data rows clock pulse, divider 303 divides the contents of register
have the same t values as the penultimate and last data 302 by the contents of register 301 and supplies the
rows respectively, but that their messages m are inter
changed with different values ofk, as mentioned earlier. quotient
the
to modular multiplier 304 and the remainder to
register 301. Once the quotient value settles, modu
20
lar multiplier 304 forms the modulo n product of the
quotient and the contents of register 306, and supplies
15 153 152 155 157 158 159 the product as the minuend input to modular subtractor
k ke t t k-l m 305. Once the product value settles, modular subtractor
628
254
255
685
886
84
826
659
19
698
691
21
543
274 25 305 subtracts modulo n the product from the contents of
40 393 210 309 340 716 710
register 307 and supplies the difference to an input of
53 440 212 72 54 615 85 register 306. With the rising edge of each clock pulse,
755 748 16 393 110 256 291 register 302 latches in new contents from line 352, and
623
724
111
308
107
461
135
235
60
69
81
108
135
260
register 307 latches in new contents from line 360. Dur
254 548 520 826 19 251 274 30 ing the falling edge of each clock pulse, register 301
628 94 807 659 698 373 543 latches in new contents from line 356, and register 306
latches in new contents from line 358. The duration of
Referring now to FIG. 3, a detailed description of an each clock pulse is short enough that the output of
exemplary embodiment of a modular multiplicative modular subtractor 305 and the remainder output 356 of
inverter, herein called a modular inverter, is presented. 35 dividerof303 do not change between the rising and falling
The number to be inverted appears on line 351, and is edge a clock pulse.
The following table illustrates the operation of the
initially loaded into register 301. The output of register modular inverter by showing the contents of the vari
301 appears on line 352, which is input to register 302, ous registers at the end of each cycle. Cycles #0 shows
which takes its initial value, the modulus n, from line the initial state; and as can be seen from the first row,
353, and has output on line 354. Ordinary arithmetic the number whose inverse is sought is 255, initially in
divider 303 takes its dividend from line 354 and its divi
sor from line 352; its quotient output appears online 355 302.register 301; the modulus n is 899, initially in register
and its remainder output appears on line 356. Such bi As can be seen from the row of cycle #6, the result
nary arithmetic dividers for unsigned integers are well in register 307 is 691.
known in the art, for example see K. Hwang, "Com 45
puter Arithmetic: principles, architecture, and design' register number
John Wiley, 1979, Chapter 7. Line 356 is input to regis cycle 301 302 306 307
ter 301, described earlier. Line 355 is input to modular #0 255 899 1 O
multiplier 304, such multipliers to be described. The #1 134 255 896 1
output of modular multiplier 304 is line 357, which is 50 #2 21 34 4 896
subtrahend input to modular subtractor 305, such sub i3
#4
13
4
121
13
892
67
4.
892
tractors to be described. The difference output of modu #5 1 4 69 67
lar subtractor 305 is line 358, which is input to register ió O 1 0 691
306, which takes its initial value of 1 from line 359 and
whose output appears on line 360. Modular multiplier 55
304 already described takes one of its multiplicand in Turning now to FIG. 4, a detailed description of an
puts from line 360. Register 307 takes input from line exemplary embodiment of a modular exponentiator is
360, takes its initial value of 0 from line 361, and its presented for completeness. The base input appears on
output appears on line 362. Line 362 is minuend input line 451, which is an initial input to register 401. The
for modular subtractor 305 already described, and is the output of register 401 appears online 452, which is both
output of the modular inverter. multiplicand inputs to modular multiplier 402, to be
A detailed description of the operation of the modu described. The output of modular multiplier 402, line
lar inverter of FIG. 3 is now presented. The modular 453, is the data intput to register 401. The output of
inverter takes an input from line 351 whose value is register 401, line 452, is one multiplicandinput to modu
between 0 and n-1, and produces on the output line 65 lar multiplier 403. The product output of modular mul
362 a value between 0 and n-1 which is congruent to tiplier 403 appears on line 454 and is a data input for
the multiplicative inverse modulo n of the value input. register 404. The initial value for register 404 is 1 and is
The principle of operation is based on a variation of shown on line 455. The contents of register 404 appear
4,759,063
15 16
on line 456, which is input to modular multiplier 403 its output on line 558, which line enables the latching
and also output of the modular exponentiator. The ex function of register 504, to be described.
ponent input appears on line 457 and is initial data input A detailed description of the operation of the exem
for ordinary right-shifting binary shift register 405. The plary modular multiplier of FIG. 5 is now presented,
rightmost bit of shift register 405 appears as its output 5 The modular multiplier takes two multiplicands, one
on line 458, which line enables the latching function of from each of lines 551 and 557, each represented as a
register 404, to be described. value between 0 and n-1, and produces on its output
A detailed description of the operation of the exem line 503 a value between 0 and n-1 that is congruent
plary modular exponentiator of FIG. 4 is now pres modulo n to the product of the multiplicands. The prin
ented. The modular exponentiator takes two inputs, a O ciple of operation is to form the sum of one multiplicand
base from line 451 (represented as a value between 0 and multiplied by all powers of two that correspond with
n-1) and a power from line 457 (a positive binary inte set bits in the other multiplicand. (Notice, for example,
ger), and produces on its output line 456 a value be that 21-20+-22+24, and
tween 0 and n-1 that is congruent modulo n to the base 15 13x21 = 13x20-13x22--13x24=273.) Initially, the
raised to the power. The principle of operation is to multiplicands are in registers 501 and 505, and register
form the product of the base raised to all powers of two 504 is reset to zero. The operation proceeds in 1 cycles,
that correspond with set bits in the exponent. (For ex where 1 is the number of bits used to represent numbers
ample, notice that 21=20-22-24, and between 0 and n-1. At the end of each of the 1 cycles
521=5x522x52=476837158203125.) Initially, the base 20 a clock line (not shown for clarity) is raised briefly from
and exponent are in registers 401 and 405 respectively, the Zero state to the one state and then returned to the
and register 404 is reset to one. The operation proceeds Zero state. During the first cycle, the contents of regis
in 1 cycles, where 1 is the number of bits used to repre ter 501 is doubled (modulo n) by modular adder 502 and
sent numbers between 0 and n-1. At the end of each of appears on line 553, and the modulo n sum of the con
the 1 cycles a clock line (not shown for clarity) is raised 25 tent of register 501 and register 504 is developed by
briefly from the zero state to the one state and then modular adder 503 and appears on line 554. At the end
returned to the zero state. During the first cycle, the of the first cycle, on the rising edge of the first clock
contents of register 401 is squared (modulo n) by modu pulse, the value on line 553 is latched into register 501,
lar multiplier 402 and appears on line 453, and the mod the value on line 554 is latched into register 504 only
ulo n product of the content of register 401 and register 30 when the enabling value on line 558 is a one bit, and on
404 is developed by modular multiplier 403 and appears the falling edge of the clock the content of register 505
on line 454. At the end of the first cycle, on the rising is shifted one bit to the right. During each of the 1-1
edge of the first clock pulse, the value on line 453 is subsequent cycles, the new sums settle on lines 553 and
latched into register 401, the value online 454 is latched 554, and at the end of the cycle, with the rising edge of
into register 404 only when the enabling value on line 35 the clock, the value on line 553 is latched into register
458 is a one bit, and on the falling edge of the clock the 501, and the value online 554 is latched into register 504
contents of register 405 is shifted on bit to the right. if and only if line 558 has the enabling value of a one bit;
During each of the 1-1 subsequent cycles, the new with the falling edge of the clock, the contents of regis
products settle on lines 453 and 454, and at the end of ter 505 is shifted one bit to the right. Thus, after the fall
the cycle, with the rising edge of the clock, the value on 40 of the 1th (final) clock pulse, all the original bits of
line 453 is latched into register 401, and the value online register 505 have been shifted out, register 501 contains
454 is latched into register 404 if and only if line 458 has a number congruent modulo n to the value on line 551
the enabling value of a one bit, and with the falling edge doubled 1 times, and the content of register 504 is the
of the clock, the contents of register 405 is shifted one desired value and is on the output line 556 of the modu
bit to the right. Thus, after the fall of the clock pulse 1, 45 lar multiplier.
the last clock pulse, all the original bits of register 405 Referring now to FIG. 6, a detailed description of an
have been shifted out, register 401 contains a number exemplary embodiment of a modular subtractor is pres
congruent modulo n to the value on line 451 squared 1. ented for completeness. The subtrahend to the modular
times, and the content of register 404 is the desired subtractor is on line 651, which is the subtrahend to
value and is on the output line 456 of the modular ex 50 ordinary arithmetic subtractor 601, such ordinary arith
ponentiator. metic binary subtractors with positive integer inputs
Referring now to FIG. 5, a detailed description of an being well known in the art. The minuend input to
exemplary embodiment of a modular multiplier is pres subtractor 601 is on line 652 and is the modulus n. The
ented for completeness. One multiplicand input appears result of the ordinary subtractor 601 appears on line
online 551, which is an input to register 501. The output 55 653. Modular adder 602, to be described, takes the dif
of register 501 appears on line 552, which is both ad ference from line 653 and the minuend for the modular
dend inputs to modular adder 502, to be described. The subtractor from line 654, and produces the modulo n.
output of modular adder 502, line 553, is an input to sum as its output on line 655.
register 501. The output of register 501, line 552, is one The detailed operation of the modular subtractor of
addend input to modular adder 503. The sum output by 60 FIG. 6 is now described. Its input are numbers between
modular adder 503 appears on line 554 and is a data 0 and n-1 and it produces a number between 0 and
input for register 504. The initial value for register 504 n- 1 which is congruent to the difference of the input
is 0 and is shown on line 555. The contents of register numbers modulo n. A number congruent to the additive
504 appear on line 556, which is input to modular adder inverse modulo n of the subtrahend from line 651 is
503 and also the output of the modular multiplier. The 65 developed by subtractor 601, by subtracting from n, and
second multiplicand input appears on line 557 and is transmitted by line 653 to modular adder 655, and then
data input for ordinary right-shifting binary shift regis added modulo n to the minuend on line 654, producing
ter 505. The rightmost bit of shift register 505 appears as the result on line 655.
4,759,063 18
17
Referring now to FIG. 7, a detailed description of an produce a corresponding plurality of digital second
exemplary embodiment of a modular adder is presented messages;
for completeness. The two numbers to be added are unblinding said plurality of second messages by said
supplied on lines 751 and 752, which are the summand supplier parties transforming each at least partially
inputs to ordinary binary adder 701, such ordinary bi responsive to said first keys to produce a corre
nary arithmetic adders being well known in the art. The sponding plurality of digital third messages which
output of adder 701 is supplied by line 753 to the subtra retain a public key digital signature property re
hend input to ordinary binary subtractor 702. The minu lated to said original messages and to said signing
end supplied subtractor 702 on line 754 is the modulus in 10 saidstep; and
blinding step being performed by said supplier
for the modular addition. The result of the ordinary parties using said first keys so as to make said signer
subtraction by subtractor 702 appears online 755. Ordi party without the corresponding first keys unable
nary binary comparator 703, such comparators being to readily determine the correspondence between
well known in the art, takes one comparend input from individual messages within said plurality of third
line 753 and the other comparend from line 756, which messages and individual messages within said plu
is the modulus n, and develops a single output bit indi rality of first messages.
cating the result of the comparison, which output ap
pears on line 757. Selector 704 takes its two data inputs any2. atAleast
method as in claim 1 wherein, for substantially
two of said original messages, there exist at
from lines 755 and 753, and its control input from line
757, has output on line 758, the output of the modular 20 least two possible choices of said corresponding first
keys that would produce the same said first messages
adder, and outputs data from line 753 if comparator and where the different choices would produce differ
output 757 indicates that data value on line 753 is less ent correspondences between the original messages and
than the data value on line 756, and outputs data from the first messages.
line 755 otherwise.
The operation of the exemplary modular adder of 25 ity3.distribution
A method as in claim 1 wherein there is a probabil
for independently choosing said first
FIG. 7 will now be described in detail. The modular keys so that it is substantially impossible for said signer
adder takes two numbers between 0 and n, not both n, party to learn substantially anything about which of said
and produces as output a third numbers between 0 and first messages corresponds with which of the second
n-1 which is congruent to the sum of the inputs mod messages based upon (a) the first messages correspond
ulo n. Two numbers to be added modulo n appear on 30 ing to at least two such keys, (b) the third messages
lines 751 and 752 and are added by ordinary arithmetic corresponding to the at least two keys, and (c) said
producing a sum on line 753. The sum is subtracted signer party's secret signing key, all taken together.
from n by subtractor 702 with the result online 755. The 4. A method as in claim 3 wherein said first keys are
sum is compared with n by comparator 703, with the substantially independently chosen from substantially
result on line 757. If the comparison indicates that the 35 said probability distribution.
sum is less than n then the sum is between 0 and n-1 5. A method as in claim 1, 2, 3 or 4 further comprising
and is output on line 758; otherwise the sum is at most in the step of transferring at least one of said first messages
too large, and the difference of the sum and n from line from the corresponding said supplier party to said
755 is output on line 758. signer party.
While these descriptions of the present invention 6. A method as in claim 1, 2, 3 or 4 further comprising
have been given as examples, it will be appreciated by the step of transferring at least one of said second mes
those skilled in the art that various modifications, alter sage from said signer party back to the corresponding
nate configurations and equivalents may be employed said supplier party.
without departing from the spirit and scope of the pres 7. A method for processing a plurality of original
ent invention. 45 digital messages before they receive public key digital
What is claimed is: signatures and for processing the resulting messages
1. A method for processing a plurality of original after they have received the public key digital signa
digital messages by plural provider parties before they tures where said processed digital messages are consid
are transformed with public key digital signatures by a ered to be "blinded' and said resulting digital messages
signer party and for processing the resulting messages 50 to be “unblinded' because, although the public key
by the corresponding provider parties after they have ditial signatures of said resulting digital messages are
been transformed with the public key digital signatures checkable using a public key, even possession of the
where said processed digital messages are considered to public key and of the corresponding secret signing key
be "blinded' and said resulting digital messages to be does not readily allow the correspondence between the
"unblinded” because, although the public key digital 55 elements of said processed digital message set and the
signatures of said resulting digital messages are check elements of the corresponding said resulting digital
able using a public key, the signer is unable to determine message set to be determined, said method for process
the correspondence between elements of said processed ing comprising the steps of:
digital message set and elements of the corresponding blinding a plurality of original digital messages by
said resulting digital message set, said method for pro 60 transforming each responsive to a corresponding
cessing comprising the steps of: first key to produce corresponding digital first
blinding a plurality of original digital messages by a messages;
plurality of corresponding supplier parties trans signing each of said first messages by applying a pub
forming each such message at least partially re lic key digital signature transformation thereto,
sponsive to a corresponding first key to produce 65 using at least a secret signing key, to produce a
corresponding digital first messages; corresponding plurality of digital second messages;
signing each of said first messages by a signing party unblinding said plurality of second messages by trans
applying a public key digital signature thereto to forming each, at least partially responsive to said
4,759,063
19 20
first keys, to produce a corresponding plurality of receiving corresponding said second messages by said
signed digital third messages related to said original supplier parties and transforming the correspond
messages and where the digital signature property ing second messages with said first keys to produce
derives from said secret signing key; and corresponding unblinded third digital messages
said blinding step being performed using separate said each having a digital signature property related to
first keys so as to make substantially computation a corresponding one of said original messages
ally infeasible substantial linking, even using said thereby making it infeasible for the signer party to
secret signing key, of individual messages within link said first messages with the third messages,
said plurality of third messages to individual mes without the first keys;
sages within said plurality of first messages. 10 receiving at least one of said third messages by a
8. A method as in claim 7 wherein, for substantially checker party, and the checker party checking a
any at least two of said original messages, there exists at public key digital signature related to the corre
least two possible choices for said corresponding first sponding said original message; and
keys that would produce the same said first messages maintaining a record depending on said previously
and where the different choices would produce differ 15 checked third messages and preventing a signature
ent correspondences between the original messages and related to the same such third message from being
the first messages. accepted more than once, and providing value in
9. A method as in claim 7 wherein there is a probabil exchange for said signatures accepted.
ity distribution for independent choice of said first keys 15. A method as in claim 1, 2, 3, 4, 7, 8, 9, 10 or 14
so that substantially all pairs of individual said first 20 wherein:
messages and individual said third messages are substan said blinding step includes forming a product of at
tially equally likely to correspond, thereby providing least one of said original messages and a blinding
substantially complete unlinkability. factor derived from a corresponding one of said
10. A method as in claim 9 wherein said first keys are
chosen substantially independently from substantially 25 saidfirst keys; and
unblinding step includes forming a product of the
said probability distribution and used in said blinding corresponding said second message with a multipli
and unblinding steps. cative inverse of a signed form of said first key, in
11. A method as in claim 1, 2, 3, 4, 7, 8, 9 or 10 further a finite structure where such multiplication and
comprising the step of checking the public key digital multiplicative inverses are defined.
signature property of at least one of said third messages. 30
12. A method as in claim 11 further comprising the step of checking theinpublic
16. A method as claim 15 further comprising the
key digital signature prop
step of transferring a said third message to a party for erty of at least one of said third messages.
performing said checking. 17. A method as described in claim 15 wherein:
13. A method as in claim 11 further comprising the said blinding step transforms original messages mi
steps of: 35 using first keys ki to produce first messages ti de
retaining a record responsive to valid said third mes scribed by
sages checked; and
searching said record to determine when the same ti=miki (mod n)
said third message has been recorded previously.
14. A method for providing untraceability of value where is is a public signing exponent, and n is a public
transfers by processing a plurality of original digital key digital signature modulus;
messages before they receive public key digital signa said signing step transforms said first messages ti using
tures and for processing the resulting messages after secret signing key d to produce second messages ti
they have received the public key digital signatures described by
where said processed digital messages are considered to 45
be "blinded” and said resulting digital messages to be
"unblinded' because although the public key digital
signatures of said resulting digital messages are check said unblinding step transforms said second messages
able using a public key, even possession of that public t’i using first keyski to produce said third messages
key and of the corresponding secret signing key is sub 50 m" described by
stantially insufficient to substantially feasibly determine
the correspondence between the elements of said pro
cessed digital message set and the elements of the corre
sponding said resulting digital message set, said method 18. A method as in claim 17 further comprising the
for processing comprising the steps of: 55 step of checking the public key digital signature prop
blinding at least part of each of a plurality of digital erty of at least one of said third messages m'i including
original messages responsive to first keys to pro exponentiation to the power e.
duce corresponding blinded first digital messages, 19. A method for processing original digital messages
by each of plural supplier parties; before they receive public key digital signatures and for
receiving said first messages, by a signer party, and 60 processing the resulting messages after they have re
the signer party transforming at least two of said ceived the public key digital signatures where said pro
first messages, at least partially responsive to sign cessed digital messages are considered to be "blinded'
ing secret key information of said signer party, to and said resulting digital messages to be "unblinded'
produce second digital messages; because, although the public key digital signatures of
providing the corresponding said second messages to 65 said resulting digital messages are checkable using a
at least two corresponding said supplier parties in public key, even possession of the public key and of the
exchange for a transfer of value from such corre corresponding secret signing key does not readily allow
sponding supplier parties; the correspondence between elements of said processed
4,759,063 22
21
digital message set and elements of the corresponding the different choices would produce different corre
said resulting digital message set to be determined, said spondences between the original messages and the first
method for processing comprising the step of . messages.
transforming at least part of a first input with a first 22. Apparatus as in claim 20 wherein said means for
blinding transformation depending on a first secret 5 blinding operates such that there is a probability distri
key to produce a first output; bution for independently choosing said first keys so that
receiving said first output and transforming said first it is substantially impossible for said signer party to
output with a second blinding transformation de learn substantially anything about which of said first
pending on a second secret key to produce a sec messages corresponds with which of the second mes
ond output; 10 sages based upon (a) the first messages corresponding to
receiving said second output and developing a third at least two such keys, (b) the third messages corre
output at least partially responsive to the second sponding to the at least two keys, and (c) said signer
output and to a secret signing key; party's secret signing key, all taken together.
receiving said third output and transforming the third 23. Apparatus as in claim 22 wherein said means for
output with a first unblinding tranformation, de 15 blinding includes means for substantially independently
pending on a first one of said first and second secret providing said first keys from substantially said proba
key, to produce a fourth output; and bility distribution.
transforming said fourth output with a second un 24. Apparatus as in claim 22, 21, 22 or 23 further
blinding transformation, depending on the remain comprising means for transferring at least one of said
ing one of said first and second secret keys, to 20 first messages from the corresponding said supplier
produce a fifth output, and the fifth output retain party to said signer party.
ing a digital signature property related to said first 25. Apparatus as in claim 22, 21, 22 or 23 further
input, and said third and the fifth outputs being not comprising means for transferring at least one of said
readily linkable without the first and second secret second messages from said signer party back to the
keys. 25 corresponding said supplier party.
20. Apparatus for processing a plurality of original 26. Apparatus for processing a plurality of original
digital messages by plural provider parties before they digital messages before they receive public key digital
are transformed with public key digital signatures by a signatures and for processing the resulting messages
signer party and for processing the resulting digital after they have received the public key digital signa
messages by the corresponding provider parties after 30 tures where said processed digital messages are consid
they have been transformed with the public key digital ered to be "blinded' and said resulting digital messages
signatures where said processed digital messages are to be "unblinded' because, although the public key
considered to be "blinded' and said resulting digital digital signatures of said resulting digital messages are
messages to be “unblinded' because, although the pub checkable using a public key, even possession of the
lic key digital signatures of said resulting digital mes 35 public key and of the corresponding secret signing key
sages are checkable using a public key, the signer is does not readily allow the correspondence between the
unable to determine the correspondence between ele elements of said processed digital message set and the
ments of said processed digital message set and elements elements of the corresponding said resulting digital
of the corresponding said resulting digital message set, message set to be determined, said apparatus for pro
said apparatus for processing comprising: cessing comprising:
means for blinding a plurality of original digital mes means for blinding a plurality of original digital mes
sages by a plurality of corresponding supplier sages by transforming each responsive to a corre
parties transforning each such message at least sponding first key to produce corresponding digital
partially responsive to a corresponding first key to first messages;
produce corresponding digital first messages; 45 means for signing each of said first messages by ap
means for signing each of said first messages by a plying a public key digital signature thereto, using
signing party applying a public key digital signa at least a secret signing key to produce a corre
ture thereto to produce a corresponding plurality sponding plurality of signed digital second mes
of digital second messages; Sages;
means for unblinding said plurality of second mes 50 means for unblinding said plurality of signed second
sages by said supplier parties transforming each at messages by transforming each, at least partially
least partially responsive to said first keys to pro responsive to said first keys, to produce a corre
duce a corresponding plurality of digital third mes sponding plurality of signed digital third messages
sages which retain a public key digital signature related to said original messages and where the
property related to said original messages and to 55 digital signature property derives from said secret
said means for signing; and signing key; and
said means for blinding by said supplier parties in said means for blinding using said first keys so as to
cluding means for using said first keys so as to make make substantially computationally infeasible sub
said signer party without the corresponding first stantial linking, even using said secret signing key,
keys unable to readily determine the corresponding of individual messages within said plurality of third
between individual messages within said plurality messages to individual messages within said plural
of third messages and individual messages within ity of first messages.
said plurality of first messages. 27. Apparatus as in claim 26 wherein said means for
21. Apparatus as in claim 20 wherein said means for blinding operates so that, for substantially any at least
blinding operates so that, for substantially any at least 65 two of said original messages, there exists at least two
two of said original messages, there exist at least two possible choices for said corresponding first keys that
possible choices of said corresponding first keys that would produce the same said first messages and where
would produce the same said first messages and where the different choices would produce different corre
23
4,759,063
24
spondences between the original messages and the first messages thereby making it infeasible for the signer
messages. party to link said first messages with the third mes
28, Apparatus as in claim 26 wherein said means for sages, without the first keys;
blinding operates so that there is a probability distribu means for receiving at least one of said third messages
tion for independent choice of said first keys so that by a checker party and the checker party checking
substantially all pairs of individual said first messages a public key digital signature property related to
and individual said third messages are substantially the corresponding said original messages; and
equally likely to correspond, thereby providing substan means for maintaining a record depending on said
tially complete unlinkability. previously checked third messages and preventing
29. Apparatus as in claim 28 wherein said means for 10 a signature related to the same such third messages
blinding uses first keys substantially independently from being accepted more than once, and for pro
chosen substantially from said probability distribution. viding value in exchange for said signatures ac
30. Apparatus as in claim 20, 21, 22, 23, 26, 27, 28 or cepted.
29 further comprising means for time delaying messages 36. Apparatus as in claim 35 further comprising
disposed in a communication path to said means for 15 means for introducing time delay between reception of
unblinding. said second messages and the sending of said third mes
31. Apparatus as in claim 20, 21, 22, 23, 26, 27, 28 or Sages.
29 further comprising means for checking the public
key digital signature property of at least one of said or37. Apparatus as in claim 20, 21, 22, 23, 26, 29, 28, 29
35 wherein:
third messages. said means for blinding includes means for forming a
32. Apparatus as in claim 31 further comprising product of at least one of said original message and
means for transferring a said third message to a party for a blinding factor derived from a corresponding one
performing said checking. of said first keys; and
33. Apparatus in claim 32 wherein said means for
transferring a third message includes means for time 25 saida product
means for unblinding includes means for forming
of the corresponding said second mes
delaying such messages. sage with a multiplicative inverse of a signed form
34. Apparatus as in claim 31 further comprising: of said first key, in a finite structure where such
means for retaining a record responsive to valid said multiplication and multiplicative inverses are de
third messages checked; and fined.
means for searching said record to determine when 30 38. Apparatus as in claim 37 further comprising
the same said third message has been recorded means for checking the public key digital signature
previously.
35. Apparatus for providing untraceability of value property
39.
of at least one of said third messages.
Apparatus as described in claim 37 wherein:
transfers by processing a plurality of original digital said means for blinding transforms original messages
messages before they receive public key digital signa 35 mi using first keys ki to produce first messages ti
tures and processing the resulting digital messages after described by
they have received the public key digital signatures
where said processed digital messages are considered to ti= miki (mod n),
be "blinded' and said resulting digital messages to be
"unblinded” because although the public key digital where e is a public signing exponent, and n is a public
signatures of said resulting digital messages are check key digital signature modulus;
able using a public key, even possesssion of that public said means for signing transforms said first messages
key and of the corresponding secret signing key is sub ti using secret signing key d to produce second
stantially insufficient to substantially feasibly determine messages ti described by
the correspondence between the elements of said pro 45
cessed digital message set and the elements of the corre
sponding said resulting digital message set, said appara
tus for processing comprising: said means for unblinding transforms said second
means for blinding by transforming at least part of messages t't using first keyski to produce said third
each of a plurality of original digital messages re 50 messages m't described by
sponsive 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 40. Apparatus as in claim 39 further comprising
party, and the signer party transforming at least 55 means for checking the public key digital signature
two of said first messages, at least partially respon property of at least one of said third messages m'i in
sive to signing secret key information of said signer cluding exponentiation to the power e.
party, to produce second digital messages; 41. Apparatus for processing original digital messages
means for providing the corresponding said second before they receive public key digital signatures and for
messages to at least two corresponding said sup 60 processing the resulting messages after they have re
plier parties in exchange for a transfer of value ceived the public key digital signatures where said pro
from such corresponding supplier parties; cessed digitial messages are considered to be "blinded'
means for receiving corresponding said second mes and said resulting digital messages to be "unblinded'
sages by said supplier parties and transforming the because, although the public key digital signatures of
corresponding second messages with said first keys 65 said resulting digital messages are checkable using a
to produce corresponding unblinded third digital public key, even possession of the public key and of the
messages each having a digital signature property corresponding secret signing key does not readily allow
related to a corresponding one of said original the correspondence between elements of said processed
4,759,063 26
25
digital message set and elements of the corresponding means for receiving said third output and transform
said resulting digital message set to be determined, said ing the third output with a first unblinding tranfor
apparatus for processing comprising: mation, depending on a first one of said first and
means for transforming at least part of a first input second secret keys, to produce a fourth output; and
with a first blinding transformation depending on a means for transforming said fourth output with a
first secret key to produce a first output; second unblinding transformation, depending on
means for receiving said first output and transforming the remaining one of said first and second secret
said first output with a second blinding transforma keys, to produce a fifth output, and the fifth output
tion depending on a second secret key to produce a retaining a digital signature property related to said
second output; O first input, and said third and the fifth outputs being
means for receiving said second output and develop not readily linkable without the first and second
ing a third output at least partially responsive to the secret keys. it k it is
second output and to a secret signing key;
15
20
25
30
35
45
50
55
65