Multi-purpose transaction card system

• US 20030097344A1
• Filed: 08/12/2002
• Published: 05/22/2003
• Est. Priority Date: 01/11/1994
• Status: Active Grant

• Current Assignee: Van Detsan Networks LLC (Intellectual Ventures LLC)
• Original Assignee: InfoSpace, Inc. (Blucora Incorporated)
• Inventors: Chaum, David, Ferguson, Niels, Van Der Hoek, Jelte
• Granted Patent: US 6,718,314 B2
• Time in Patent Office: Days
• US Class Current: 705/75
• 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/367 involving electronic purses or money safes
• CPC Class Codes: G06Q 20/3674 involving authentication
• CPC Class Codes: G06Q 20/382 insuring higher security of transaction
• CPC Class Codes: G06Q 20/401 Transaction verification
• 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: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/3257 using blind signatures
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

Disclosed is a multi-purpose transaction card system comprising an issuer, one or more cards, one or more terminals, and optionally one or more acquires, communicating using a variety of cryptographic confidentiality and authentication methods. Cards authenticate messages using public key based cryptographic without themselves performing the extensive computations usually associated with such cryptography. Integrity of complex transaction sequences and plural card storage updates are maintained even under intentionally generated interruptions and/or modifications of data transmitted between card and terminal. Cards do not reveal any information to the terminal which is not directly necessary for the transaction or any information to which the terminal should not have access, though externally measurable aspects of its behavior. Transaction types supported include those suitable for off-line credit cards, in which the “open to buy” is maintained on the card.

Claims

1. A method for public-key digital authentication of messages, comprising the steps of:

creating a private key by a signing party;

making a public key, corresponding to said private key of said signing party, verifiable by at least a receiving party;

creating a set of one-time signatures;

forming a compression hierarchy of said one-time signatures;

forming a public key digital signature, verifiable with said public key, on said compression hierarchy;

storing edges of said compression hierarchy by an endorser;

endorsing by signing with at least one of said one-time, signatures and providing stored edge values;

verification of said one-time signature and said edge values supplied and said digital signature on said compression values; and

accomplishing the foregoing by said endorser storing substantially less than all edges and computing before each endorsement substantially less than all edges.

2. In the method of claim 1, using a cascade structuring of compression functions.

3. In the method of claim 1, preparing for future endorsements so that they will require substantially less computation.

4. In the method of claim 1, said one-time signature being constructed using different oneway functions in a chain of oneway functions.

5. In the method of claim 3, said preparations being done at least in part by a party different from the endorser.

6. Apparatus for public-key digital authentication of messages, comprising:

means for creating a private key by a signing party;

means for making a public key, corresponding to said private key of said signing party, verifiable by at least a receiving party;

means for creating a set of one-time signatures;

means for forming a compression hierarchy of said one-time signatures;

means for forming a public key digital signatures, verifiable with said public key, on said compression hierarchy;

means for storing edges of said compression hierarchy by an endorser;

means for endorsing, comprising means for signing with one of said one-time signatures and means for providing stored edge values;

means for verification of a one-time signature and compression hierarchy values supplied and for verification of said digital signature on said compression value and

means for accomplishing the foregoing by said endorser storing substantially less than all edges and computing before each endorsement substantially less than all edges.

7. In the apparatus of claim 6, means for forming a cascade structuring of compression functions.

8. In the apparatus of claim 6, means for preparing future endorsements so that they will require substantially less computation.

9. A method for financial transactions, comprising the steps of:

maintaining a challenge seed by a terminal for use with respect to at least one subsequent transaction;

issuing a challenge seed modifier by an on-line server to said terminal;

modifying said challenge seed by said terminal at least responsive to said modifier;

developing a challenge value for use in a subsequent transaction, where said challenge value depends oat least substantially on said challenge seed; and

accomplishing the foregoing so as to make said challenge unpredictable even to someone privy to the secrets of said terminal.

10. Apparatus for financial transactions, comprising:

means for maintaining a challenge seed by a terminal for use with respect to at least one subsequent transaction;

means for issuing a challenge seed modifier by an on-line server to said terminal;

means for modifying said challenge seed by said terminal at least responsive to said modifier;

means for developing a challenge value for use in a subsequent transaction, where said challenge value depends oat least substantially on said challenge seed; and

means for accomplishing the foregoing so as to make said challenge unpredictable even to someone privy to the secrets of said terminal.

11. A method for public key digital authentication of a message, comprising the steps of:

creating a private key for a signing party;

making a public key, corresponding to said private key, verifiable by at least a receiving party;

generating the commit value of a commit-challenge-response protocol by said signing party;

sending said commit value to said receiving party;

forming a mutually random value by said signing party and said receivable party;

choosing the challenge value of said commit-challenge-response protocol as the hash value of the concatenation of the message to be authenticated and said mutually random value;

generating the response value of said commit-challenge-response protocol by said signing party;

sending said response value to said receiving party; and

verifying said response value by said receiving party.

12. In the method of claim 11, said commit-challenge-response protocol consisting of a compact endorsement signature protocol.

13. Apparatus for public key digital authentication of a message, comprising:

means for creating a private key for a signing party;

means for making a public key, corresponding to said private key, verifiable by at least a receiving party;

means for generating the commit value of a commit-challenge-response protocol by said signing party;

means for sending said commit value to said receiving party;

means for forming a mutually random value by said signing party and said receiving party;

means for choosing a mutually random value by said commit-challenge-response protocol as the hash value of the concatenation of the message to be authenticated and said mutually random value;

means for generating the response value of said commit-challenge-response protocol by said signing party;

means for sending said response value to said receiving party; and

means for verifying said response by said receiving party.

14. A method for storing data in non-volatile memory, comprising the steps of:

initializing a commit value to a logical zero;

storing one or more descriptions of modifications to be made;

setting said commit value to a logical one;

performing the modifications specified by said descriptions setting said commit value to a logical zero; and

detecting interruptions in the above mentioned steps, and upon detection performing the steps of;

a) inspecting said commit value;

b) performing said modifications if said commit value is a logical one;

c) setting said commit value to a logical zero

15. In the method of claim 14, with means for setting said commit value to a logical one value after an interruption and before said modifications are made.

16. In the method of claim 14, with improvements comprising the steps of:

initializing an in-use value to a logical zero;

setting said in-use value to a logical one before said commit value is set to a logical one;

setting said in-use value to a logical one before said commit value is set to a logical zero; and

setting said commit value to a logical zero and then setting said in-use value to a logical zero if the in-use value is found to contain a logical one while the commit value is found to contain a logical zero after an interruption.

17. In the method of claim 14 or 16, with different commit values used for different modifications.

18. In the method of claim 14 or 16, each of said modifications consisting of a standard action on one of a given set of memory locations.

19. In the method of claim 18, said standard action consisting of setting the location to fixed value.

20. In the method of claim 18, said retention means for modification descriptions consisting of a single bit for each of the possible locations for the modification.

21. In the method of claim 14 or 16, with improvements comprising the steps of:

storing one or more reversion descriptions to be made; and

performing the reversions specified by said reversion descriptions if the commit value is found to contain a logical zero after an interruption.

22. In the method of claim 21, each of said reversions consisting of a standard action on one of a given set of memory locations.

23. In the method of claim 22, said standard action consisting of setting the location to a fixed value.

24. In the method of claim 22, said retention means for reversion descriptions consisting of a single bit for each of the possible locations for the reversion.

25. Apparatus for storing data in non-volatile memory, comprising:

retention means for a single bit commit value;

retention means for one or more modification descriptions to be made;

initialization means to ensure that said commit value is a logical zero during a prefix of the card life;

means for storing one or more modification descriptions to be made in said second retention means;

means for setting said commit value to a logical one;

means for performing the modifications specified by said descriptions;

means for setting said commit value to a logical zero; and

means for detecting an interruption of normal processing and triggering;

a) means for inspecting said commit value;

b) means for performing said modifications if said commit value is a logical one; and

d) means for setting said commit value to a logical zero.

26. A method for handling memory errors in a computing device with non-volatile memory, comprising the steps of:

initializing a mode value to indicate a first mode;

detecting the occurrence of an errornous state of said memory;

setting said mode value to indicate a second mode upon detection of said errornous state;

inspecting said mode value in at least one of the processes executed by said computing device; and

modifying the behaviour of said process depending on the value of said mode value.

27. In the method of claim 26, said modifying of the behaviour of said process including restriction of normal execution of said process to the first state.

28. In the method of claim 26, said modifying of the behaviour of said process including including enabling a process in the second mode that allows recovery of application data.

29. In the method of claim 28, said process restricting access to data that is nonsecret.

30. In the method of claim 29, the secretness of the data being determined by a coding which increases the secretness level if individual bits in said memory are changed from a logical “

one”

state to a logical “

zero”

state.

31. In the method of claim 26, said detection of erroneous states using a coding of data to detect memory errors with substantially high probability.

32. Apparaturs for handling memory errors in a computing device with non-volatile memory, comprising of:

means for initializing a mode value to indicate a first mode;

means for detecting the occurrence of an errornous state of said memory;

means for setting said mode value to indicate a second mode upon detection of said errornous state;

means for inspecting said mode value in at least one of the processes executed by said computing device; and

means for modifying the behaviour of said process depending on the value of said mode value.

33. A method for communicating and linking a plurality of indepent action between a terminal and a card, with improvements comprising the steps of:

initializing a first hash state in said card to a known value before the start of the communication;

initializing a second hash state in said terminal to a known value before the start of the communication;

updating said first hash state using a function which takes said first hash state and substantially the data associated with an independent action as input and yields the new value for said first hash state as output;

updating said second hash state using a function which takes said second hash state and substantially the data associated with an independent action as input and yields the new value for said second hash state as output; and

making at least some of the data communicated between said terminal and said card dependent on said hash states.

34. In the method of claim 33, an initial independent action updating said hash states using at least one secret key.

35. In the method of claim 34, an initial independent action including a proof by said terminal of possession of said key.

36. In the method of claim 33, 34 or 35, said independent actions including cryptographic confidentiality coding of data communicated between said card and said terminal based on said hash states.

37. In the method of claim 36, said confidentiality coding using the same coding function in said card for both directions of data communication.

38. In the method of claim 36, said confidentiality coding using the same coding function in said terminal for both directions of data communication.

39. In the method of claim 33, 34 or 35, said independent actions only making tentative changes to the state of said card until a final independent action which makes the tentative changes permanent.

40. In the method of claim 39, discarding said tentative changes upon detection of an interruption.

41. In the method of claim 39, said final action including a first cryptographic authentication by said terminal to said card on said second hash state to start the process of making said tentative changes permanent.

42. In the method of claim 39, said final independent action including a second cryptographic authentication by said card to said terminal on said first hash state to show that said tentative changes have become permanent.

43. In the method of claim 42, a resend process being executed on request of the terminal after said final independent action in which said card resends said second cryptographic authentication to said terminal.

44. In the method of claim 43, with improvements comprising the steps of:

initializing a done value in said card to a logical zero state during said final independent action;

inspecting said done value during said resend process;

resending said second cryptographic authentication only if said done value is a logical zero;

sending a request by said terminal to said card to set said done value to a logical one; and

setting said done value to a logical one upon reception of said request.

45. In the method of claim 41, said last independent action) including provisions for said card to wait for a signal of said terminal after having verified said first cryptographic authentication but just before said tentative changes become permanent.

46. In the method of claim 41, the data for said independent actions having been generated by an issuer and sent to said terminal, and where said terminal executes said actions with said card based on the data supplied by said issuer.

47. Apparatus for communicating and linking a plurality of indepent actions between a terminal and a card, with improvements comprising of:

retention means for a first hash state in said card;

retention means for a second hash state in said terminal;

means for initializing said first hash state in said card to a known value before the start of the communication;

means for initializing said second hash state in said terminal to a known value before the start of the communication;

means for updating said first hash state using a function which takes said first hash state and substantially the data associated with an independent action as input and yields the new value for said first hash state as output;

means for updating said second hash state using a function which takes said second hash state and substantially the data associated with an independent action as input and yields the new value for said second hash state as output; and

means for making at least some of the data communicated between said terminal and said card dependent on said hash states.

48. A method for performing computations by a card which is communicating with a terminal comprising the steps of:

sending a first message by said terminal;

receiving said first message by said card;

performing computations by said card on the data received in said first message and data stored in the memory of said card;

sending a second message by said card;

receiving said second message by said terminal; and

inducing a delay between said first message and said second message, where the duration of said delay is determined solely by public information consisting of the contents of the messages received by said card before said delay, the contents of the messages sent by said card before said delay, and by data that said card would send to said terminal in subsequent communications given appropriate requests by said terminal

49. In the method of claim 48, said delay being made constant by adding sufficient delays in each of the possible execution paths of said computations.

50. In the method of claim 48, said computations being implemented by a sequence of actions each of which induces a known fixed delay where said sequence is solely determined by said public information.

51. In the method of claim 50, said sequence of actions consisting of actions that are functionally equivalent to a set of actions that contains one or more actions that are executed conditionally.

52. In the method of claim 50, said sequence of instructions implementing a conditional storage operation by executing a storage operation using an address whose value is computed as a function of the condition of said conditional storage operation.

53. Apparatus for performing computations by a card which is communicating with a terminal comprising of:

means for sending a first message by said terminal;

means for receiving said first message by said card;

means for performing computations by said card on the data received in said first message and data stored in the memory of said card;

means for sending a second message by said card;

means for receiving said second message by said terminal; and

means for inducing a delay between said first message and said second message, where the duration of said delay is determined solely by public information consisting of the contents of the messages received by said card before said delay, the contents of the messages sent by said card before said delay, and by data that said card would send to said terminal in subsequent communications given appropriate requests by said terminal.

54. A method for converting a set of instructions, comprising steps of:

inspecting said set of instructions;

determining the conditions used in said set;

adding instructions to said set which convert said conditions to values; and

rewriting expressions contained in said set to an equivalent formulation using said values instead of conditional execution of instructions.

55. Apparatus for converting a set of instructions, comprising of:

retention means for storing a set of instructions;

means for inspecting said set of instructions;

means for determining the conditions used in said set; and

means for adding instructions to said set which convert said conditions to values;

means for rewriting expressions contained in said set to an equivalent formulation using said values instead of conditional execution of instructions.

56. A method for collecting transaction information related to one or more transactions from a terminal by an acquirer, comprising steps of:

computing by said terminal a first value from said transaction information, whose size is substantially smaller than the size of said transaction information;

sending by said terminal to said acquirer a first message including an indication of the number of transactions, the applicable totals of the transactions, and said first value;

receiving said first message by said acquirer;

storing substantially the data from said first message by said acquirer for future computations;

making a random selection from the set of transaction, and

sending said random selection in a second message to said terminal;

receiving said second message by said terminal,

sending by said terminal to said acquirer in a third message substantially the transaction information for the transactions in said selection.

57. In the method of claim 56, said first message including skeleton transaction information about all transactions.

58. In the method of claim 56, said first message including a cryptographic hash value on substantially the full the transaction data of all transactions, and said third message including data that allows said hash value to be verified by said acquirer.

59. In the method of claim 58, said cryptographic hash value being computed using a tree structure.

60. Apparatus for collecting transaction information related to one or more transactions from a terminal by an acquirer, comprising:

means for computing by said terminal a first value from said transaction information, whose size is substantially smaller than the size of said transaction information;

means for sending by said terminal to said acquirer a first message including an indication of the number of transactions, the applicable totals of the transactions, and said first value;

means for receiving said first message by said acquirer;

retention means for storing substantially the data from said first message by said acquirer for future comparisons;

means for making a random selection from the set of transaction;

means for sending said random selection in a second message to said terminal;

means for receiving said second message by said terminal; and

means for sending by said terminal to said acquirer in a third message substantially the transaction information for the transactions in said selection.

61. A method for conducting financial transactions using a card, a terminal, and an issuer substantially according to the EMV specifications, with improvements comprising the steps of:

generating variable transaction data which is typically different for different transactions;

constructing a message block whose value depends on at least some of said variable transaction data;

generating by said card of an authentication based on public key cryptography on said message block;

sending said authentication in a message to said terminal;

receiving said message by said terminal; and

verifying said authentication by said terminal.

62. In the method of claim 61, said message block including the transaction certificate TC.

63. Apparatus for conducting financial transactions comprising a card, a terminal, and an issuer substantially according to the EMV specifications, with improvements characterized by:

means for generating variable transactoin data which is typically different for different transactions;

means for constructing a message block whose value depends on at least some of said variable transaction data;

means for generating by said card of an authentication based on public key cryptography on said message block;

means for sending said authentication in a message to said terminal;

means for receiving said message by said terminal; and

means for verifying said authentication by said terminal.

64. A method for conducting financial transactions using a card, a terminal, and an issuer substantially according to the EMV specifications, with improvements comprising the steps of:

maintaining a balance value in said card for all financial transaction applications;

decreasing said balance value by the amount of each transaction; and

refusing an off-line transaction if the amount of said transaction exceeds said balance value.

65. In the method of claim 64, said issuer using the script feature of the EMV to modify said balance value stored on said card.

66. In the method of claim 65, with improvements comprising the steps of:

storing information by said issuer related to said card;

storing information by said issuer related to on-line transactions performed by said card;

detecting by said issuer of failures to execute a first script issued by said issuer during an on-line transaction;

creating a second script including substantially the actions of said first script.

sending said second script to said terminal; and

executing said script by said terminal with said card

67. In the method of claim 66, with improvements comprising the steps of:

detecting by said issuer after a period of time off-line transactions performed by said card but not presented to said issuer for clearing;

estimating the total amount of said off-line transactions; and

adding substantially said total amount to said balance value using a script.

68. Apparatus for conducting financial transactions comprising a card, a terminal, and an issuer substantially according to the EMV specifications, with improvements characterized by:

retention means for a balance value in said card;

means for decreasing said balance value by the amount of each transaction; and

menas for refusing an off-line transaction if the amount of said transaction exceeds said balance value.

69. A method for conducting financial transactions using a card, a terminal, and an issuer substantially according to the EMV specifications, with improvements comprising the step of:

incrementing the transaction counter ATC only for those transactions which are completed successfully.

70. Apparatus for conducting financial transactions comprising a card, a terminal, and an issuer substantially according to the EMV specifications, with improvements characterized by:

means for incrementing the transaction counter ATC only for those transactions which are completed successfully.

71. A method for conducting financial transactions using a card, a terminal, and an issuer substantially according to the EMV specifications, with improvements comprising the steps of:

making a decision by said card whether to allow an off-line transaction or require an on-line transaction in a fixed amount of time; and

storing said decision in a fixed amount of time.

72. Apparatus for conducting financial transactions using a card, a terminal, and an issuer substantially according to the EMV specifications, with improvements comprising the steps of:

means for making a decision by said card whether to allow an off-line transaction or require an on-line transaction in a fixed amount of time; and

means for storing said decision in a fixed amount of time.