20 May 1998: Image and tables added

19 May 1998
Source: http://www.patents.ibm.com/details?patent_number=5712913
Thanks to Anonymous

View Images (17 pages)   |   Order Patent   |   Vote  [All links to IBM patent-server site]

5712913 : Limited-traceability systems

ABSTRACT:   Cryptographic methods and apparatus for payment and related transaction systems are disclosed that allow some kinds of tracing under some conditions and make substantially infeasible other kinds of tracing under other conditions. Examples include: allowing tracing if and only if agreed sets of trustees cooperate; tracing from a payment to the payer by cooperation of a set of trustees; tracing from a payment to the payer without revealing to trustees which payer is being traced or which payment; identifying all payments by a payer provided appropriate trustees cooperate; and identifying all payments by a payer under investigation without trustees learning which payer and/or which payments; Other examples include: limiting resolution to groups of payers in tracing for statistical purposes; allowing limited different markings of payment instruments while preventing payers from learning which marking they receive; providing for recovery of lost money without compromise of unrelated transactions; allowing participants the ability to retain, not forward, and even destroy some tracing information without financial harm; providing the option of artificial increase in the computational cost of at least some tracing; and providing the option of blurry linking of payments to payers.

U.S. REFERENCES:   (No patents reference this one)

Patent	Inventor	Issued	Title
4438824	Mueller-Schloer	3 /1984	Apparatus and method for cryptographic identity verification
4458109	Mueller-Schloer	7 /1984	Method and apparatus providing registered mail features in an electronic communication system
4759063	Chaum	7 /1988	Blind signature systems
4759064	Chaum	7 /1988	Blind unanticipated signature systems
4868877	Fischer	9 /1989	Public key/signature cryptosystem with enhanced digital signature certification
4879747	Leighton et al.	11 /1989	Method and system for personal identification
4947430	Chaum	8 /1990	Undeniable signature systems
4949380	Chaum	8 /1990	Returned-value blind signature systems
4987593	Chaum	1 /1991	One-show blind signature systems
5131039	Chaum	7 /1992	Optionally moderated transaction systems
5224162	Okamoto et al.	6 /1993	Electronic cash system
5276736	Chaum	1 /1994	Optionally moderated transaction systems
5276737	Micali	1 /1994	Fair cryptosystems and methods of use
5315658	Micali	5 /1994	Fair cryptosystems and methods of use
5373558	Chaum	12 /1994	Desinated-confirmer signature systems
5553145	Micali	9 /1996	Simultaneous electronic transactions with visible trusted parties

EXEMPLARY CLAIM(s): Show all 51 claims

What is claimed is:
    1. In a machine-implemented payment system method, the improvement comprising the steps of:

• forming with an automated machine, signals representing tracing signals depending on tracing key data substantially concealed by at least one trustee party apparatus; and
• convincing at least one party, while keeping the tracing key data secret from that party, that the tracing key data allows linking of payment data with data representing payer accounts;
• such that without the tracing key data of the at least one trustee party apparatus it is infeasible to link payment transaction data with data representing payer accounts and that with the cooperation of the at least one trustee party apparatus using the tracing key data, at least under predetermined conditions, at least a predetermined linking is feasible.

RELATED U.S. APPLICATIONS: none
FOREIGN APPLICATION PRIORITY DATA: none
FOREIGN REFERENCES: none

OTHER REFERENCES:

• Chaum et al, "Demonstrating Possession of a Discrete Logarithm Without Revealing It", Centre for Mathematics and Computer Science, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands, CRYPTO '86, Springer-Verlag, 1987, pp. 200-212.

[Figures 1 and 2 series inserted below in text; transcription below of pages 7 and partial 8]

LIMITED TRACEABILITY SYSTEMS

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to transaction systems, and more specifically to cryptographic prtocols and other techniques for ensuring security and privacy.

2. Description of Prior Art

Reference is hereby made to the following U.S. patents by the present applicant that are included herein by reference: U.S. Pat. No. 4,759,063 "Blind signature systems"; U.S. Pat. No. 4,759,064 "Unanticipated blind signature systems"; U.S. Pat. No. 4,947,430 "Card computer moderated systems"; U.S. Pat. No. 4,949,380 "Returned-value blind signature systems"; U.S. Pat. No. 4.987,593 "One-show blind signature systems"; and U.S. Pat. No. 5,131,039 "Optionally moderated transaction systems."

Payment systems today structurally provide either substantially unlimited traceability of payments or substantial untraceability. Bank notes and checks are paper-based examples of each extreme. Most digital systems proposed to date are similarly polarized into substantially traceable and substantially untraceable.

A variety of perceived requirements are believed to suggest a need for systems that have some provisions for traceability. Examples include: blacklisting known abusers of a system; investigations related to violation of law; marking of bearer instruments given to suspected criminals; statistical analysis of aggregated consumer behavior; recovery of money in case of unanticipated loss of information; and maintenance and provision by participants in payments of comprehensive records.

On the other hand, a variety of perceived requirements are believed to suggest a need for some corresponding limitations of traceability. Examples include: preventing use of blacklisting mechanism for unauthorized blacklisting or tracing; controlling how many investigations are made and maintaining confidentiality of who is being investigated; preventing of marking of money withdrawn from occurring more than to a limited extent; ensuring that statistical studies cannot determine individually identifiable data; preventing use of a recovery mechanism by parties other than the party whose data is being recovered; and allowing recipients and intermediaries in payments some control over clandestine or otherwise improper use of tracing information.

OBJECTS OF THE INVENTION

Accordingly, objects of the present invention include:

allowing tracing under one or more conditions and preventing it under other conditions;

allowing tracing if and only if agreed sets of trustees cooperate;

tracing from a payment to the payer by cooperation of a set of trustees;

tracing from a payment to the payer without revealing to trustees which payer is being traced or which payment;

identifying all payments by a payer provided appropriate trustees cooperate;

identifying all payments by a payer under investigation without trustees learning which payer and/or which payments;

limiting resolution to groups of payers in tracing for statistical purposes;

allowing limited different markings of payment instruments while preventing payers from learning which marking they receive;

providing for recovery of lost money without compromise of unrelated transactions;

allowing participants the ability to retain, not forward, and even destroy some tracing information without financial harm;

providing the option of artificial increase in the computational cost of at least some tracing;

providing the option of blurry linking of payments to payer; and

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

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

BRIEF DESCRIPTION OF THE DRAWING FIGURES

FIG.1 shows a combination general block, functional and flow diagram of a preferred embodiment of overall structure means and working methods of a payment system in accordance with the teachings of the present invention.

FIG. 2a shows a flowchart of a preferred embodiment of an overall process from tracing key creation to payment transaction in accordance with the teachings of the present invention. [Tables here substitute for images on pages 2 and 3]

Fig. 2a

FIG. 2b shows a flowchart of a preferred embodiment of exemplary means and methods whereby payment data flows from the payer through a network of operatives and may ultimately reach the issuer, all in accordance with the teachings of the present invention.

Fig. 2b

FIG. 2c shows a flowchart of a preferred exemplary means and methods whereby tracing is conducted and optionally trustees are kept from knowing from where and/or to where they are tracing, in accordance with the teachings of the present invention.

Fig. 2c

FIG. 2d shows a flowchart of a preferred exemplary means and methods whereby trustees allow tracing from an account identifier to actual payment transactions, in accordance with the teachings of the present invention.

Fig. 2d

FIG. 2e shows a flowchart of a preferred exemplary means and methods whereby a payer can obtain an identity from a group of identities that can be traced by a trustee, in accordance with the teachings of the present invention.

Fig. 2e

FIG. 2f shows a flowchart of a preferred exemplary means and methods whereby computational difficulty of tracing can be increased and tracing can be conducted accordingly, in accordance with the teachings of the present invention.

Fig. 2f

FIG. 2g shows a flowchart of a preferred exemplary means and methods whereby a secret seed is used to develop the parameters needed to protect unlinkability and can later be used to allow tracing of those values, in accordance with the teachings of the present invention.

Fig. 2g

FIG. 3 shows a flowchart of a preferred embodiment of a cut-and-choose protocol performed between parties denoted Bank B and Payer P in accordance with the teachings of the present invention.

[Complex equations of Figures 3 and 4 series not provided]

FIG. 4a shows a flowchart of a first preferred exemplary embodiment of both a form of money and a blinded, two-trustee protocol for tracing without the trustees learning either what was traced or who it was traced to, in accordance with the teachings of the present invention.

FIG. 4b shows a flowchart of a first preferred exemplary embodiment of an alternate form of money and a single trustee, as well as an unblinded form of a tracing protocol, all in accordance with the teachings of the present invention.

FIG. 4c shows a flowchart of a first preferred exemplary embodiment of a system for convincing a payer P that a particular set of linking information is merely a permuted copy a list developed by the trustee(s), thereby allowing a payer substantial certainty that they are linkable to an entry on the list, but substantially inability to determine which entry on the original list they are linked to, all in accordance with the teachings of the present invention.

FIG. 4d shows a flowchart of a first preferred exemplary embodiment of a system for allowing blacklisting information to be developed with knowledge of the payer account, in accordance with the teachings of the present invention.

FIG. 4e shows a flowchart of a first preferred exemplary embodiment of a system for restricting the blinding factor and also another use of the truncation function just described, both in accordance with the teachings of the present invention.

FIG. 4f shows a flowchart of a first preferred exemplary embodiment of another example of the choice of a blinding factor from a limited range corresponding to certain limited values, in accordance with the teachings of the present invention.

BRIEF SUMMARY OF THE INVENTION

In accordance with the forgoing and other objects of the present invention, a brief summary of some exemplary embodiments will now be presented. Some simplification and omissions may be made in this summary, which is intended to highlight and introduce some aspects of the present invention, but not limit its scope in any way. Detailed descriptions of preferred exemplary embodiments adequate to allow those of ordinary skill in the art to make and use the inventive concepts are presented later.

The essential way of providing the limited tracing is to put tracing information into the money numbers that will be spent or to ensure that is in the blinding parameters used in withdrawing them.

There are various ways of ensuring that the tracing information is in place. Examples include: the payer's tamper-resistant device can form it or certify that it is in place; a trustee can put it in place; the issuer can put it in place; a protocol between the issuer workstation and the payer can ensure the issuer that it is in place without revealing the tracing information to the issuer; or a protocol involving a tamper-resistant device communicating only with the workstation can convince the issuer that the information is in place.

There are various types of tracing information. Examples include: information that can be used to identify the payer if each trustee does some computation on it; information that allows an acceptor to do a computational test base on a cryptographic witness for a payment that is not be honored or that is to cause alarm if recognized; information that can be reconstructed by the trustees so that they can publish in effect a blacklist of all payments by a payer; information that lets the payments of a particular payer be recognized based on withdrawal and payment data; information that links a payer to a group of payers, without the payer needing to know which member of the group the linking is to; and seed information that the payer can recover in case other payment information is lost by the payer.

If payments are to be traced, then some trustees are preferably required, giving a separation between the role of allowing tracing on the one side and, on the other side, of issuing and guaranteeing the funds. There may be various sets of trustees corresponding to different kinds of tracing information and different payers. There may also be a variety of quorum conditions that are sufficient to allow tracing, such as two out of three or unanimity. Furthermore, the tracer party doing the tracing might not wish to reveal certain things to the trustees, such as which payment is being traced or which person is being investigated.

[Balance page 8 through page 17 omitted]