Privacy-protected transfer of electronic information

Abstract

Cryptographic apparatus and means are disclosed for each of three types of participants in an electronic system for privacy-protected transfer of certified information. This invention reveals protocols that improve efficiency and security in such systems, and allows a variety of useful extensions in functionality without difficulty. This is achieved by a restrictive blind signature protocol in combination with a testing protocol. The restrictive blind signature protocol allows the certifying party to encode data into certified information that it provides to a receiving party, such that it cannot be altered or modified by the receiving party. The testing protocol enables parties to prove a variety of characteristics about the encoded data in their certified information.

Claims

What is claimed is:

1. A method for a first party to have information certified by a second party by generating a signal representative of a digital certificate corresponding to a vector of numbers, wherein the signals representative of the vector of numbers and the digital certificate are hidden from the second party, yet the second party is ensured that a representation, known by the first party, of at least one number in the vector of numbers, contains the information to be certified, the method comprising the steps of:

generating by the second party, a signal representative of a secret key and a corresponding public key, and providing a specification of the correspondence between the signals representative of the digital certificates and vectors of numbers with respect to the public key;

randomly transforming by the first party, signals representative of the information to be certified, into a vector of numbers, such that the first party knows a representation of at least one number in the vector of numbers, and the representation contains the information to be certified;

computing by the first party, challenge information, and transmitting signals representative of the challenge information to the second party;

computing by the second party, response information based on at least the challenge information and the secret key, and transmitting signals representative of the response information to the first party; and

computing by the first party, based on at least the received response information, a digital certificate corresponding to the vector of numbers.

2. A method as in claim 1, wherein the vector of numbers comprises the at least one number of which the first party knows a representation, and additional numbers, of each of which the first party knows a substantially randomly generated representation.

3. A method as in claim 1, wherein the information to be certified has previously been certified by the second party.

4. A method as in claim 2, wherein the information to be certified is a combination of information that has previously been certified by the second party and values by which the information that has previously been certified by the second party, is updated.

5. A method as in claim 1, wherein the vector of numbers represents a digital pseudonym of the first party.

6. A method as in claim 1, wherein the first party comprises a third party and a fourth party.

7. A method as in claim 1, wherein the specification provided by the second party is sufficient for the first party to compute digital certificates corresponding to vectors of numbers, without further assistance of the second party.

8. A method as in claim 1, wherein a representation of a number, m, is a vector of numbers, (a.sub.1, . . . , a.sub.k ; a.sub.k+1), such that m+Y.sub.1.sup.a.sbsp.1. . . Y.sub.k.sup.a.sbsp.k a.sup.v.sub.k+1 where

k.gtoreq.1,

m is a number in a group, Z.sub.n *, where n is a product of at least two distinct prime numbers,

Y.sub.1, . . . , Y.sub.k are numbers in Z.sub.n *,

a.sub.1, . . . , a.sub.k are numbers in a ring, Z.sub.v, where v is a positive number, and

a.sub.k+1 is a number in Z.sub.n *.

9. A method as in claim 8, wherein

the public key comprises a number, X, in Z.sub.n *, and a hash-function H;

the secret key comprises the v.sup.th root modulo n of each of the numbers, X,Y.sub.1, . . . , Y.sub.k, or, alternatively, the prime factorization of the number, n; and

the correspondence between a digital certificate and a vector of numbers with respect to the public key is specified according to b.sup.v =(Xm).sup.c a or, alternatively, according to b.sup.v =Xm(a).sup.c, where

a and b are numbers in Z.sub.n *, and

c denotes H(m,B.sub.1, . . . , B.sub.1,a), where (m,B.sub.1, . . . , B.sub.1) is the vector of numbers.

10. A method as in claim 1, wherein a representation of a number, m, is a vector of numbers, (a.sub.1, . . . ,a.sub.k), such that m=g.sub.1.sup.a.sbsp.1. . . g.sub.k.sup.a.sbsp.k, where

k.gtoreq.2,

m is a number in a group, G.sub.q, of order q, where q is a prime number,

g.sub.1, . . . , g.sub.k are numbers in G.sub.q, and

a.sub.1, . . . , a.sub.k are numbers in the ring, Z.sub.q.

11. A method as in claim 10, wherein

the public key comprises two numbers, g and h, in G.sub.q, and a hash-function H;

the secret key comprises the discrete logarithm, in Z.sub.q, of h with respect to g; and

the correspondence between a digital certificate and a vector of numbers with respect to the public key is specified according to g.sup.r =(hm).sup.c a or, alternatively, according to g.sup.r =hm(a).sup.c, where

a is a number in G.sub.q,

c denotes H(m,B.sub.1, . . . ,B.sub.1,a), where (m,B.sub.1, . . . ,B.sub.1) is the vector of numbers, and

r is a number in Z.sub.q.

12. A method as in claim 10, wherein

the public key comprises two numbers, g and h, in G.sub.q, and a hash-function H;

the secret key comprises the discrete logarithm, in Z.sub.q, of h with respect to g; and

the correspondence between a digital certificate and a vector of numbers with respect to the public key is specified according to g.sup.r =h.sup.c a and m.sup.r =z.sup.c b, or, alternatively, according to g.sup.r =ha.sup.c and m.sup.r =za.sup.c, where

z, a, and b, are numbers in G.sub.q,

c denotes H(m,B.sub.1, . . . , B.sub.1,a), where (m,B.sub.1, . . . , B.sub.1) is the vector of numbers, and

r is a number in Z.sub.q.

13. A method for a first party which knows a first representation, where a first representation is a representation of at least one number in a vector of numbers with respect to a first function, to transmit to a third party a signal constituting a second representation, where a second representation is a representation of a second function of the at least one number in the vector of numbers with respect to a third function, the first party having previously generated a signal representative of a digital certificate corresponding to the vector of numbers with respect to a public key of a second party, the method comprising the steps of:

providing by the first party to the third party, signals representative of the vector of numbers and the digital certificate;

computing by the first party, in response to challenge information, response information based on at least the challenge information and the second representation, and transmitting signals representative of the response information to the third party; and

verifying by the third party, that the digital certificate corresponds to the vector of numbers with respect to the public key and that the response information corresponds to the challenge information, the second function of the at least one number in the vector of numbers, and the third function.

14. A method as in claim 13, wherein the second function is an identity function and the third function is the same as the first function.

15. A method as in claim 13, wherein the second and third functions determine a property of the first representation.

16. A method as in claim 13, wherein the challenge information is a one-way hashfunction of at least the vector of numbers.

17. A method as in claim 13, wherein knowing the correspondence between digital certificates and vectors of numbers with respect to the public key, is sufficient for the first party to compute digital certificates corresponding to vectors of numbers, without further assistance of the second party.

18. A method as in claim 13, wherein

the first party also transmits to the third party a signal representative of an additional number, of which it knows a substantially random representation with respect to the third function; and

the response information is a linear combination, determined by the challenge information, of the second representation and the substantially random representation.

19. A method as in claim 13, wherein

the vector of numbers comprises the at least one number of which the first party knows a representation with respect to the first function, and additional numbers, of each of which the first party knows a substantially randomly generated representation with respect to the third function; and

the response information is a linear combination, determined by the challenge information, of the second representation and the substantially randomly generated representation of one of the additional numbers.

20. A method as in claim 13, wherein the first party comprises a fourth party and a fifth party.

21. A method as in claim 13, wherein the first representation contains a set of credentials that has been certified by the second party.

22. A method as in claim 13, wherein a representation of a number, m, with respect to the third function is a vector of numbers, (a.sub.1, . . . , a.sub.k ; a.sub.k+1), such that m=Y.sub.1.sup.a.spsb.1. . . Y.sub.k.sup.a.spsb.k a.sub.k+1.sup.v, where

k.gtoreq.0,

m is a number in a group, Z.sub.n *, where n is a product of at least two distinct prime numbers,

Y.sub.1, . . . , Y.sub.k are numbers in Z.sub.n *,

a.sub.1, . . . , a.sub.k are numbers in a ring, Z.sub.v, where v is a positive number, and

a.sub.k+1 is a number in Z.sub.n *.

23. A method as in claim 22, wherein the first function maps a vector of numbers, (b.sub.1, . . . , b.sub.j ; b.sub.j+1), to the number Z.sub.1.sup.b.sbsp.1 . . . Z.sub.j.sup.b.sbsp.j b.sub.j+1.sup.v, for j.gtoreq.1, where Z.sub.1, . . . Z.sub.j, are numbers in Z.sub.n * that have been determined by the second party, and each of the numbers, Y.sub.1, . . . , Y.sub.k, is a product of powers of numbers in the set, {Z.sub.1, . . . , Z.sub.j }, and their inverses.

24. A method as in claim 13, wherein a representation of a number, m, with respect to the third function is a vector of numbers, (a.sub.1, . . . , a.sub.k), such that m=g.sub.1.sup.a.sbsp.1 . . . g.sub.k.sup.a.sbsp.k, where

k.gtoreq.1,

m is a number in a group, G.sub.q, of order q, where q is a prime number,

g.sub.1, . . . , g.sub.k are numbers in G.sub.q, and

a.sub.1, . . . , a.sub.k are numbers in the ring, Z.sub.q.

25. A method as in claim 24 wherein the first function maps a vector of numbers, (b.sub.1, . . . , b.sub.j), to the number e.sub.1.sup.b.sbsp.1 . . . e.sub.j.sup.b.sbsp.j, for j.gtoreq.2, where e.sub.1, . . . , e.sub.j are numbers in G.sub.q that have been determined by the second party, and each of the numbers, g.sub.1, . . . , g.sub.k, is a product of powers of numbers in the set, {e.sub.1, . . . , e.sub.j }, and their inverses.

26. A method for a first party to have information certified by a second party by generating a signal representative of a digital certificate corresponding to a vector of numbers, wherein the signals representative of the vector of numbers and the digital certificate are hidden from the second party, yet the second party is ensured that the information to be certified is contained in a representation known by the first party of at least one number in the vector of numbers with respect to a first function, and then to transmit to a third party a signal constituting a representation of a second function of the at least one number in the vector of numbers with respect to a third function, the method comprising the steps of:

generating by the second party, a signal representative of a first secret key and a corresponding first public key, and providing a specification of the correspondence between the signals representative of the digital certificates and vectors of numbers with respect to the first public key;

randomly transforming by the first party, signals representative of the information to be certified, into a vector of numbers, such that the first party knows a first representation, where a first representation is a representation of at least one number in the vector of numbers with respect to the first function, and the first representation contains the information to be certified;

computing by the first party, first challenge information, and transmitting signals representative of the first challenge information to the second party;

computing by the second party, first response information based on at least the first challenge information and the first secret key, and transmitting signals representative of the first response information to the first party;

computing by the first party, based on at least the received first response information, a digital certificate corresponding to the vector of numbers;

transmitting by the first party to the third party, signals representative of the vector of numbers and the digital certificate;

computing by the first party, in response to second challenge information, second response information based on at least the second challenge information and a second representation, where a second representation is a representation of the second representation is a representation of the second function of the at least one number in the vector of numbers with respect to the third function, and transmitting a signal representative of the second response information to the third party; and

verifying by the third party, that the digital certificate corresponds to the vector of numbers with respect to the first public key and that the second response information corresponds to the second challenge information, the second function of the at least one number in the vector of numbers, and the third function.

27. A method as in claim 26, wherein the specification provided by the second party is sufficient for the first party to compute digital certificates corresponding to vectors of numbers, without further assistance of the second party.

28. A method as in claim 26, wherein

the vector of numbers comprises the at least one number of which the first party knows a representation with respect to the first function, and additional numbers, of each of which the first party knows a substantially randomly generated representation with respect to the third function; and

the second response information is a linear combination, determined by the second challenge information, of the second representation and the substantially randomly generated representation of one of the additional numbers.

29. A method as in claim 28, wherein there are at least two additional numbers.

30. A method as in claim 28, wherein the first party has a second secret key and a corresponding second public key, and the first representation contains the second secret key.

31. A method as in claim 26, wherein the information to be certified has previously been certified by the second party.

32. A method as in claim 26, wherein the information to be certified is a combination of information that has previously been certified by the second party and values by which the information that has previously been certified by the second party, is updated.

33. A method as in claim 26, wherein the information to be certified is a set of credentials.

34. A method as in claim 26, wherein the vector of numbers represents a pseudonym of the first party with the third party.

35. A method as in claim 26, wherein the first party comprises a fourth party and a fifth party.

36. A method as in claim 35, wherein the fourth party acts in the interest of the second party, and can only communicate with the fifth party.

37. A method as in claim 36, wherein the fifth party randomizes at least one number provided by the fourth party.

38. A method as in claim 26, wherein

the first party also transmits to the third party a signal representative of an additional number, of which it knows a substantially random representation with respect to the third function; and

the second response information is a linear combination, determined by the second challenge information, of the second representation and the substantially random representation.

39. A method as in any one of claims 26 to 37 for implementing an electronic cash system, wherein

the first party is a paying party, such as a consumer;

the second party is a financial institution, such as a bank, that issues electronic cash; and

the third party is a servicing organization, such as a shop.

40. A method as in claim 39, wherein the amount of electronic cash held by the first party is indicated by a counter held by, but not under control of, the first party.

41. A method as in claim 26, wherein a representation of a number, m, with respect to the first function is a vector of numbers, (a.sub.1, . . . , a.sub.k ; a.sub.k+1), such that m=Y.sub.1.sup.a.sbsp.1 . . . Y.sub.k.sup.a.sbsp.k a.sub.k+1.sup.v, where

k.gtoreq.1,

m is a number in a group, Z.sub.n *, where n is a product of at least two distinct prime numbers,

Y.sub.1, . . . , Y.sub.k are numbers in Z.sub.n *,

a.sub.1, . . . , a.sub.k are numbers in a ring, Z.sub.v, where v is a positive number, and

a.sub.k+1 is a number in Z.sub.n *.

42. A method as in claim 26, wherein a representation of a number, m, with respect to the first function is a vector of numbers, (a.sub.1, . . . , a.sub.k), such that m=g.sub.1.sup.a.sbsp.1 . . . g.sub.k.sup.a.sbsp.k, where

k.gtoreq.2,

m is a number in a group, G.sub.q, of order q, where q is a prime number,

g.sub.1, . . . , g.sub.k are numbers in G.sub.q, and

a.sub.1, . . . , a.sub.k are numbers in the ring, Z.sub.q.

43. An apparatus for a first party to have information certified by a second party by generating a signal representative of a digital certificate corresponding to a vector of numbers, wherein the signals representative of the vector of numbers and the digital certificate are hidden from the second party, yet the second party is ensured that a representation, known by the first party, of at least one number in the vector of numbers, contains the information to be certified, the apparatus comprising:

first processing means for use by the first party;

second processing means for use by the second party, the second processing means being beyond control of the first party;

interface means between the first processing means and the second processing means;

key generation means for generating a secret key and a corresponding public key for the second party;

means within the first processing means for randomly transforming signals representative of the information to be certified, into a vector of numbers, such that the first processing means has access to a representation of at least one number in the vector of numbers, and the representation contains the information to be certified;

means within the first processing means for computing challenge information;

means within the first processing means for transmitting to the second processing means, signals representative of the challenge information;

means within the second processing means for computing response information, based on at least the challenge information and the secret key;

means within the second processing means for transmitting to the first processing means, signals representative of the response information; and

means within the first processing means for computing, based on at least the received response information, a digital certificate corresponding to the vector of numbers.

44. An apparatus as in claim 43, wherein the first processing means comprises a third processing means, a fourth processing means, and interface means therebetween.

45. An apparatus for a first party which knows a first representation, where a first representation is a representation of at least one number in a vector of numbers with respect to a first function, to transmit to a third party a signal constituting a second representation, where a second representation is a representation of a second function of the at least one number in the vector of numbers with respect to a third function, the first party having previously generated a signal representative of a digital certificate corresponding to the vector of numbers with respect to a public key of a second party, the apparatus comprising:

first processing means for use by the first party;

second processing means for use by the third party;

interface means between the first processing means and the second processing means;

means within the first processing means for transmitting to the second processing means, signals representative of the vector of numbers and the corresponding digital certificate;

means within the first processing means for computing, in response to challenge information, response information based on at least the challenge information and the second representation;

means within the first processing means for transmitting to the second processing means, signals representative of the response information; and

means within the second processing means for verifying that the digital certificate corresponds to the vector of numbers with respect to the public key and that the response information corresponds to the challenge information, the second function of the at least one number in the vector of numbers, and the third function.

46. An apparatus as in claim 45, wherein the first processing means comprises a third processing means, a fourth processing means, and interface means therebetween.

47. An apparatus for a first party to have information certified by a second party by generating a signal representative of a digital certificate corresponding to a vector of numbers, wherein the signals representative of the vector of numbers and the digital certificate are hidden from the second party, yet the second party is ensured that the information to be certified is contained in a representation known by the first party of at least one number in the vector of numbers with respect to a first function, and then to transmit to a third party a signal constituting a representation of a second function of the at least one number in the vector of numbers with respect to a third function, the apparatus comprising:

first processing means for use by the first party;

second processing means for use by the second party and beyond control of the first party;

third processing means for use by the third party;

first interface means between the first processing means and the second processing means;

second interface means between the first processing means and the third processing means;

key generation means for generating a signal representative of a secret key and a corresponding public key for the second party;

means within the first processing means for randomly transforming signals representative of the information to be certified, into a vector of numbers, such that the first processing means has access to a first representation, where a first representation is a representation of at least one number in the vector of numbers with respect to the first function, and the first representation contains the information to be certified;

means within the first processing means for computing first challenge information;

means within the first processing means for transmitting to the second processing means, a signal representative of the first challenge information;

means within the second processing means for computing first response information based on at least the first challenge information and the secret key;

means within the second processing means for transmitting to the first processing means, a signal representative of the first response information;

means within the first processing means for computing, based on at least the first response information, a digital certificate corresponding to the vector of numbers;

means within the first processing means for transmitting to the third processing means, signals representative of the vector of numbers and the digital certificate;

means within the first processing means for computing, in response to second challenge information, second response information based on at least the second challenge information and a second representation, where a second representation is a representation of the second function of the at least one number in the vector of numbers with respect to the third function;

means within the first processing means for transmitting to the third processing means, a signal representative of the second response information; and

means within the third processing means for verifying that the digital certificate corresponds to the vector of numbers with respect to the public key and that the second response information corresponds to the second challenge information, the second function of the at least one number in the vector of numbers, and the third function.

48. An apparatus as in claim 47, wherein the first processing means comprises a fourth processing means, a fifth processing means, and third interface means therebetween.

49. An apparatus as in claim 48, wherein the fourth processing means is tamper-resistant and can only communicate with the fifth processing means, through the third interface means.

50. An apparatus as in claim 49, wherein the fifth processing means randomizes at least one number provided by the fourth processing means.

51. An apparatus as in any one of claims 47 to 50 for implementing an electronic cash system, wherein:

the first party is a paying party, such as a consumer;

the second party is a financial institution, such as a bank, that issues electronic cash; and

the third party is a servicing organization, such as a shop.

52. An apparatus as in claim 47 for implementing an electronic cash system, wherein the first processing means is tamper-resistant, and further comprises counter means for indicating the amount of electronic cash held by the first party.

53. An apparatus as in either claim 49 or 50 for implementing an electronic cash system, wherein the fourth processing means comprises counter means for indicating the amount of electronic cash held by the first party.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to digital transaction systems, and more specifically to secure systems for privacy-protected transfer of certified electronic information based on public key cryptography.

2. Description of Prior Art

The invention relates to electronic systems for privacy-protected transfer of certified information.

It is common usage in the art to model such systems using three basic types of participants: a "certifying" party that certifies information, a "user" that makes use of certified information, and an "organization" to whom certified information is shown. In general, a system will consist of several users and organizations, and possibly also certifying parties. It is also possible for a participant to perform more than one role, such as be a certifying party and an organization or be a user and an organization. Each type of participant has access to an electronic computing device with storage capacity, in the form of, for example, a smart card, a palm-top computer or a personal computer. Certified information is represented by vectors of numbers, hence it can be transferred by electronic means. In this context, a vector is an ordered set of one or more numbers.

A particular example of such a system is an electronic cash system. The certifying party is the blank; it issues money. Users are account holders; they can withdraw electronic money at the bank. Organizations are shops and the like; according to the rules of the system they have to accept certified information as a means of payment for goods and services. Of course, in a practical implementation of such a system there will be various banks and other organizations such as a clearing center.

In general, any transaction system that can be subjected to automation is a potential example of this system. One can consider systems for transferring certified information of a great many types: voting rights, certificates or diplomas, coins, driver's licenses, doctor's approvals, birth certificates, certificates of citizenship, tax-related data, and the like.

It is well-known in the art that digital signatures can be used to certify electronic information. This cryptographic technique consists of the certifying party generating two algorithms or keys, only one of which it makes publicly known. To certify a vector of numbers, the certifying party generates, by applying the secret algorithm, a second vector of numbers (the digital signature) that is in a certain mathematical relation to the vector of numbers to be certified. Two vectors of numbers for which this relation holds can only be efficiently constructed if one knows the secret algorithm. The publicly known algorithm can merely be used to verify whether two vectors of numbers are in such a relation to one another. Hence the second vector can serve as a digital signature on the first vector. Both vectors together form a piece of certified information, and they can be viewed as being one vector embodying a signature of the certifying party.

When digital signatures are used without any additional features, no privacy is offered to the users. Such digital signatures will be referred to as ordinary digital signatures. The information that is shown by users to different organizations can be linked; the certifying party knows which user receives which certified vector of numbers, and the organization that the certified information is transferred to sees exactly the same vector of numbers.

A cryptographic concept has been devised to guarantee privacy in such systems (see U.S. Pat. No. 4,759,063 to Chaum). This concept consists of a so-called "blind" signature protocol between the certifying party and the user. In such a protocol the user can make sure that the certifying party at the end of the protocol has no clue whatsoever regarding the vector of numbers he obtained. Yet, the certifying party knows for sure that the user has obtained a piece of certified information of the type specified at the start of the protocol, such as a coin or a driver's licence.

A second cryptographic concept to guarantee privacy of users when transferring certified information is known. It consists of letting the users be known by different pseudonyms at different organizations such that the pseudonyms are unlinkable. In principle, it is then possible for users to tranfer certified information between their pseudonyms. This concept necessarily uses the concept of blind signature protocols: each user must obtain his pseudonyms in a blind signature protocol. Cryptographic protocols have been proposed that enable the user to transform an ordinary digital signature on one of his pseudonyms (made by the organization at which he has that pseudonym; note that this is an example of an organization acting also as a certifying party) to a digital signature on each of his other pseudonyms. In this way information certified by one particular organization can be shown to all other organizations at which the user has a pseudonym, without enabling the organizations to link the transferred information. A system that makes use of unlinkable pseudonyms between which credentials are transferred is known as a credential mechanism.

Certain types of certified information may only be shown once, such as coins in a cash system. To prevent users in a system based on blind signatures from showing such information multiple times to distinct organizations without ever revealing their identity, a third concept is known, consisting of a special type of blind signature protocol called a "one-show" blind signature protocol (see U.S. Pat. No. 4,914,698 to Chaum). In a one-show blind signature protocol, the certifying party knows for sure that information related to the participating user is encoded into the certified information he obtains. Certified information must then be "tested" by the organization to which it is shown in such a way that testing it twice allows the encoded information to be computed.

To guarantee organizations and certifying parties in the privacy-protecting systems more control over what users do with their certified information, yet another concept is known (see U.S. Pat. No. 4,926,480 to Chaum). This consists of "embedding" a tamper-resistant computing device into the device of the user. Embedding should not to be taken too literally; the configuration might as well consist of, say, a tamper-resistant device connected to the parallel port of the user's personal computer. The tamper-resistant device acts in the interests of the certifying parties and/or organizations. In principle, cryptographic protocols can ensure that the device of the user can only show and erase certified information in cooperation with the embedded tamper-resistant device. Due to the embedding, the user-module can ensure itself that the privacy is guaranteed, since it can see to it that no identity-related information is leaked by or to the embedded device.

Significant difficulties show up in the realization of these concepts. Essentially only one realization of the credential mechanism for transferring credentials between pseudonyms (not considering the few minor variations that have been proposed) is known. In this mechanism, users can transfer a signature on one of their pseudonyms to a signature on all their pseudonyms; there is no provision for transfer between pseudonyms of credentials that may only be used a limited number of times. This is because ordinary digital signatures are used to sign pseudonyms. A further difficulty is that the known realization of a protocol for issuing pseudonyms in a blinded way to users is quite inefficient in communication, computation and storage complexity due to the so-called "cut-and-choose" technique that is applied. Yet another important concern is that the security of this protocol, and hence of the entire system, is an open question. Furthermore, no protocols are known for which the concept of the embedded tamper-resistant part is realized under the most stringent of privacy criteria known in the art, consisting of the impossibility for the certifying party, organization and the tamper-resistant device to develop during the protocols random numbers known to at least two of these parties. No provision seems to exist for multiple users to prove in cooperation that the ensemble of their credentials meets certain requirements. Still another problem is that there seems to be no way for users to prove to an organization that a pseudonym is theirs other than by first obtaining a signature on one of their pseudonyms. Yet another problem is that there seems to be no efficient protocol that can be used to prove that one has a certain combination of a plurality of credentials. A further problem is that it is difficult to allow for credentials that represent quantities, such as age, income, and the like; there is also no provision to prove relations between various quantities without revealing the quantities themselves and no way for certifying parties to update such credentials without needing to know their previous values.

Several realizations of the concepts for the particular instance of off-line electronic cash systems are known. In these systems, one-show credentials are not transferred between pseudonyms; account holders do not have pseudonyms with shops. Yet, this type of system may be called a credential machanism. None of the cash systems known in the literature is a particular instance of the known credential mechanism, i.e., none can be derived from it by using the same general techniques used to realize the credential mechanism. They all use what seem to be ad hoc constructions to realize the concepts of the one-show blind signatures (since coins are credentials that may be shown only once). This causes their security to be an open question, and also prevents efficient implementation by means of a simple and compact software kernel that need not be modified when extensions in functionality are added later on. Furthermore, the withdrawal protocols known to realize the one-show property make use of the cut-and-choose technique, which causes them to be inefficient in communication, computation, and storage complexity. Due to the use of the ad hoc constructions in the protocols, it seems very difficult to extend the functionality of the systems without further worsening the problems related to security and efficiency.

A few extensions allowing the issuing of cheques have been proposed. However, once again, their security is an open problem, and they are quite inefficient. A general technique to incorporate protection against framing attempts of the bank (meaning that the bank falsely accuses an account holder of having double-spent a coin) is known. This technique, however, causes a serious increase in storage requirements for the computing devices of the users and only offers protection assuming that the bank has limited computing power. Another problem is that the only way to encode additional information, such as expiration dates, currency denomination, and the like, seems to be to use a different type of signature for each value. Although it has been suggested that the bank can allow coins to be spent more than once without payments being traceable, no efficient realizations are known. Although untraceable cash systems have been proposed, systems with both untraceable payments and anonymous accounts seem difficult to realize in currently known systems. No system is known that allows realization of the concept of embedded tamper-resistant devices under the most stringent of privacy requirements mentioned above, and the few systems known that realize this extension meeting less stringent criteria have questionable security. Another item of concern might be that there is no satisfactory way to prevent the "halting channel" in this extension. The halting channel problem means that the tamper-resistant part can leak at least one bit of information to the certifying party or organization by simply halting, or not halting, the execution of the protocol at a certain point. In view of these shortcomings, it will come as no surprise that no systems have been proposed that can incorporate all combinations of these extensions simultaneously.

The known credential mechanism and the off-line cash systems that are of practical relevance can all be broken if the so-called RSA problem, well-known in the art (See Rivest et al., "A method for obtaining digital signatures and public-key cryptosystems," Communications of the ACM, Feb. 1978, pp. 120-126), can be broken. No such systems are known that will remain secure even if the RSA problem is broken.

OBJECTS OF THE INVENTION

Accordingly, it is an object of the present invention to:

increase efficiency, security, and extendability in functionality of systems for transferring electronic information by introducing a special type of blind signature protocol that will henceforth be referred to as a restrictive blind signature protocol;

increase the efficiency of credential mechanisms by applying a restrictive blind signature protocol to issue pseudonyms instead of using the technique of cut-and-choose;

allow for credentials that may be shown only a limited number of times to be transferred between pseudonyms, by using restrictive blind signature protocols to sign pseudonyms;

improve the security of credential mechanisms by providing for realizations of restrictive blind signature protocols whose security is directly related to that of protocols that are well-known in the art;

construct efficient and secure realizations of restrictive blind signature protocols by providing for two techniques to construct such protocols based on a particular type of identification and signature protocol well-known in the art;

improve the privacy offered to users in systems that use embedded tamper-resistant devices by providing for appropriate protocols based on restrictive blind signatures;

allow efficient proofs for showing possession of a plurality of credentials using only a single protocol;

prevent the need for a separate digital signature for each credential;

allow a variety of credentials to be maintained by the user such that only one corresponding digital signature is needed;

allow credentials that denote quantities without needing a different type of signature for each quantity;

allow organizations to update credentials of a user without needing to know the credentials already owned by the user;

allow users to prove a variety of mathematical relations between their credentials without revealing any additional information, by means of one, simple protocol;

efficiently realize credentials that may be shown a limited number of times;

allow the creation of anonymous accounts in off-line electronic cash systems by using restrictive blind signature protocols;

improve the security of off-line electronic cash systems by avoiding ad hoc constructions;

improve the efficiency of off-line cash systems by using restrictive blind signature protocols to withdraw cash;

allow efficient and secure ways to issue checks in off-line electronic cash systems;

allow for off-line electronic cash systems based only on the techniques used in the general credential mechanisms;

prevent the halting channel from the tamper-resistant part to the outside party by constructing protocols in which only one transmission between the computing device of the user and the outside party is needed;

prevent in such protocols in a similar way the halting channel from the outside party to the tamper-resistant device;

allow extensions in functionality of credential mechanisms to be simply switched off by setting corresponding subsets of numbers chosen randomly by the user to a fixed value, and letting the certifying party perform the computations involving the numbers in those subsets rather than the user himself;

allow implementation of such systems using a highly compact set of basic algorithms and data structures which may be used regardless of the number and nature of the various extensions in functionality of these systems;

protect against framing attempts in a simple manner that does not affect storage requirements;

allow the certifying party to encode additional information into credentials in an efficient way that does not influence security;

allow combinations of the aforementioned objects to be achieved without this negatively affecting efficiency and security, by providing for a compact and uniform set of algorithms on which the entire system is based;

increase in off-line electronic cash systems using embedded tamper-resistant devices the security for certifying parties and organizations by in effect letting the tamper-resistant device execute in the ensemble of withdrawal and payment protocol a special type of identification protocol well-known in the art;

require very little storage space and computational effort of tamper-resistant parts, such that they can be implemented using small computing devices, such as currently used smart cards; and

allow efficient, economical, and practical apparatus and methods fulfilling the other objects of the invention.

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

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 shows a block diagram of a preferred embodiment including a workstation, external system, and an optional tamper-resistant computing device in accordance with the teachings of the present invention.

FIG. 2 shows a flowchart of a restrictive blind signature protocol for a first preferred embodiment in accordance with the teachings of the present invention.

FIG. 3 shows a flowchart of another restrictive blind signature protocol for the first preferred embodiment in accordance with the teachings of the present invention.

FIG. 4 shows a flowchart of a third restrictive blind signature protocol for the first preferred embodiment in accordance with the teachings of the present invention.

FIG. 5 show a flowchart of a proof of knowledge of a representation of a number A for the first preferred embodiment in accordance with the teachings of the present invention.

FIG. 6 show a flowchart of a protocol for establishing a pseudonym for the first preferred embodiment in accordance with the teachings of the present invention.

FIG. 7 shows a flowchart of a withdrawal protocol for a coin in a cash system for the first preferred embodiment in accordance with the teachings of the present invention.

FIG. 8 shows a flowchart of a payment protocol for a coin for the first preferred embodiment in accordance with the teachings of the present invention.

FIG. 9 shows a flowchart of a withdrawal protocol for a coin, when a tamper-resistant device must cooperate with the computing device of the user, for the first preferred embodiment in accordance with the teachings of the present invention.

FIG. 10 shows a flowchart of a payment protocol for a coin, when a tamper-resistant device must cooperate with the computing device of the user, for the first preferred embodiment in accordance with the teachings of the present invention.

FIG. 11 shows a flowchart of a withdrawal protocol for a cheque for the first preferred embodiment in accordance with the teachings of the present invention.

FIG. 12 shows a flowchart of a payment protocol for a cheque for the first preferred embodiment in accordance with the teachings of the present invention.

FIG. 13 shows a flowchart of a refund protocol for cheques for the first preferred embodiment in accordance with the teachings of the present invention.

FIG. 14 shows a flowchart of a restrictive blind signature protocol for a second preferred embodiment in accordance with the teachings of the present invention.

FIG. 15 shows a flowchart of another restrictive blind signature protocol for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 16 shows a flowchart of a third restrictive blind signature protocol for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 17 shows a flowchart of yet another restrictive blind signature protocol for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 18 shows a flowchart of a proof of knowledge of a representation of a number A for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 19 shows a flowchart of a withdrawal protocol for a coin in a cash system for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 20 shows a flowchart of a payment protocol for a coin for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 21 shows a flowchart of a withdrawal protocol for a coin, when a tamper-resistant device must cooperate with the computing device of the user, for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 22 shows a flowchart of a payment protocol for a coin, when a tamper-resistant device must cooperate with the computing device of the user, for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 23 shows a flowchart of yet another restrictive blind signature protocol for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 24 shows a flowchart of a withdrawal protocol for a coin in a modified cash system for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 25 shows a flowchart of a payment protocol for a coin for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 26 shows a flowchart of a withdrawal protocol with unconditional protection against framing for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 27 shows a flowchart of a payment protocol with unconditional protection against framing for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 28 shows a flowchart of a protocol for opening an account, when a tamper-resistant device must cooperate with the computing device of the user, for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 29 shows a flowchart of a withdrawal protocol for a coin, when a tamper-resistant device must cooperate with the computing device of the user, for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 30 shows a flowchart of a payment protocol for a coin, when a tamper-resistant device must cooperate with the computing device of the user, for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 31 shows a flowchart of a withdrawal protocol for a cheque for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 32 shows a flowchart of a payment protocol for a cheque for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 33 shows a flowchart of a refund protocol for cheques for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 34 shows a flowchart of a pseudonym-issuing protocol for the second preferred embodiment in accordance with the teachings of the present invention.

SUMMARY OF THE INVENTION

In accordance with these and other objects of this invention, a brief summary of the invention is presented. Some simplifications and omissions may be made in the following summary, which is intended to highlight and introduce some aspects of the present invention, but not to limit its scope. Detailed descriptions of two preferred exemplary embodiments adequate to allow those of ordinary skill in the art to make and use this invention will be provided later.

A computing device is held by a user who can control its internal operation (almost) completely. The user conducts transactions by transferring certified electronic information between one or more certifying parties and organizations.

Optionally, the computer device of the user needs assistance of a tamper-resistant computing device in order to successfully make such transfers. The tamper-resistant device represents the interests of certifying parties, and possibly also of the organizations. To guarantee that the tamper-resistant part does not compromise the untraceability of transactions conducted by its holder, the physical arrangement is such that the tamper-resistant part can only send information to its holder and, likewise, can receive information only from its holder. The only exception is that the certifying parties and/or organizations may perhaps store occasionally, or at least once before handing the device to a user, (additional) information into the tamper-resistant part, such as secret keys, that the user would need to know in order to transfer certified information without its assistance.

FIGS. 2, 3, 4, 14, 15, 16, 17, and 23 show particular instances for a first and a second preferred embodiment of what will be called a restrictive blind signature protocol. This inventive concept ensures that certified information is obtained in a blinded way, yet a certain structure in the message that was used as input to the protocol is still present in its blinded form (upon which a signature is computed by the user at the end of the protocol), regardless of the blinding transformation applied to it by the user. That is, the user can blind the input message of the protocol in a way that is sufficient to ensure untraceability of the blinded form and the corresponding signature, yet cannot get rid of certain information contained in the input.

All these flowcharts have the same structure, as will be readily apparent to those of skill in the art. As will be described in detail in the detailed description of the invention, they are all constructed by means of one of two inventive techniques for constructing such protocols based on identification protocols of a particular type well-known in the art. The flowcharts show the certifying party, , performing transformations on the input m to the protocol, defined by his secret key and responsive to a challenge of the user, . The actions of serve to blind the input m to an output m', and to compute a corresponding signature by using the information supplied by .

FIGS. 5 and 18 show a protocol for the first and second preferred embodiments respectively, for proving knowledge of a representation of a number A to another party.

The other flowcharts are based on various inventive techniques for combining the restrictive blind signature protocols with the proofs of knowledge of a representation in such a way that the output m' of the former is used as the number A in the latter, such that the contained information in m' is in fact a function of the numbers in the representation that proves knowledge of. The usefulness of this derives from the fact that can install credentials in what is known to be the contained information in m that will be conserved while blinding; the representation the user performs the proof of knowledge for then still relates to the same credentials.

In the detailed description it will be shown how these basic protocols can be used to prove the presence of various kinds of structures in the representation known of A by any party.

FIG. 6 shows how a restrictive blind signature protocol can be used to issue pseudonyms in credential mechanisms without needing the cut-and-choose technology. A number u.sub.i is encoded by the certifying party into the part of the input of the protocol that is known to be conserved while blinding the input; this number is different for each user. In this way, each user, , can obtain many pseudonyms for use at organizations that are all related, since the same number u.sub.i is encoded in the representations known by of the pseudonyms.

FIGS. 7 and 8, and likewise FIGS. 19 and 20, show the withdrawal protocol and payment protocol for a basic off-line cash system. As will be appreciated, no ad hoc constructions are applied in these figures; FIGS. 7 resp. 19 are in effect minor modifications of restrictive blind signature protocols of FIGS. 2 and 14 respectively, and the payment protocols are in effect minor modifications of the protocols for proving knowledge of a representation. Paying twice with a withdrawn coin enables computation of the representation of A from the responses sent by the user in the payment protocol, and hence of the information contained in the input m to the withdrawal protocol. FIGS. 24 and 25 show the withdrawal protocol and payment protocol in the second preferred embodiment when another restrictive blind signature protocol is used, namely that of FIG. 23. As can be seen, hardly any modifications are needed. This illustrates the object of the invention to develop a compact set of algorithms and data structures that is robust under modifications and substitutions of other restrictive blind signature schemes. Furthermore, by setting the random choices of the computing device to fixed values, privacy can be switched off; in that case the bank can compute c, and no interaction in the withdrawal protocol is needed. As will be appreciated, this means that privacy can be made optional without needing additional algorithms or data structures.

The protocols of FIGS. 9 and 10, and likewise those of FIGS. 21 and 22, show the withdrawal protocol and payment protocol for an off-line cash system in case tamper-resistant user-modules are applied. As before, this extension is realized in effect by applying slight modifications to the withdrawal protocols and payment protocols of the basic cash system. As will be appreciated, the shop, , in the payment protocols need not even be aware that a third party is taking part. Clearly the fact that no different protocol is needed is quite advantageous. Likewise, the actions that the bank must perform in the withdrawal protocol are also independent of whether the tamper-resistant part is used; the actions for the bank differ only from those in the basic system in a set-up phase that need be performed only once. The actions that need be performed by the tamper-resistant part are very limited. In fact, in the ensemble of withdrawal and payment protocols the actions of the tamper-resistant part are exactly those of the identification scheme that can also be used to construct the restrictive blind signature protocols which underly the withdrawal protocol. Yet, the user needs the assistance of the tamper-resistant part in order to compute the responses expected by the shop in the payment protocol. At the same time, not only is it impossible for the tamper-resistant part to leak additional information to or , or vice versa, it is even impossible for the tamper-resistant part, the bank and to develop during the withdrawal and payment protocols numbers that are correlated; such numbers would enable tracing of payments of the user in case the tamper-resistant part is ever revealed to the bank. A further feature of the protocols is that the halting channel can be prevented, so that not even one bit of information can be leaked by halting (or delaying transmissions). To this end, in the payment protocol the user must then compute the challenge d from by himself, as will be explained in the detailed description. In that case, all the interaction between the tamper-resistant part and the computing device of the user is merely pre-processing. In fact, the basic system is just a special case of this extension; by fixing the random numbers and secret keys of the tamper-resistant part to 0 for exponents and 1 for numbers in the base, "degeneration" to the basic system takes place.

FIGS. 29 and 30 show similar protocols for the case when another restrictive blind signature protocol is used and the same remarks apply.

FIGS. 11, 12, and 13, and likewise FIGS. 31, 32, and 33, show protocols for the dealing with electronic cheques. The respective first protocols show the withdrawal of a cheque; they are, again, very similar to the withdrawal protocols of the basic system. The main difference is that the user performs additional actions that result in a number m that is multiplied by the bank with m.sub.1 to obtain the input to the protocol. This is an example of a general technique made possible by repeated use of restrictive blind signature protocols that allows the certifying party to install new credentials into a number, without it needing to know what the credentials in the number are. The respective second protocols describe the payment protocol for cheques, these being once more very similar to the payment protocol in the respective basic systems. The respective third protocols are new: they allow the user to obtain a refund for the part of the cheque that was not spent in the payment protocol. As will be appreciated from the detailed description, this protocol is in effect a slight modification of the protocol for proving knowledge of a representation.

Finally, FIG. 34 shows a protocol for opening an anonymous account. This protocol must precede the withdrawal protocol of the cash system, without needing any further modifications. As will be appreciated from the detailed description, this protocol is in effect a restrictive blind signature protocol.

The flowcharts in the figures are all straightforwardly derived from more general inventive techniques applicable to restrictive blind signature protocols. These will be described in the detailed description, and they can be applied to construct general credential mechanisms. For example, the extension to cheques is based on two such techniques: the first consists of the ability of the certifying party to install new credentials by taking a function of a number as input to the protocol, this function being determined by itself. In FIGS. 11 and 31 this function is a simple multiplication of m by a number determined by the user. The extension to anonymous accounts serves as another example: this is based on the fact that the output of an earlier execution of the protocol can be used as the new input to a later execution of the protocol. Another example is the technique to prevent framing: this stems directly from the fact that restrictive blind signature protocols exist for which the certifying party does not need to know the information contained in the input.

A further illustration is provided by the fact that the cash systems are in fact a method for transferring certified information that may only be shown a limited number of times between organizations, such that one can transfer the information to any organization regardless of whether one has a pseudonym with that organization. The restrictive blind signature protocols allow for general techniques to transfer limited-show credentials as well as credentials that may be shown as often as desired (in the detailed description actually limited-show credentials will be separated further into one-show and multi-show credentials), as well as for general techniques that allow credentials to be shown only to all organizations at which one has a pseudonym, to only one such organization, or to any organization at all. In total, this gives six combinations, of which the cash systems are only one. Using the techniques such as to realize one of the five other combinations, cash systems in which users can only pay under pseudonym can be constructed (see detailed description). As will be obvious to those of moderate skill in the art, one can readily combine these two types of cash systems, such that users can pay at certain organizations regardless of whether they have pseudonyms, and at others only if they have a pseudonym at that organization.

The broad applicability of these general techniques to construct credential mechanisms will be appreciated in particular when the sections in the detailed description that deal with application to credential mechanisms are read.

DETAILED DESCRIPTION OF THE INVENTION

While it is believed that the notation of FIGS. 2 to 34 would be clear to those of ordinary skill in the art, it is first reviewed here for definiteness.

The actions performed by the parties participating in the protocols are grouped together into flowchart boxes. The party performing the actions described in a flowchart box is indicated by the column that box is in. The columns are labeled by a symbol denoting the type of party.

The symbol ".rarw." denotes assignment, meaning that the variable or symbol on its left-hand side is assigned the value or values on its right-hand side to. Several of such assignments do not imply that actually storage space must be reserved; it might be merely an intermediary computation performed in RAM with further operations successively performed on it.

Another operation is a test for equality, which is indicated by the symbol. As is common in the art, the protocol halts in case the equality does not hold. Likewise, the sign denotes a test for inequality.

The symbol .epsilon..sub. indicates that the number or numbers on its left-hand side are chosen from the set on its right-hand side according to a uniform probability distribution, and independently of anything else. Preferably a physical random number generator should be used for this, possibly in conjunction with additional post-processing. In practice, pseudo-random techniques may be used. As will be obvious to those of ordinary skill in the art, a better approximation by the sampling distribution of the independent uniform distribution guarantees better privacy or security. "Generating a number at random from a set" ("generating a random number") in the text indicates the same. In case the symbol .epsilon. is used, it indicates that the number d need not be determined according to an independent uniform distribution; in particular, the number on the left-hand side may be determined from the set on the right-hand side in a manner specified in the corresponding description of the box in the text.

Another action is denoted by the word "Send," followed by a colon and one or more numbers. This indicates that those numbers are sent by the party performing the actions described in the box to another party participating in the protocol. The receiving party is indicated by the connections between the flowchart boxes.

Some actions have to be performed only one for each participating other party or parties. Such actions are displayed between square brackets.

Various actions are described by words, such as "Split m' into A,B," sign(m), "Verify sign(m)." In such a case, the corresponding description in the text specifies the meaning of the action. In any case, this will only be done in case the same actions have already been displayed in foregoing flowcharts.

In the general description of restrictive blind signature protocols, the certifying party will be denoted by and the user by .

In the particular case of off-line cash systems, the various participants in the protocols will be denoted by the following calligraphic symbols:

=bank (certifying party)

=account holder user

=shop (organization)

=tamper-resistant bank-module

Turning now to FIG. 1, a description of the apparatus in which the invention is to be implemented will now be described in detail.

Block 1 represents a computing device held by the type of party referred to as user. It contains processing means 1b, memory means 1a, data entry means 1c, and data/message display means 1d. These means are interfaced by suitable means not shown for clarity; only the interface between memory means and processing means is indicated by a double-sided arrow. Such interface means are well known in the art. Block 1 also contains two communication interfaces to be described.

The computing device of the user may come in various sizes and capabilities. It can be a smart card, and so be of the size of current credit cards. In case the smart-card does not have its own power supply, as is currently the case, it might be supplied with current by connecting it to other means in case it must perform actions, such as by another party in a protocol or by another device owned by the user.

The computing device of the user can alternatively be a palm-top computer, a personal computer, or a more powerful workstation. It can even be a part of a multimedia apparatus such as an interactive TV set or the remote control thereof. It might also be a smart telephone, facsimile or the like. As will be appreciated by those of ordinary skill in the art, the embodying apparatus can come in a great many forms, only limited by ones imagination.

Clearly, the data/message display will differ in accordance with the embodiment of the device of the user. For example, for a personal computer it can be the monitor, and for a smaller embodiment such as a palmtop computer it can be an LCD dot matrix display. The same holds for the data entry means: for a personal computer it will be the keyboard, whereas for a smart phone it can be the dialing buttons.

The communication interfaces might be by direct electrical connection, or by electro magnetic waves, sound waves, and the like. For example, in case the device of the user is a personal computer in a Wide-Area-Network, data can be send through the wires of the network, and for a remote control device infra red technology can be used.

Of course, any suitable technologies for accomplishing these functions may be used.

As will be appreciated, the computing device of the user can be fully under his own control; he might even build it himself, or buy it on the free market.

In addition, it is conceivable that the computing device of the user offers its owner protection against theft and the like. Furthermore, a user may own various such computing devices and transfer the data stored in one such device to another before performing another protocol. For such reasons, in the detailed description the actions in the boxes will be described as being performed by the type of party that is involved, rather than by its computing device. That is, when the description specifies for example the user to send certified information it received earlier to a shop, these actions are performed by one of his computing devices. Likewise, will be referred to as "user" or "he," whereas the actual computational actions are performed by the computing device. This convention is common usage in the art (where computations are performed by parties referred to as "Alice," "Bob," and so on), and will not cause any ambiguities when read in the context of the description. For example, when it is said that "the user opens an account by generating a random number, sending this to the bank, and identifying himself by means of a passport," it will be clear that for showing a passport the user may have to show up at the local bank in person; the bank the passport is shown to will then also be a person, employed by the bank, or perhaps an apparatus checking fingerprints, etc., of the user. The part of generating the random number and sending it to the bank is performed by the computing device of the user. The same convention is also taken with respect to the other types of participant, since, for instance, in the off-line cash systems the bank verifies the identity of the user, computes signatures, verifies the validity of deposited databases, and takes appropriate action in case an account holder has double-spent.

Block 2 represents a computing device controlled by the types of party referred to as a certifying party and an organization. It contains memory means 2a and processing means 2b. In case the device belongs to a certifying party, it is very well conceivable that there are no means for data/message entry and display, since its only task is to generate signatures on input messages, that it first may have to verify. In case it is a computing device of an organization, it is conceivable that there are also display means, perhaps very rudimentary to merely represent Boolean values to convey the result of a test.

Again, an almost unlimited number of embodiments of this device is conceivable. For example, in a cash system it can be a tamper-resistant part generating the signatures to issue money, it can be some informational facility accessed remotely be telecommunications or the like. In particular, it can also be the same apparatus as that of Block 1, which is particularly conceivable in case an organization is also a user.

The processing means of the computing device of Block 2 can communicate with the processing means of the computing device of users.

Block 3 is an, optional, computing device. It contains memory means 3a and processing means 3b. It is intended to be needed by the computing device of users in order to succesfully complete protocols with organizations and certifying parties, and so it offers organizations and certifying parties better control over the actions performed by users. Since its purpose is to maintain at least some secrets from the user that holds it, in order to ensure that its assistance to successfully perform protocols cannot be avoided, it must in particular be tamper-resistant.

Its processing means can commicate with the processing means of the user that owns it. However, during executions of protocols in which it must assist the user to complete the protocol, it should not be able to communicate directly to organizations and certifying parties. Its only way to convey information to the "outside" world is through the computing device of its owner.

Again, the tamper-resistant device can be of many forms. For instance, in case the computing device of its holder is a personal computer or workstation, it might be a device connected to the parallel port thereof, or it can be a so-called PCMCIA-card inserted in an opening of a palm top computer or remote control for an interactive T.V. set.

Restrictive blind signature protocols.

The requirement for a blind signature protocol, well-known in the art, is that may not get any clue about the numbers that obtains at the end of the protocol other than that they can be used as certified information. More specifically, given the set of numbers with a corresponding signature, the numbers that has viewed in the execution of the protocol do not provide any information about the numbers and signature that has obtained at the end of the protocol.

A restrictive blind signature protocol is a blind signature protocol that satisfies an important additional requirement. A detailed description follows. At the start of the protocol (say, in a set-up phase) two functions, denoted by f.sub.1 and f.sub.2, are chosen.

At the start of the protocol and agree on a number m that is henceforth called the input of the protocol. This number is such that at least knows a k-tuple (a.sub.1, . . . , a.sub.k) such that m=f.sub.1 (a.sub.1, . . . , a.sub.k).

At the end of the restrictive blind signature protocol can compute a number m' (which will be referred to as the output of the protocol) with a corresponding digital signature of , such that he knows a l-tuple (b.sub.1, . . . , b.sub.l) such that m'=f.sub.2 (b.sub.1, . . . , b.sub.k). The important characteristic is that there exist at least two non-constant functions I.sub.1 and I.sub.2 associated with the protocol such that inevitably I.sub.1 (a.sub.1, . . . , a.sub.k) is equal to I.sub.2 (b.sub.1, . . . , b.sub.l), independent of the transformations applied by during the protocol.

For a function f and number m, henceforth f.sup.-1 (m) will be referred to as a representation of m with respect to f. For example, if f is a hash-function such that there is a plurality of arguments that are mapped by f to the same output then there exist many representations for outputs. In case such an f is a collision-free hash-function, meaning that it is infeasible to determine two different argument that map to the same outcome, then a user can only know at most one representation. In that case it makes sense to speak of a user knowing a representation of a number. The same is also the case if f is a one-way function that is one to one.

By "information contained" in a representation that a user knows of a number with respect to a function f is meant any function I of the representation. Clearly, there is lots of information contained in a representation, since there are a lot of different functions of the numbers in the representation.

With this terminology, which will be used henceforth, a restrictive blind signature protocol is a digital signature protocol in which can fully blind the number m to a blinded number m' such that the requirement for a blind signature protocol is met, but there inevitably exists certain information contained in the representation he knows of m that is equal to certain information contained in the representation he knows of m', independent of how he blinded m to m'. As will be obvious to those of ordinary skill in the art, this actually means that he cannot blind independently at random each number in the representation of m.

In general, m and m' can be vectors of numbers, such that knows a certain representation of each of the numbers in the vector.

As will be obvious to those of ordinary skill in the art, one can usually determine the functions f.sub.1 and f.sub.2 to be the same function, and one is then speaking about representations of m and m' with respect to the same function f. Likewise, it is often possible to determine the functions I.sub.1 and I.sub.2 to be equal to the same function. Examples of this are given in the descriptions of two preferred embodiments.

Proving knowledge of relations between the numbers in the representation of m'

There is no practical reason to use restrictive blind signature protocols without using an additional testing protocol (the opposite is not true; as will be obvious to those of ordinary skill in the art, the various techniques for testing that will be described in each of two sections on application to credential mechanisms are of interest in their own right). That is, associated with restrictive blind signature protocols is the fact that can prove to "organizations" various statements about the numbers in I.sub.2 (b.sub.1, . . . , b.sub.k), where (b.sub.1, . . . , b.sub.l) is the representation he knows of m' with respect to f.sub.2. The basic idea is that the numbers in I.sub.2 (b.sub.1, . . . , b.sub.l) can each denote a certain type (piece) of information. For example, these numbers may be only zero or one, and then the value of b.sub.i can denote whether one has or does not have a piece of information of type i (type i might for instance stand for "driver's licence"). In general, b.sub.i 's of many distinct values can be used to represent types of information or, say, "quantifications" of a certain type such as hight of income.

Since I.sub.1 (a.sub.1, . . . , a.sub.k)=I.sub.2 (b.sub.1, . . . , b.sub.l), this actually means that did not make up these pieces of information himself if he can show a corresponding signature. After all, himself has accepted m, of which knows the representation (a.sub.1, . . . , a.sub.k), as input to the restrictive blind signature protocol. Therefore, by proving relations between the numbers in I.sub.2 (b.sub.1, . . . , b.sub.k), is actually proving that these relations hold for pieces of information certified by . Note that need not know what this representation is.

The importance of the inventive techniques derives in part from the fact that one can let prove knowledge of a representation he knows of a number (on which he has a signature) with respect to the function f.sub.2 ; more generally, by taking a suitable mathematical function of f.sub.2, and letting prove knowledge of a suitable other function of the number with respect to the function of f.sub.2, one can in effect have him prove a broad range of functions of the representation he knows. This will be described in detail in the sections on application to credential mechanisms.

Differences with "one-show" blind signatures

The one-show blind signatures known in the art can be considered as a special type of restrictive blind signatures: they only serve as a means to determine the identity of a user that shows a piece of information more than once--showing the signature twice reveals the information contained in the certified information. As will be appreciated when the detailed description is studied in conjuction with the figures, in restrictive blind signatures there need not be such a limit. Restrictive blind signature schemes can serve much broader applications. Furthermore, restrictive blind signatures can be used to prove relations between the parts of the information contained in the certified information without revealing any additional information.

The only known technique for the construction of one-show blind signatures uses the well-known cut-and-choose technique. This consists of performing a great many "ordinary" blind signature protocols in parallel. The user must in the third transmission "open" a substantial part of all the blinded numbers he sent in the first transmission, i.e. show to the certifying party that he indeed included the correct pieces of information in each of them. The reason for this is that there are no restrictions on the blinding transformations that the user can perform that are inherent to the mathematics. The unopened parts (or the product thereof) are signed in a fourth step by the certifying party, and then unblinded by the user as in the ordinary blind signature protocols. Since the user could not know in advance which numbers the certifying party would request him to open, the certifying party with (hopefully) high probability is ensured that the unopened numbers also include the correct pieces of information. As will be appreciated by those of ordinary skill in the art, restrictive blind signature protocols do not have to make use of such an inefficient technique, of which it also will be hard to prove the security; hence, they can be orders of magnitude more efficient.

An inherent feature of restrictive blind signature protocols is that the output of a previous execution of such a protocol can repeatedly (recursively) be used as input to a new execution, such that the information contained in the various inputs and outputs is inevitably conserved throughout. This is most obvious if f.sub.1 =f.sub.2 and I.sub.1 =I.sub.2. As will be appreciated, in case f.sub.1 and f.sub.2 are not equal, it most often is the case that they can be adjusted such that they are equal. The same holds for I.sub.1 and I.sub.2. The repeated use of the restrictive blind signature protocol as in the first sentence of this paragraph is henceforth called "transitivity." The contained information even can be modified under control of the certifying party by using a function of a previous output as input to a new execution of the protocol. This very powerful technique can be put to use in many applications, as will be shown in great detail for two preferred embodiments.

As will be appreciated, as special use of restrictive blind signature is to construct one-show blind signatures. However, the most powerful use of restrictive blind signatures will be shown to stem from the general techniques that cannot be achieved with one-show blind signatures.

In order to explain the invention, two preferred embodiments will now be described in great detail. Each of these embodiments will be described in turn. The additional notational conventions used only in a particular embodiment will be described at the start of the description of that particular embodiment.

Each of these two preferred embodiments is characterized by a specific choice for the functions f.sub.1 and f.sub.2. Although these functions can as well be chosen to be different, one can point out in both preferred embodiments a function f that is equal to both f.sub.1 and f.sub.2. As will be appreciated from the descriptions, this has some advantages when using the output of a previous execution of the protocol as the new input to a next execution of the protocol.

The respective descriptions are organized as follows. For each preferred embodiment various realizations of restrictive blind signature protocols are described, based on either one of two techniques described in text. Following this is a description of how can prove knowledge of a representation of m' with respect to a function f, and how a plurality of parties can do this in cooperation. These protocols form the basis for the construction of protocols that can be used to prove a diversity of relations between the numbers in I.sub.2 (b.sub.1, . . . , b.sub.k), where (b.sub.1, . . . , b.sub.k) is the representation knows of m' with respect to f. These latter protocols are extensively described in the section concerning the application of restrictive blind signatures to so-called "credential mechanisms," including protocols for transferring one-show credentials between pseudonyms. Finally, for both preferred embodiments an off-line electronic cash system is described in great detail; many of the described techniques are applied here once more.

As will be appreciated to those of ordinary skill in the art, the example protocol descriptions in each of the two preferred embodiments illustrate many particular of the herein disclosed inventive techniques and concepts, but they are only intended to be suggestive and not limiting in any way.

FIRST PREFERRED EMBODIMENT

1 Introduction

In the first preferred embodiment computations are performed in a multiplicative group modulo n, denoted by *.sub.n, with n being the product of two distinct large primes. The RSA problem, mentioned in the description of the prior art, seems infeasible to solve in such a group. Since the order of the group may only be known to the certifying party, the computations in the exponents are performed modulo a certain number v that is not a proper divisor of the order of *.sub.n. Hence expressions involving div v will show up, due to the relation a=a mod v+v (a div v) for a .epsilon. .

Since multiplications and divisions in *.sub.n are always performed modulo n, the operator mod n will never be mentioned explicitly. So for example Y.sup.u.sbsp.1 stands for Y.sup.u.sbsp.1 mod n. In case other modulo operations are involved, the modulo operator is explicitly mentioned (like in for example r.sub.1 =x.sub.1 +x.sub.2 c mod v). If numbers are chosen from a group, always the smallest positive remainder is implied. For instance, a .epsilon..sub. *.sub.n implies that a is chosen at random from the subset {1, . . . , n-1} containing the numbers co-prime with n (in practice, this set can be taken to be {1, . . . , n-1}).

For the restrictive blind signatures in this preferred embodiment use is made of the fact that, given a vector of numbers (Y.sub.1, . . . , Y.sub.k), all unequal to 1, from the group, and a random elements A from the group it seems infeasible to compute a vector (a.sub.1, . . . , a.sub.k ; a.sub.k+1) (not equal to (0, . . . , 0; 1) in case A=1) such that Y.sub.i.sup.a.sbsp.1 . . . Y.sub.k.sup.a.sbsp.k a.sub.k+1.sup.v =A, where a.sub.1, . . . , a.sub.k .epsilon. .sub.v and Y.sub.1, . . . , Y.sub.k,a.sub.k+1 .epsilon. *.sub.n. In the vector-notation the symbol ";" is used to stress that the number on its right-hand side is from a different set than the numbers on its left-hand side.

In terms of the general description of restrictive blind signatures given previously the functions f.sub.1 and f.sub.2 can both be defined by f.sub.i (a.sub.1, . . . , a.sub.k+1)=Y.sub.1.sup.a.sbsp.1 . . . Y.sub.k.sup.a.sbsp.k a.sub.k+1.sup.v, for i=1,2. That is, f.sub.1 can be chosen equal to f.sub.2. Doing this in fact is commonly possible, as will be obvious to those of ordinary skill in the art. Henceforth, this function will be denoted simply by f.

At the start of the protocol knows a vector (a.sub.1, . . . , a.sub.k ; a.sub.k+1) such that f (a.sub.1, . . . , a.sub.k+1)=m. This vector is called a representation of m with respect to (Y.sub.1, . . . , Y.sub.k ; v).

In the next section, FIGS. 2 and 3 two different types of restrictive blind signature protocol will be described. Here, too, can the functions I.sub.1 and I.sub.2 be chosen to be the same functions, and they will hence be denoted by I. In the first two flowcharts, the function I is (for example) defined by I(a.sub.1, . . . , a.sub.k+1)=(a.sub.1 mod v, . . . , a.sub.k mod v). (As will be clear to those of ordinary skill in the art, functions of the numbers in I(a.sub.1, . . . , a.sub.k) are also examples of such a function!) This means that in the protocol can only modify a.sub.k+1, and that modulo v he cannot modify the other numbers. Notice that the ability to arbitrarily modify a.sub.k+1 is sufficient to guarantee the statistical independence between m and m', as is required by a blind signature protocol. In terms of the general description of restrictive blind signatures, the information "contained" in m is the vector (a.sub.1 mod v, . . . , a.sub.k mod v).

In the protocol of the flowchart of FIG. 4, and its variant described in the text, has more freedom in blinding the numbers in the representation. In these protocols one has (for example) I(a.sub.1, . . . , a.sub.k+1)=(. . . , a.sub.i /a.sub.j mod v, . . . ), for 1.ltoreq.i.noteq.j.ltoreq.k. In other words, it is inevitably the case that there exists a number t in *.sub.v such that b.sub.i =a.sub.i t mod v, for 1.ltoreq.i.ltoreq.k.

Following this, it will be explained how the general technique used to construct these four protocols can be used to construct other restrictive blind signature protocols.

As will be obvious to those of ordinary skill in the art, the protocols can be modified in various obvious ways. In the restrictive blind signature protocols one can take v to be either composite or prime. In the application for off-line electronic cash systems it will be assumed that v is a prime number co-prime with the order of *.sub.n ; however, here as well v may be chosen to be of another form. For instance, v=p'q' can be used, for prime numbers p',q' such that one of both properly divides the order of *.sub.n.

Furthermore, n can be taken to be the product of more than just two prime numbers; this however only weakens the security of the system. Such modifications are well-known in the art. It is noted that various suitable choices for n are known in the art.

2 Restrictive blind signatures

Turning now to FIG. 2, the first flowchart of a restrictive blind signature protocol for the first preferred embodiment will now be described in detail.

In a set-up phase, preceding executions of the protocol, has made publicly known a triple (n,v,X.epsilon. *.sub.n). The number n is the product of two large prime numbers, suitable choices for such a composite being well-known in the art. The number v is a prime number co-prime with the order, denoted by .phi.(n), of the group *.sub.n. As will be obvious to those of ordinary skill in the art, and as explained earlier, other choices of v can also be used; v can even be a power of two. Finally, X is an element of large order in *.sub.n. stores the inverse of v modulo .lambda.(n) (in the sequel this number will be denoted in the exponent by 1/v) as its secret key.

also makes publicly known a function . is a hash-function, preferably "collision free," that maps two numbers from *.sub.n to a number in .sub.v. "Collision-free" means that not only is it infeasible to compute inverses but it also is infeasible to compute two distinct pairs of numbers that are mapped by to the same outcome. Such functions are well-known objects in the art.

At the start of the protocol a number m from *.sub.n is decided on that should be known to both and . A digital signature of on a number m in *.sub.n is defined to be a pair of numbers (a,b) in *.sub.n .times. *.sub.n such that the v-th power of b is equal modulo n to the product of (Xm).sup.c and a, where c denotes the image of (m,a) under the hash-function .

Box 21 shows generating a random number a in *.sub.n, which it then sends to .

The first, third and fourth lines of Box 22 show generating two random numbers s,t, both in *.sub.n, and a random number u .epsilon..sub. .sub.v. The box in the second line shows computing the blinded form m' of m by multiplying the v-th power of s by m. Furthermore, the fifth line of the box shows how computes the blinded form a' of a, by using the numbers t and u. Next a "challenge" c' is computed as the image of (m',a') under the hash-function . In the seventh line it is shown how uses the previously generated random number u to blind this challenge by adding modulo v the number u to it. The outcome of this transformation, denoted by c for clarity, is then sent by to .

Box 23 shows how , after receiving challenge c from , computes the "response," which will be denoted by b. Having computed this number, sends it to .

Box 24 defines the actions of after receiving response b from . The first line shows that verifies whether the v-th power of b equals modulo n the product of a with a number that can compute from the publicly known information. If this test holds then "accepts," since it must be the case that computed the correct response. then computes a transformed form of b, which is denoted for clarity by b', by using the publicly known information, the input m to the protocol, and the numbers generated in the protocol. As is common in the art, the box does not display the action of in case the verification in the first line does not hold, since these actions do not influence the correctness of the protocol; may complain or take other appropriate action, various such actions being conceivable and depending on the implementation environment of the protocol.

If both and followed the description of the protocol (and hence accepts in Box 24), then the pair (a',b') is a digital signature of on m'. Hence, it can be verified by anyone, by using the information made publicly known. As will be appreciated, the pair consisting of m' and the signature (a',b') meets the requirement for a blind signature described earlier.

It will be obvious to those of ordinary skill in the art that, without further restrictions, signatures obtained in the above manner are easy to forge. This is not a problem at all, since what matters for restrictive blind signatures is the information "contained" in the signed message m': must know a representation of m'. Assuming that at the start of the protocol knows a representation (a.sub.1, . . . , a.sub.k ; a.sub.k+1) of m with respect to a publicly known vector (Y.sub.1, . . . , Y.sub.k ; v), and that at the end of the protocol knows a representation (b.sub.1, . . . , b.sub.k ; b.sub.k+1) of m' with respect to the same vector, the number a.sub.i will inevitably be equal to b.sub.i modulo v for all i such that 1.ltoreq.i.ltoreq.k, if only does not know a representation (c.sub.0, . . . , c.sub.k ; c.sub.k+1) (not equal to (0, . . . , 0; 1) of 1 with respect to (X,Y.sub.1, . . . , Y.sub.k ; v). This can easily be taken care of by by for example generating X and all Y.sub.i 's at random.

Several remarks are in order here. As will be appreciated, need only know the v-th roots modulo n of both X and m in order to properly perform his part of the protocol. In particular, does not need to know the prime factorization of the modulus n. To perform the action in Box 23, in Box 21 should generate the number a in such a way that it knows its v-th root modulo n. This can be easily accomplished by generating at random a number a.sub.0 in *.sub.n and taking a equal to the v-th power modulo n of a.sub.0.

As will be obvious to those of ordinary skill in the art, the assignments made by in the fifth and seventh lines of Box 22 to a' and c, and c, and that made to b' in the second line of Box 24 can be slightly modified in various ways.

In the foregoing description of the flowchart the digital signature is only on one number, denoted by m'. A simple yet important modification suffices to obtain a digital signature on several numbers. If the signature should not only correspond to m' but also to k other numbers, which will be denoted by B.sub.1, . . . , B.sub.k, for a certain positive integer k, then it suffices that in the sixth line of Box 22 compute c' as the image of (m',B.sub.1, . . . , B.sub.k,a') under the hash-function . The requirements for the hash-function are the same as before, the only difference being that must now operate on an argument consisting of k+2 numbers. It is noted that most hash-functions known in the art can take any number of elements as an argument, in which case one can use the same hash-function. A signature on (m',B.sub.1, . . . , B.sub.k) in this case is a pair (a',b') of numbers in *.sub.n .times. *.sub.n such that the v-th power of b' modulo n equals (Xm').sup.c' a', where c' now is the image of (m',B.sub.1, . . . , B.sub.k,a') under the hash-function. Note that the numbers B.sub.i can be chosen from any set.

Furthermore, a signature on a number m in *.sub.n can alternatively be defined (in a somewhat more efficient way) as a pair (c,b) in .sub.v .times. *.sub.n such that c equals the image of (m,b.sup.v (Xm).sup.-c) under the hash-function . As will be obvious to those of ordinary skill in the art, this definition is equivalent. In particular, its verification relation can be substituted in place of the verification relation specified in the description of the set-up phase for the protocol.

The hash-function is not necessarily such that for each element in .sub.v there is a number that is mapped to it by ; may as well map its arguments to, say, .sub.2.spsb.t, where the "security parameter" t is of an appropriate length, probably set beforehand by .

As is well-known by those of ordinary skill in the art, the verification relation b.sup.v =(Xm).sup.c a in the first line of Box 24 can be implemented such that one side of the equality sign does not require any computations. The expression on the other side can be efficiently computed by using for example "simultaneous repeated squaring" techniques. So for Box 24 the verification relation can be rewritten as, say, (b.sup.-1).sup.v (Xm).sup.c =a.sup.-1 ; in that case it is preferable that send in Box 21 the inverse modulo n of the number a instead of a itself, and the inverse modulo n of b in Box 23; this avoids computation of inverses by . For reasons of clarity in this application none of the verification relations will be described in such a form.

As will be appreciated, all these remarks also apply to all the other flowcharts. In particular, as noted, one can modify the verification relation defining a signature in an equivalent way each time.

Turning now to FIG. 3, a second flowchart of another restrictive blind signature protocol for the first preferred embodiment will now be described in detail.

The set-up is the same as for the previous flowchart, with the only distinction that should never map its argument to zero. This is merely a technical detail needed to rigorously prove information-theoretic privacy. A digital signature of on a number m in *.sub.n is defined to be a pair (a,b) in *.sub.n .times. *.sub.n such that the v-th power modulo n of b is equal to Xm(a).sup.c. Here, as before, the symbol c denotes the image of (m,a) under . Equivalently, as explained in the description of the previous flowchart, (c,b) can instead be taken to be the signature.

Box 31 shows generating a random number a in *.sub.n, which it then sends to .

The first and third lines of Box 32 show generating two random numbers s,t, both in *.sub.n, and the fourth line shows generating another random number u in *.sub.v. The second line of the box shows how computes the blinded form m' of m by using the random number s. Using t and u also computes a blinded form a' of a. then computes the challenge, denoted by c', as the image under of (m',a'). Finally, computes the blinded challenge c by multiplying the number c' modulo v with u, and sends it to .

Box 33 indicates how computes the response b as a v-th root modulo n of an expression involving the challenge c it just received. then sends b to .

Box 34 details in the first line the testing of the response of and in the second line the final computation needed to obtain a signature on m'. Specifically, the first line shows how raises b to the power v and compares the result for equality with a product involving the publicly known information, the challenge, and the input m of the protocol. When this test completes successfully, computes a number b', which in fact is the blinded form of b. As before, if the test does not hold, takes other action.

The remark made at the end of the description of the previous flowchart also applies here. That is, if it is assumed that at the start of the protocol knows a representation (a.sub.1, . . . , a.sub.k ; a.sub.a+1) of m with respect to (Y.sub.1, . . . , Y.sub.k ; v), and at the end knows a representation (b.sub.1, . . . , b.sub.k ; b.sub.k+1) of m' with respect to the same vector, then a.sub.i will inevitably equal b.sub.i modulo v for all i such that 1.ltoreq.i.ltoreq.k, if only does not know a representation (c.sub.0, . . . , c.sub.k ; c.sub.k+1) (not equal to (0, . . . , 0; 1)) of 1 with respect to (X,Y.sub.1, . . . , Y.sub.k ; v).

Turning now to FIG. 4, a third flowchart of yet another restrictive blind signature protocol in the first preferred embodiment will now be described in detail.

The set-up is the same as for the previous flowchart (FIG. 3). A digital signature of on a number m in *.sub.n is a pair (a,b) in *.sub.n .times. *.sub.n such that the v-th power of b equals (Xa).sup.c m, where c denotes (m,a). It turns out that now has somewhat more freedom in blinding the input m than in the previous two protocols, however, this is not sufficient to independently blind each number in the representation and so this also is a restrictive blind signature.

Box 41 shows generating a random number a .epsilon..sub. *.sub.n, which it then sends to .

The first, second and fourth lines of Box 42 describe that generates two random numbers s .epsilon..sub. .sub.v, u .epsilon..sub. *.sub.v and a random number t .epsilon..sub. *.sub.n. Using s,t, blinds m to a number m' in the way indicated in the third line. Using s and u, also blinds the number a to a number a' in the way specified in the fifth line. then computes the challenge c' by applying the hash-function to (m',a'). Finally, computes the blinded challenge c by multiplying c' modulo v with u, and sends c to .

Box 43 shows computing the response b corresponding to the challenge c it received from . then sends this number to .

The first line of Box 44 indicates that accepts if and only if the v-th power of b equals an expression involving the input m to the protocol, the challenge, and the publicly known information. If that is the case, computes a blinded form of b, which as before is denoted by b'.

If it is assumed that at the start of the protocol knows a representation (a.sub.1, . . . , a.sub.k ; a.sub.k+1) of m with respect to (Y.sub.1, . . . , Y.sub.k ; v), and at the end knows a representation (b.sub.1, . . . , b.sub.k ; b.sub.k+1) of m' with respect to the same vector, then a.sub.i /a.sub.j will inevitably equal b.sub.i /b.sub.2 mod v for all distinct i,j such that 1.ltoreq.i,j.ltoreq.k, if only s is not equal to 0 mod v and does not know a representation (c.sub.0, . . . , c.sub.k ; c.sub.k+1) (not equal to (0, . . . , 0; 1)) of 1 with respect to (X,Y.sub.1, . . . , Y.sub.k ; v).

As will be appreciated, in the same way that the second flowchart (FIG. 3) is closely related to the first flowchart (FIG. 2), there is also a restrictive blind signature protocol closely related to the present flowchart. The set-up for that protocol is the same, except for the distinction that a digital signature of on a number m in *.sub.n is now a pair (a,b) in *.sub.n .times. *.sub.n such that the v-th power of b is equal to Xa(m).sup.c, where again the image of (m,a) under the hash-function is denoted by c. has exactly the same freedom in blinding m as in the third flowchart (FIG. 4). The remarks made with respect to the flowchart of FIG. 4 hence also apply here. Since the only difference is that the assignments made by in Box 42 and Box 43 to a',c and b' have to be modified in a way obvious to those of ordinary skill in the art, a detailed description is omitted.

The four described restrictive blind signature protocols are all based on the signature variant of the Guillou/Quisquater identification protocol, known from Guillou, L. and Quisquater, J., "A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory," Lecture Notes in Computer Science 330, Proceedings of Eurocrypt '88, pages 123-128, and the `mirrored` variant (Ohta, K. and Okamoto, T., "A modification of the Fiat-Shamir scheme," Lecture Notes in Computer Science 403, Proceedings of Crypto '88, pages 222-243). The protocol of Guillou/Quisquater is of the so-called Fiat/Shamir type, known from Fiat, A, and Shamir, A., "How to prove yourself: practical solutions to identification and signature problems," Crypto '86, Springer-Verlag, (1987), pages 186-194.

As will be obvious to those of ordinary skill in the art, the technique used to realize the restrictive blind signatures in the previous flowcharts can be applied, at least in principle, to any identification protocol of the Fiat/Shamir type, if only one can convert it to a signature protocol by computing the challenge c as the outcome of a hash-function of, amongst others, numbers that were received earlier (this is the construction of Fiat/Shamir). To this end not but must compute the challenge c, and the input m must be multiplied (or using another mathematical operation such as exponentiation) in an appropriate way into the verification relation. For example, the verification relation in the Guillou/Quisquater scheme is b.sup.v =X.sup.c a; one then gets the verification-relation of the first flowchart (FIG. 2).

For instance, with this technique the identification protocol from Okamoto, T., "Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes," Preproceedings of Crypto '92, pages (1-15)-(1-25) can be turned into a restrictive blind signature protocol. In this identification protocol proves that he knows the secret key (s.sub.1,s.sub.2) in .sub.v .times. *.sub.n corresponding to a public key which is of the form Y.sup.s.sbsp.1 s.sub.2.sup.v mod n.

Since this is realized in the same way as in the flowcharts of FIGS. 2, 3 and 4 (again, there are in total four variants that result in a restrictive blind signature protocol), and various other protocols that are also all based on this inventive technique will be described in detail in the second preferred embodiment, a detailed description is omitted here; the described flowcharts are believed to be more than sufficient to enable those of ordinary skill in the art to apply the inventive technique to any other identification protocol of the Fiat/Shamir type.

There also exists a different technique to turn an identification protocol of the Fiat/Shamir type into a restrictive blind signature protocol. This technique consists of doubling the verification relation, where in the second verification-relation one of the numbers of the public key is replaced by the input m. As before, computes the challenge c himself. In the Guillou/Quisquater protocol one can for example use the verification relations b.sub.1.sup.v =X.sup.c a.sub.1 and b.sub.2.sup.v =m.sup.c a.sub.2 (so here X is replaced by m in the "copy" of the verification relation). Yet another example of this doubling technique is the restrictive blind signature protocol described in FIG. 23 for the second preferred embodiment. The difference with the first technique, applied in the flowcharts of FIGS. 2, 3 and 4, is that signatures that are constructed in this way cannot be forged by even if he does not need to know a representation of the signed numbers.

3 Proving knowledge of a representation

Turning now to FIG. 5, a flowchart of a protocol in the first preferred embodiment will now be described that enables to prove that he knows a representation (a.sub.1, . . . , a.sub.k ; a.sub.k+1) of a number A in *.sub.n with respect to (Y.sub.1, . . . , Y.sub.k ; v), without revealing the representation itself (so in particular the information contained in A is kept secret).

Box 51 shows generating k random numbers x.sub.1, . . . , x.sub.k in .sub.v, and a random number x.sub.k+1 in *.sub.n. He uses these to compute a number B, as specified in the third line, which he sends to .

Box 52 shows generating a challenge d in .sub.v, which it then sends to .

Box 53 indicates how computes the responses r.sub.i, for 1.ltoreq.i.ltoreq.k+1. then sends r.sub.1, . . . . , r.sub.k+1 to .

Box 54 indicates that accepts the proof if and only if a product involving the k+1 responses just received from is equal modulo n to the product of A.sup.d and B.

This protocol is a generalization of a protocol known in the art, which however serves only for the purpose of identification and signatures. As will be shown in detail, the inventive techniques allow this proof to be used as the basis for protocols that enable to prove certain mathematical relations between the numbers in the representation. This inventive concept enables the construction of efficient provacy-protecting credential mechanisms.

As is well-known by those of ordinary skill in the art, there are two basic ways to use this protocol. Firstly, it can be required that d, generated in Box 52, is at most, say, ten bits in length, and the protocol is then repeated a few times. In that case, cannot use the transcript of the execution of the protocol to prove to someone else that the proof took place; the protocol is "zero-knowledge," using well-known cryptographic terminology.

Secondly, it can be required that determine d in Box 52 as the outcome of a publicly known collision-free hash-function having as argument at least the numbers A and B, and for example also a message m. Often will then be able to compute d himself, and so not interaction is needed between and . The transcript of an execution of the protocol can now serve as a digital signature on m, A and B, and in particular it proves that the proof was performed; this is sometimes called a "signed proof" in cryptographic terminology.

In case B can be chosen in each execution of the protocol by himself, can perform the proof of knowledge of a representation of A as many times as desired without ever enabling to compute the representation he knows of A. However, if performs the protocol twice using the same number B, then can compute the representation knows of A by using two different challenges d in Box 52.

In case knows a representation of A.sub.1, and ' knows a representation of A.sub.2, then they can prove to by cooperating that they together know a representation of the number A which is the product A.sub.1 A.sub.2 of their individual numbers. To this end, in Box 51 they multiply B.sub.1 and B.sub.2, and send the outcome B to . In Box 53 they then pairwise add together their responses r.sub.i,r'.sub.i (for 1.ltoreq.i.ltoreq.k), and multiply r.sub.k+1 and r'.sub.k+1. They send the k+1 resulting responses to , who verifies them as in the flowchart of FIG. 5. As will be obvious to those of ordinary skill in the art, this modification can also be applied in case more than just two receivers are involved.

A somewhat more difficult situation occurs in case one of the two parties is not allowed to leak to information about what numbers (including A.sub.1, B.sub.1 and r.sub.i) it is using. This situation is especially of concern in case one computing device represents the interests of an organization or a certifying party. The technique used to construct this protocol will be described in the flowchart of FIG. 10.

Various intermediate forms of these two techniques can be thought of, for example to solve a situation with four computing devices of which two are "embedded" within the other two. Such situations will be described shortly in detail.

4 Application to credential mechanisms

A "credential" mechanism is a collection of cryptographic protocols enabling users to transfer certified information between organizations. A piece of certified information is called a "credential." One may think of various distinct types of credentials such as tax information, money, medical data, driver's license, legal right to vote, and so on. To prevent massive matching of databases (that is, to guarantee privacy of transfer of information between organizations), each user is know under a different pseudonym at different organizations. Possibly one even has multiple pseudonyms with one organization.

Signatures of organizations must hence be transferable between distinct pseudonyms of the same user, such that certified information received from one organization can be shown to another organization without this enabling linkage to the execution of the protocol in which the information was obtained. A description of such a mechanism in the prior art can be found in Chaum, D., Evertse, J. H., "A secure and privacy-protecting protocol for transmitting personal information between organizations," Proceedings of Crypto 86, Lecture Notes in Computer Science, Springer-Verlag 1986, pages 118-168. In this mechanism ordinary blind signatures are used to certify information. It is noted that this essentially is the only credential mechanism known in the previous art (a minor improvement has been proposed in the prior art).

Techniques based on restrictive blind signatures enable the construction of much more sophisticated, efficient and secure credential mechanisms. In the following description it will be assumed throughout without loss of generality that the restrictive blind signature protocol of FIG. 2 is used; that is, m can be blinded to ms.sup.v with a corresponding signature for a secret choice of s .epsilon..sub. *.sub.n. Clearly, the protocol of, for instance FIG. 3 could just as well be used instead; the choice is merely for clarity.

4.1 Validation of pseudonyms

In the credential mechanism known in the prior art a pseudonym of user i with an organization j is of the form m.sub.i s.sub.j.sup.v, with the user knowing m.sub.i and s.sub.j, both in *.sub.n. Since one at least has to be sure that different users use a different pseudonym of which they do not know the v-th root modulo n, pseudonyms first must be validated by a special certifying party called the "center" for convenience. The center is the only party knowing the factorization of the modulus n. This means that the center has to compute all signatures.

In the present description it will henceforth always implicitly assumed that the center will also certify information at the request of organizations; that is, it is implicitly understood that in case an organization computes a digital signature, this computation is actually performed by the center via for example an on-line connection. As will be clear to those of ordinary skill in the art, this is not an inherent requirement.

The credential mechanism known in the prior art uses the inefficient "cut-and-choose" technique to certify pseudonyms (validation). By using a restrictive blind signature protocol, the validation protocol can be realized much more efficiently and securely, while at the same time also resulting in a much more sophisticated system.

Turning to FIG. 6, a flowchart of a pseudonym validation protocol in the first preferred embodiment will now be described that enables user i to have a pseudonym validated for use with some organization j.

At the start of the protocol, the center chooses a number u.sub.i in *.sub.v that has not been used in a previous execution of the protocol. Alternatively, user i can determine this number, possibly in cooperation with the center. Box 61 indicates that the protocol of FIG. 2 is performed. In the second line of Box 22 of the flowchart of that protocol, i blinds the number Y.sup.u.sbsp.i, which will be denoted by m.sub.i, to the pseudonym m.sub.i s.sub.j.sup.v for a random number s.sub.j in *.sub.n. This pseudonym will be denoted henceforth by P.sub.ij. The number Y is a publicly known number, chosen beforehand by the center. Users are not supposed to know the v-th root modulo n of Y.

Box 62 indicates that, in order to use the pseudonym P.sub.ij at organization j, i sends this number together with the obtained signature of the center to organization j.

Box 63 indicates that the user then has to prove to the organization knowledge of a representation of P.sub.ij with respect to (Y; v), without revealing the representation. The flowchart of FIG. 5 shows how this can be done. Preferably the proof is done such that the organization can use the transcript of the execution of the proof to prove to for example the center that the proof took place (as explained in the description of FIG. 5).

As will be clear to those of ordinary skill in the art, one can also use restrictive blind signatures for which the mere fact that the user is able to show a signature by itself suffices to prove that the pseudonym is of the correct form. The proof of knowledge indicated in Box 63 can be omitted in that case. Such a signature can be constructed with the second technique from identitication protocols of the Fiat/Shamir type, as described before in detail.

Box 64 specifies that if organization j accepts the proof of knowledge of the user, then it accepts P.sub.ij for use as a pseudonym. Clearly, by repeating this protocol several times, i can obtain several pseudonyms for use with various organization.

In some situations, such as in systems for transferring one-show credentials between pseudonyms, as described at the end of this section (as will be appreciated, such systems are not known in the prior art), users should in addition be prevented from using the same pseudonym with various organizations; to this end, Box 63 should in addition specify the organization to contact the center, which can then test if the pseudonym is already in use with some other organization.

If user i would now simply "forget" all about u.sub.i, the system reduces to the credential mechanism known in the prior art. Namely, user i in that case has a pseudonym P.sub.ij =m.sub.i s.sub.j.sup.v with organization j for m.sub.i and s.sub.j that are known to him. However, the use of restrictive blind signatures in combination with a great many new techniques for proving relations between numbers of representations (described shortly) offers many advantages in working with u.sub.i. One such advantage is immediately obvious in that i can henceforth always prove to j that P.sub.ij is his pseudonym by proving knowledge of a representation with respect to (Y; v). Note also that in any case the validation protocol is much more efficient; the same also seems to hold for the security.

It is noted that at the start of the protocol of FIG. 6, user i could send the number m.sub.i =Y.sup.u.sbsp.i to the center, and could then prove using a cryptographic protocol such as the Guillou/Quisquater identification protocol (well-known in the art) that he knows a number u.sub.i such that m.sub.i =Y.sup.u.sbsp.i without revealing u.sub.i. As would be obvious to those of ordinary skill in the art, one could also use in such a situation a form like m.sub.i =Y.sub.0.sup.u.sbsp.0i Y.sub.1.sup.u.sbsp.1i. This has the advantage that it is impossible (regardless of computational power) for the center to compute (u.sub.0i,u.sub.1i) of i. In this way, framing is prevented.

4.2 Representing credentials as representations of a number with respect to suitably chosen vectors

In the new credential mechanism a certain type of credential that one owns is not characterised by the choice of v for the signature (i.e. what kind of RSA-root is computed, as is the case in the system known in the previous art) but by the representation the owner knows of the number m on which he has obtained a blind signature and with respect to what publicly known vector. Proving to an organization that one owns a certain credential is no longer a matter of just revealing a signature of the appropriate type on the pseudonym with that organization (as in the system known in the prior art); one also has to prove knowledge of a representation of the number (or of a mathematical function of several numbers, such as the product or quotient) on which one has obtained a signature, with respect to a vector of numbers composed of a publicly known vector of numbers (Y.sub.1, . . . , Y.sub.k ; v), where each Y.sub.i (and possibly also the choice of v) denotes a different type of credential. The specific vector with respect to which one can successfully perform the proof reflects what types of credentials one owns. In this way a user can, amongst others, "gather" many credentials in an efficient and flexible way in one number with a signature. In the next subsection this will be clarified in detail.

To illustrate this, consider a publicly known vector (Y.sub.1, . . . , Y.sub.6 ; v), of which Y.sub.i denotes credential type i. If a user can prove knowledge of a representation of, say, m/(Y.sub.2 Y.sub.6) with respect to (Y; v), and has a signature on m=Y.sup.u.sbsp.i Y.sub.2 Y.sub.6 s.sup.v, then this shows that he has credentials of types 2 and 6.

As will be described in detail in a later subsection, one can in addition make use of exponents on the Y.sub.i 's, such as for example Y.sup.u.sbsp.i Y.sub.3.sup.7 Y.sub.5.sup.2 Y.sub.6.sup.-5 s.sup.v, which gives greater functionality.

To prove knowledge of a representation of a number with respect to a certain vector either a "zero-knowledge proof" or a "signed proof" can be used, as explained previously. In the latter case the organization involved in the proof can convince others that the proof was performed, and often no interaction is needed for the proof itself.

In the special case that one should only be capable of showing his credentials to only one organization of ones own choice, such a proof is not even needed; it suffices to show the signature. At the end of this section this will be applied to construct a system for paying-under-pseudonym (that is, a system for allowing transference of one-show credentials between pseudonyms).

4.3 Transitivity of restrictive blind signatures; "updating" credentials

Each credential in the mechanism known in the prior art consists of one signature on a number. The storage requirements for signatures hence grows linearly in the number of credentials that one has. (Although it is known in the art to exchange sets of credentials for one new credential indicating ownership of all credentials in the set.)

Restrictive blind signatures enable an entirely different mechanism, where the credentials of a user are "stored" and "updated" in the representation he knows of one number (on which he knows a signature) with respect to a publicly known vector. Each time he receives a new credential, this representation is, as it were, updated (and a corresponding new signature is obtained). The previous signature may as well be destroyed in that case, since it is no longer needed.

This technique is made possible by the unique property of restrictive blind signatures that information can be blinded repeatedly, such that at least part of the representation known by the user cannot be modified by him throughout (that is, the information contained in m is inevitably conserved). This property will be called "transitivity."

In the simplest form this "transitivity" amounts to taking the output of a previous execution of the protocol as the new input to a next execution of the protocol. For example, m.sub.0 can be blinded to m.sub.0 s.sub.0.sup.v with a signature. Denoting this number by m.sub.1 can in a similar way be blinded to m.sub.1 s.sub.1.sup.v =m.sub.0 (s.sub.0 s.sub.1).sup.v with signature. Denoting this number by m.sub.2, and repeating this process i+1 times, one gets a number m.sub.i+1 which equals m.sub.0 (s.sub.0 . . . s.sub.i).sup.v. As will be clear to those of ordinary skill in the art, the following holds: considering the representation (r.sub.1, . . . , r.sub.k ;r.sub.k+1) the receiver of the signature on m.sub.i knows of m.sub.i with respect to a suitably chosen vector (Y.sub.1, . . . , Y.sub.k ; v), only r.sub.k+1 can be modified by him throughout all the iterations of the blinding process. The first k numbers will remain unchanged modulo v. Clearly, a similar thing holds when the protocol of the third flowchart, or the protocol closely related to the protocol of the third flowchart, is used; in that case the quotients r.sub.i /r.sub.j mod v will remain unmodified for i,j.ltoreq.k.

More generally the following holds for restrictive blind signatures. A function of the obtained output of a previous execution of the protocol can serve as the new input to a next execution of the protocol; if one receives in the ith execution of the restrictive blind signature protocol a signature on m.sub.i, then as input to a next execution of the protocol f(m.sub.i) can be used. The choice for f can vary per execution of the protocol (as well as the choice of v), and can be determined by the certifying party. This technique allows the certifying party to "install" new credentials in the part of the representation that is conserved under blinding.

Suppose that Y.sub.j represents credential type i. To update m.sub.i with a credential type j,f(m.sub.i)=m.sub.i Y.sub.j can be taken by the certifying party as input. The user then obtains a signature on m.sub.i+1 =m.sub.i Y.sub.j. The certifying party does not need to know the representation the user knows of m.sub.i for this. That is, updating can take place without the certifying party needing to know the credentials that the user already has.

It is noted that the user can very well use this technique in combination with the technique well-known in the art to use one type of signature for each credential. For instance, the user can store and update all the credentials pertaining to medical data in the representation he knows of a number m.sub.a for which he has a sign