Card-computer moderated systems

• US 4,926,480 A
• Filed: 05/24/1988
• Issued: 05/15/1990
• Est. Priority Date: 08/22/1983
• Status: Expired due to Term

• Current Assignee: Van Detsan Networks LLC (Intellectual Ventures LLC)
• Original Assignee: David Chaum
• Inventors: Chaum, David
• Primary Examiner(s): Buczinski, Stephen C.
• Assistant Examiner(s): Gregory, Bernarr Earl
• Application Number:
  US07/198,315
• Time in Patent Office: 721 Days
• Field of Search: 380/23-25, 380/30, 380/43, 380/44, 380/47, 380/49, 380/50, 235/379-382
• US Class Current: 705/69
• CPC Class Codes: G06K 7/00 Methods or arrangements for sensing record carriers, e.g. for reading patterns methods or arrangements for marking the record carrier in digital fashion G06K1/00; pattern recognition G06F18/00; arrangements for image or video recognition or understanding G06V10/00; character recognition, recognising digital ink or document-oriented image-based pattern recognition G06V30/00
• CPC Class Codes: G06Q 20/341 Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
• CPC Class Codes: G06Q 20/3678 e-cash details, e.g. blinded, divisible or detecting double spending
• CPC Class Codes: G06Q 20/383 Anonymous user system
• CPC Class Codes: G06Q 20/40975 using encryption therefor
• CPC Class Codes: G07F 7/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system
• CPC Class Codes: G07F 7/1016 Devices or methods for securing the PIN and other transaction-data, e.g. by encryption arrangements for secret communication, see H04L9/00
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3257 using blind signatures

Abstract

A user controlled card computer C and communicating tamper-resistant part T are disclosed that conduct secure transactions with an external system S. All communication between T and S is moderated by C, who is able to prevent T and S from leaking any message or pre-arranged signals to each other. Additionally, S can verify that T is in immediate physical proximity. Even though S receives public key digital signatures through C that are checkable using public keys whose corresponding private keys are known only to a unique T, S is unable to learn which transactions involve which T. It is also possible for S to allow strictly limited messages to be communicated securely between S and T.

Claims

1. Apparatus for conducting cryptographic transactions comprising:

first information processing means that is in the possession of an individual,

that is tamper-resistant, and that includes memory means inaccessible to the individual;

second information processing means that is under the control of said individual;

interface means between said first information processing means and said second information processing means for allowing information interchange therebetween;

key creation means for a first party to create a first private key and a corresponding first public key and to supply the first public key to a second party through said interface means;

neutralizing value creation means for said second party to create a neutralizing value at least unpredictable to said first party;

neutralizing means for said second party to determine a second public key responsive to said first public key and said neutralizing value such that for said first public key there exists at least one said neutralizing value that would determine each said second public key; and

secret key determining means for deriving a secret key, by said first party, necessary for making digital signatures verifiable with said second public key.

2. A cryptographic method wherein a first party communicates with a second party to create a neutralized public key and corresponding private key, comprising the steps of:

creating a first secret key unknown at least in part to said second party and a corresponding first public key, by a first party;

supplying to said second party, by said first party, a first message as a function of said first public key;

receiving and retaining said first message, by said second party;

developing a neutralizing value at least unpredictable to said first party, by the second party;

determining a second public key as a function of said first public key and said neutralizing value, by at least said second party, such that for said first public key there exists at least one said neutralizing value that would determine each said second public key; and

determining a second secret key, by said first party, necessary for making digital signatures verifiable with said second public key.

3. Apparatus for conducting cryptographic transactions comprising:

first information processing means that is in the possession of an individual, that is tamper-resistant, and that includes memory means inaccessible to the individual;

second information processing means comprising a system that is external to said first processing means and beyond the control of said individual;

third information processing means that is under the control of said individual;

first interface means between said first information processing means and said third information processing means for allowing information interchange therebetween;

second interface means between said second information processing means and said third information processing means for allowing information interchange therebetween;

public key digital signature forming means, at least partly within said first information processing means, for developing at least part of a digital signature, as a function of private key information within said information storage means, and for providing an at least partial digital signature to said third information processing means through said first interface means;

public key digital signature checking means for said third information processing means to check said at least partial digital signature received through said first interface means and to forward a digital signature, which the partial digital signature received is necessary to form, to said second information processing means through said second interface means; and

public key digital signature checking means for said second information processing means to check a digital signature that is received through said second interface means.

4. A cryptographic method wherein a first party communicates with a second party only via a third party and the first party having a first private key and the second party having a second private key and the public keys corresponding to the first and the second private keys being known to the three parties, the method comprising the steps of:

creating a blinding valve unpredictable to at least said first and second party, by said third party;

blinding an original message at least responsive to said blinding value to produce a blinded message such that a blinded message can result from any original message for at least one such blinding value;

signing said blinded message using said first private key to form a corresponding first public key digital signature, by said first party, and supplying this first signature to said third party;

verifying said first signature received, by said third party, using said first public key and supplying the first signature to said second party;

verifying said first signature received, by said second party;

signing said blinded message to form a signed blinded message, by said second party, by using said second private key to form a corresponding second public key digital signature and forwarding this second signature to said third party; and

unblinding said second signature received as a function of said blinding value to develop an unblinded signed message, such that said unblinded signed message and said signed blinded message are substantially unlinkable to each other because at least one particular said blinding value would imply that many different pairs of blinded and unblinded forms correspond.

5. The method of claim 4, further comprising the steps of forming said message to contain a public key by cooperation of said first and third parties, such that (a) cooperation of at least said first party is necessary to form digital signatures verifiable using said public key, and (b) said third party is able to influence the public key to take on many different values.

6. The method of claim 5, including the step of checking said message and said blinding, by said first party, before providing said first signature to said third party.

7. Apparatus for permitting cryptographic communication between first and second parties only if the distance from a first party to a second party is below an upper bound, said apparatus comprising:

selection means for forming a response value by said first party at least unpredictable to an adversary;

selection means for forming a challenge value by said second party at least unpredictable to an adversary;

challenge issuing means for said second party to issue said challenge to said first party;

response issuing means for said first party to issue said response to said second party upon receiving said challenge without substantial delay;

measuring means for said second party to determine the time elapsed between the issue of said challenge and the receipt of said corresponding response;

signing means for said first party to issue a public key digital signature depending on both said challenge and said response; and

signature checking means for said second party to check said public key digital signature.

8. A method for permitting cryptographic communication between first and second parties only if the distance from a first party to a second party is below an upper bound, said method, comprising the steps of:

forming a challenge, by a second party, in a way unpredictable to at least a third party;

forming a response, by a first party, in a way unpredictable to at least a third party;

issuing said challenge, by said second party;

issuing said response to said second party upon receiving said challenge without substantial delay, by said first party;

measuring the time elapsed between the issue of said challenge and the receipt of said corresponding response, by said second party;

issuing a public key digital signature responsive to both said challenge and said response, by said first party; and

checking said public key digital signature by said second party.

9. A method for permitting cryptographic communication between first and second parties only if the distance to a first party by a second party is below an upper bound, in which a third party is allowed to prevent outflow from the first party to the second party, said method comprising the steps of:

creating a pad, by said third party, in a way at least unpredictable to said first party and unknown to said second party;

committing to said pad, by said third party, to said first party;

forming a challenge, by said second party, in a way unpredictable to said third party;

forming a response, by said first party, in a way unpredictable to said third party;

issuing said challenge, by said second party, in a way that it is transferred to said third party;

receiving said challenge, by said first party, and issuing said response to said third party upon receiving said challenge without substantial delay;

padding said response received, by said third party, by combining said challenge with said pad to form a padded challenge, and providing said padded challenge to said second party;

measuring the elapsed time between said issue of said challenge and receipt of said padded response, by said second party;

opening said commitment to said pad, by said third party, to said first party;

issuing a public key digital signature as a function of both said challenge and said padded response, by said first party; and

checking said public key digital signature by said second party.

10. A method for permitting cryptographic communication between first and second parties only if the distance to a first party by a second party is below an upper bound, in which a third party is allowed to prevent inflow from the second party to the first party, said method comprising the steps of:

creating a pad, by said third party, in a way at least unknown to said first party and unpredictable to said second party;

committing to said pad, by said third party, to said second party;

forming a challenge, by said second party, in a way unpredictable to said third party;

forming a response, by said first party, in a way unpredictable to said third party;

issuing said challenge to said third party, by said second party;

receiving said challenge, by said third party, and padding said challenge by combining said challenge with said pad to form a padded challenge and forwarding said padded challenge to said first party;

receiving said padded challenge, by said first party, and issuing and transferring said response upon receiving said padded challenge without substantial delay to at least said second party;

measuring the elapsed time between said issue of said challenge and receipt of said response by said second party;

issuing a public key digital signature as a function of both said padded challenge and said response, by said first party;

opening said commitment to said pad, by said third party, to said second party; and

checking said public key digital signature by said second party.

11. A cryptographic method wherein a first party communicates with a second party only via a third party and the first party having a private key and the corresponding public key known to the three parties, the method comprising the steps of:

forming a public key digital signature on the message at least by said first party using said private key, and the signature becoming known to said third party;

creating an obscuring value, by said third party, at least unpredictable to said first and second party;

obscuring said digital signature, by said third party, as a function of said obscuring value, so that many different forms of a signature verifiable with said public key and said message could be created by at least one obscuring value;

verifying said digital signature on said message by said third party using said public key and forwarding said digital signature to said second party; and

verifying said digital signature received on said message, by said second party, using said public key.

12. A cryptographic method wherein a first party communicates with a second party only via a third party and the first party having a private key and the corresponding public key known to the three parties, the method comprising the steps of:

forming a signature on a message, by said first party, using said private key;

verifying said signature on said message, by said third party, using said public key by (a) forming a challenge from said signature, (b) providing said challenge to said first party, (c) receiving a corresponding response formed by said first party, and (d) checking said response;

providing said signature by said third party to said second party;

creating a challenge, by said second party, and providing the challenge to said third party;

disguising said challenge received by said third party and forwarding it to said first party;

forming a response, by said first party, to said disguised challenge received and forwarding the response to said third party;

un-disguising said response received, by said third party, and forwarding the resulting response to said second party; and

verifying, by said second party, said resulting response received.

13. Apparatus for conducting cryptographic transactions comprising:

first information processing means that is in the possession of an individual, that is tamper-resistant, and that includes memory means inaccessible to the individual;

second information processing means comprising a system that is external to said first processing means and beyond the control of said individual;

third information processing means that is under the control of said individual;

first interface means between said first information processing means and said third information processing means for allowing information interchange therebetween;

second interface means between said second information processing means and said third information processing means for allowing information interchange therebetween;

public key digital signature forming means, within said second information processing means, for forming a digital signature on a blinded digital message, as a function of a private key accessible to said second information processing means, and for forwarding said signature to said third information processing means;

public key digital signature checking means for said third information processing means to check said digital signature received through said second interface means as a function of a public key corresponding to said private key of said second party and for forwarding the digital signature to said first information processing means through said first interface means; and

public key digital signature unblinding means for said first information processing means to unblind said digital signature received through said second interface means and said blinding, said unblinding and signing cooperating so that a digital signature by said second information processing means is inaccessible to said third information processing means and is obtained by said first information processing means.

14. A cryptographic method wherein a first party communicates with a second party only via a third party and the first party having a first private key and the second party having a second private key and the public keys corresponding to the first and the second private keys being known to the three parties, the method comprising the steps of:

creating a first blinding value, by said first party, unknown at least in part to said third party;

creating a second blinding value, by said third party, at least unpredictable to said third party;

blinding a message by both said first party and said third party as a function of said first and second blinding values to produce a doubly-blinded message;

signing said doubly-blinded message, by said first party, using said first private key to form a first signature and forwarding said first signature to said third party;

checking said first signature received, by said third party, using said first public key and forwarding said first signature to said second party;

checking said first signature received, by said second party, using said first public key;

signing said doubly-blinded message, by said second party, using said second private key, to create a second signature and returning the second signature to said third party;

checking said second signature received, by said third party; and

unblinding said second signature by cooperation of said first and third party.

15. A cryptographic method wherein a first party communicates with a second party only via a third party and a public key is known to the three parties and the first party having a digital signature verifiable with the public key, the method comprising the steps of:

creating a protector value having a signature unknown to said third party, by said first party, and providing the protector to said third party;

sanitizing the protector received, by said third party, using a sanitizing value at least unpredictable to said first and second parties, so that many different sanitized protectors can result from any particular unsanitized protector, and providing the sanitized protector to the first party;

creating a challenge at least unpredictable to said first and second party, by interchange between said first and third party, and supplying the challenge to said first party;

forming a response to said sanitized challenge received, by said first and third parties, including checking the response by the third party and forwarding the response to the second party; and

checking the response received, by the second party.

16. The method of claim 15, including the step of sanitizing the challenge in a way that is unpredictable to both said first and said third parties.

17. A cryptographic method wherein a first party communicates with a second party only via a third party and the first party having a first private key and the second party having a second private key and the public keys corresponding to the first and the second private keys being known to the three parties, the method comprising the steps of:

encoding a message at least unknown to said third party and belonging to a strictly limited set of possible values, by said first party, using said second public key;

hiding said encoded message with a value at least unpredictable to said first party, so that said message is not changed but many different hidden encoded messages containing the same message can result and providing the hidden encoded message to said first party;

signing said hidden encoded message received, by said first party, using said first private key and providing the resulting signature to said third party;

checking said signature received, by said third party, and forwarding the signature to said second party; and

checking said signature received by said second party and decoding the message contained in said hidden form of said message by using said second private key, with the result that said message encoded by said first party is obtained by said second party.

18. A cryptographic method wherein a first party communicates with a second party only via a third party and the first party having a first private key and the second party having a second private key and the public keys corresponding to the first and the second private keys being known to the three parties, the method comprising the steps of:

encoding a first element of a group in a first message, by said first party, using said second public key and forwarding the encoded first message to said third party, such that the first group element is at least unknown to said third party;

modifying said encoded first message received, by said third party, using a value at least unpredictable to said first party, so that many different modified encoded messages can result, in such a way that a second group element becomes known to the third party that when combined by a group operation with said first group element yields the group element encoded in said modified encoded message, and the third party forwarding said modified encoded message to said first party;

signing said modified message received, by said first party, using said first private key and providing the resulting first signature to said third party;

checking the first signature received, by said third party, using said first public key and forwarding the first signature to said second party;

checking said first signature received, by said second party, using said first public key and decoding the modified message contained in the signature using said second private key, with the result that said third group element is obtained by said second party;

forming a second digital signature and providing it to said third party, by said second party, the second signature encoding a fourth group element that when combined with said third group element using said group operation yields a fifth group element standing for a message the second party provides to the first party;

checking said second public key digital signature received, by said third party, and forwarding the second signature to said first party; and

checking said second public key digital signature received, by said first party, and recovering said fifth group element as the result of applying said group operation to said first and second group elements and to said fourth group element.