United States Patent (19)
`Chaum
`
`Patent Number:
`11
`45) Date of Patent:
`
`4,926,480
`May 15, 1990
`
`54). CARD-COMPUTER MODERATED SYSTEMS
`76 Inventor: David Chaum, 14652 Sutton St.,
`Sherman Oaks, Calif. 91403
`21 Appl. No.: 198,315
`(22
`Filed:
`May 24, 1988
`
`col For Transmitting Personal Information Between
`Organizations', Advances in Crytology. Proceedings of
`Crypto 86, Springer Verlag Press, 1987.
`Elgamal, "A Public Key Cryptosystem. And Signature
`Scheme Based On Discrete Logarithms', Advances in
`Cryptology. Proceedings of Crypto 84, Springer Verlag
`Press, 1985.
`Chaum et al., “An Improved Protocol For Demonstrat
`ing Possession Of Discrete Logarithms And Some
`Generalations', Advances in Cryptology. Proceedings of
`Eurocrypt 87, Springer Verlag Press, 1988.
`Rivest et al., “A Method For Obtaining Digital Signa
`tures And Public-Key Cryptosystems', Communica
`tions of the ACM, Feb. 1978, pp. 120-126.
`Rabin, "Digitalized Signatures And Public-Key Func
`tions. As Intractable As Factorization', MIT Technical
`Report MIT/LCS/TR-212, Jan. 1979.
`Peralta et al., “A Simple And Secure Way To Show
`The Validity Of Your Public Key', Proceedings of
`Crypto 87, Springer Verlag Press, 1988.
`Primary Examiner-Stephen C. Buczinski
`Assistant Examiner-Bernarr Earl Gregory
`Attorney, Agent, or Firm-Nixon & Vanderhye
`(57)
`ABSTRACT
`A user controlled card computer C and communicating
`tamper-resistant part T are disclosed that conduct se
`cure transactions with an external system S. All com
`munication 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, Scan
`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 corre
`sponding 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.
`
`18 Claims, 9 Drawing Sheets
`
`63
`
`(56)
`
`Related U.S. Application Data
`Continuation-in-part of Ser. No. 524,896, Aug. 22,
`1983, Pat. No. 4,759,063, and Ser. No. 784,999, Oct. 7,
`1985, Pat. No. 4,759,064, and Ser. No. 168,802, Mar.
`16, 1988, abandoned, and Ser. No. 123,703, Oct. 23,
`987.
`(51) Int. Cl. .............................................. H04K 1/00
`52 U.S. C. ........................................ 380/23: 380/24;
`380/30; 235/379; 235/380; 235/382
`58 Field of Search .................................... 380/23-25,
`380/30, 43, 44, 47, 49,50; 235/379-382
`References Cited
`U.S. PATENT DOCUMENTS
`4,264,782 4/1981 Konheim ............................... 380/25
`4,393,269 7/1983 Konheim ............................... 380/25
`4,423,287 12/1983 Zeidler .....
`... 235/382 X
`4,529,870 7/1985 Chaum .....
`... 235/379 X
`4,590,470 5/1986 Koenig .................................. 380/23
`4,612,413 9/1986 Robert et al. ......................... 380/24
`4,625,076 11/1986 Okamoto et al. ..................... 380/23
`4,656,474 4/1987 Mollier et al........
`... 235/380 X
`4,667,087 5/1987 Quintana ............................. 235/380
`4,697,072 9/1987 Kawana .......
`... 235/379 X
`4,710,613 12/1987 Shigenaga........................... 235/380
`4,748,668 5/1988 Shamir et al. ......................... 380/30
`4,757,185 7/1988 Onishi ..........
`... 235/379
`4,759,063 7/1988 Chaum .................................. 380/30
`4,759,064 7/1988 Chaum .................................. 380/30
`4,782,455 1 1/1988 Morinouchi et al. ........... 235/380 X
`OTHER PUBLICATIONS
`Chaum, "Design Concept For Tamper Responding
`System', Proc. of Crypto 82, Plenum Press, 1983.
`Chaum et al., "A Secure And Privacy Protecting Proto
`ExTERNA
`SYSTEM
`
`S
`
`t35
`
`f 13
`(DATA ENTRY)
`
`
`
`
`
`
`
`120
`(TAMPER
`RESISTANT
`PART)
`
`TCL Exhibit 1010
`
`

`

`5,mm“
`
`S.
`
`1mt
`
`m.t.555Do”4<zmmhxm
`
`“.6;
`
`m
`
`a
`
`9.m1
`
`0
`
`%£52m<29LD
`
`tw:
`
`mu_:h
`
`unlawfiwmuimbmslwmn
`
`
`
`m,...............6"A552.F2398”.
`0V.«82%48.
`
`m.h
`
`TCL Exhibit 1010
`
`TCL Exhibit 1010
`
`
`
`

`

`4,926,480
`
`95$...5
`
`(09a53.n.vo332uguIma
`0V:33:
`mEu3DE
`
`«noofiég4new.
`
`U.S. Patent
`US. Patent
`
`Z "101,4.
`N.Genn
`
`May 15, 1990
`
`
`
`.->1Eoucm.InaNewBannoA.:3n.An-EMEoucEIx >n-vk.33nu.vk=.-_%Eoucm.
`
`8N
`
`Sheet 2 of 9
`
`.ofiéa983.a.&
`
`:33:3..
`
`.mone:..26$2EN...aMvanhafar—.5.6A..8.S.
`.qurdwfxaxxI2%
`
`adsIx8m
`
`
`
`
`
`
`
`
`
`
`
`
`
`cafe."NA.:63
`
`
`
`.qufltsE"NA.3.52
`
`
`TCL Exhibit 1010
`
`TCL Exhibit 1010
`
`
`
`

`

`US. Patent
`
`May 15, 1990
`
`Sheet 3 of9
`
`4,926,480
`
`Non
`
`vow.
`
`2
`
`an
`
`E038..xEoucm.1.
`
`
`
`8.:sA..33s.u.vp.52
`
`man
`
`r..612-vpinr51.23...32
`
`3m
`
`_._Ex5.8I$8
`
`
`
`__31:3A..32
`
`.32r.vh:522.2mm:+cu:.2:5:AE8m
`
`._:sA.
`
`mom.
`
`8n
`
`2m
`
`8.5E.agar
`
`:235x3+:33u:5
`
`$2+c2325xaA.E
`
`
`
`2.5T...:82:
`
`man
`
`TCL Exhibit 1010
`
`TCL Exhibit 1010
`
`
`
`
`
`
`
`

`

`mm,
`
`0y53%A..-“Lil4{FE.
`
`US. Patent
`
`v.35“
`
`AmaA8.3;4aasA.83;m>H=u:HsA.
`
`.339.aA3&3
`fleahaéa:3.F.«A...aS8vamaxE
`
`33asA.
`
`15.3.asA.a}...
`
`>23A2.3;
`
`..mMEsauAn1~A5,>u-vpa...1E852n>W.NS.M:a“0A:"FE
`
`maintaé
`
`3v.anoA-33
`
`Eoucm.I33V
`
`TCL Exhibit 1010
`
`TCL Exhibit 1010
`
`
`

`

`US. Patent May 15,1990
`
`Sheet 5 of 9
`
`4,926,480
`
`T
`
`501
`
`[51] I m'x
`[51] a c: m"
`
`He . 5
`C
`
`W
`
`502
`
` u - random
`v - random
`
`
`
`
`
`[52] . [51]“[211V
`[52] T <- : mxugx"
`
`
`
`504
`
`
`
`
`
`
`[53] ?-7 mug"
`[54.1] - [51])!
`[54-2] - CI
`[54-31 - q'
`[54.1] -> w: me
`[54.2] -> W: gxy
`[54.3] -> w: figmd
`
`
`
`
`
`
`7
`[57.] - [56] x
`[57] -> C: mu'wgv'w
`
`506
`w - random
`[56] - [551?W ,
`[5511' ‘_ : mxu WgXV W
`
`‘f'
`[581-[57]
`[58] -> w: m" g"
`
`.
`
`505
`
`
`
`
`[54.3] 7-? {(15421)
`
`u' - random
`v' - random
`[551 - [54.11"'[§4.21"
`
`[55] c <- : mm 93W
`
`, .
`
`[58] 7-? m"u'gV
`
`TCL Exhibit 1010
`
`TCL Exhibit 1010
`
`

`

`U.S. Patent
`
`May 15, 1990
`
`Sheet 6 of 9
`
`4,926,480
`
`9 "101,4
`
`209
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ipui: -> 1 [99]
`
`Z09
`
`TCL Exhibit 1010
`
`

`

`.b.3.u.vo5..yECU—LN.l0a«E
`
`9mgAfunmEaten..-.o
`1Eaten.I.m,.8“
`
`3
`
`mt
`
`UhSena
`
`h3oh
`
`6098..IatBu
`
`Mo.noA-5..
`
`m6,
`
`.mm2SEVE
`tat3..5%
`
`.min.92onu-vhan7EmBxGEE-at
`
`mamaasA.FE
`
`.0asA.as:
`
`2.82.onEx8EEasA-_E0yham.an425.3“Bxv.
`
`«2.3m5x8:.qunoA.atm.E..3E9.8“
`
`TCL Exhibit 1010
`
`TCL Exhibit 1010
`
`
`

`

`Sheet 8 of 9
`
`9
`
`.m.54.35..an
`
`.uaa$.awn...“:5A.3.3
`
`HaIfix;
`
`85.3:.«AoaéwA«ana::sA.3.3.
`
`
`U.S. Patent
`SU
`ma
`
`May 15, 1990
`
`I3oh
`
`as."oA.:2tEoUcEImDEm
`
`’Q..E.au.v.FRayEOUCSI.mWFE5%
`
`mom
`
`...na:noA.33.uaum.nwmfia.“a...8a
`
`RE
`
`aura..:egA.mrmsrpum083
`
`8 "101,4.
`a.Senn
`
`
`
`
`
`
`
`
`
`
`
`4,926,480
`4,926,480
`
`TCL Exhibit 1010
`
`TCL Exhibit 1010
`
`
`

`

`US. Patent May 15, 1990
`
`Sheet 9 of 9
`
`4,926,480
`
`H6 . 9
`
`902
`
`MW) 7-? 1
`s' - random
`a‘ - random
`
`[92.2] T <- : a'
`
`[92.1] T <.- : 3'
`
`901
`s - random
`a - random
`[911° c: szt‘
`
`[93] - 1(52[92.1]2t3+[92'«2})d‘
`[93] ., c: {(323.2 tmm )d
`
`[9319' 7-? f([91]s'2t'a')
`
`
`[94.1] . [9115-29
`[94.2] - 93
`[94.1] -) W: Sgs'Ltai-a'
`
`
`[94.2] -) w: 1(323'2t3+8')d'
`
`[94.2]6 7-? f([94.1])
`a" - Q([94.1]) xor b'
`[95.1 -f([94.]]ta':')d:
`[95.11c <-:1(3 3-2pm +a )d
`
`[95.2] c <- : a"
`[95.119" 2.? f([91]s-2ta'+[95.2])
`
`
`{96-11 - [95.1]
`..
`'
`[96.2] - [95.2]
`'
`[96.1] T <- : {(323'2‘a+a +a )d'
`
`[96.2] 1' <- : a"
`
`[96.119 7.? t(s2[92.112ta+I92-21+[95-21)
`b" - a xor [92.2] xor [96.2]
`
`TCL Exhibit 1010
`
`TCL Exhibit 1010
`
`

`

`1.
`
`CARD-COMPUTER MODERATED SYSTEMS
`
`10
`
`15
`
`35
`
`RELATED APPLICATIONS
`This application is a continuation-in-part of my prior
`co-pending applications noted below:
`(a) Ser. No. 06/524,896 filed August 22, 1983 and issued
`July 19, 1988 as U.S. Pat. No. 4,759,063;
`(b) Ser. No. 06/784,999 filed October 7, 1985 and issued
`July 19, 1988 as U.S. Pat. No. 4,759,064;
`(c) Ser. No. 07/168,802 filed March 16, 1988, now aban
`doned; and
`(d) Ser. No. 07/123,703 filed November 23, 1987.
`BACKGROUND OF THE INVENTION
`1. Field of the Invention.
`This invention relates to secure transaction systems,
`and more specifically to configurations and crypto
`graphic techniques for transactions between two sub
`systems moderated by a third subsystem.
`20
`2. Description of Prior Art.
`There are essentially three approaches to secure con
`sumer transactions in the known art based on active
`devices held by individuals. Each of these three has
`25
`some shortcomings solved by the others, but the tech
`niques are mutually exclusive.
`The first, and perhaps most obvious, known approach
`is based solely on portable tamper-resistant devices,
`such as are commonly called "IC,' "chip,' or "smart'
`cards. The active part of these cards is comprised today
`30
`of preferably one (but possibly more) integrated cir
`cuit(s), typically including input/output interface, mem
`ory, and often processing means.
`Security from the point of view of the card issuing
`organization under this approach derives primarily
`from the tamper-resistance of the card: the individual
`holding a card is assumed unable to modify or discover
`the content of some data stored within it. The card
`issuer should ensure that the logical structure of the
`card allows only the desired operations to be performed
`on this protected data. Security often also requires that
`the instructions requesting (and results of) these allowed
`operations be securely communicated to (and from) the
`card. Physically secured communication may be possi
`ble when the card is in direct mechanical contact with
`45
`(or at least quite near) other apparatus trusted by the
`card issuer. A more attractive basis for secure commu
`nication, however, is provided by cryptographic tech
`niques, which make direct contact or even proximity
`unnecessary. These techniques allow wider use while
`reducing the trust issuers must have in each terminal
`device within a system. The basis for security of such
`cryptographic communication must of course be keys
`placed within a card's protected storage initially or
`once otherwise secured communication is established.
`Care must also be taken in such systems to further
`protect issuers and individuals from terminal devices,
`even once cryptographically secured communication is
`established between the card and its issuer. This is so
`because modified or completely bogus terminals might
`benefit from making improper use of data provided
`them by individuals (such as, e.g., PIN codes) or from
`displaying misleading information (such as, e.g., im
`proper amounts of payment) to individuals. Solutions
`include a keyboard and display on board the card. The
`65
`keyboard ensures the issuer that input from the individ
`ual card holder is supplied securely to the issuer; the
`display allows the issuer to control messages shown to
`
`4,926,480
`2
`the individual. These humanly operable input and out
`put means are tamper-resistantly integrated with the
`secured chip(s), under this first approach. The recently
`demonstrated Visa/Toshiba "SuperSmart' card, for
`instance, is programmed to display a transaction code
`together with the amount of payment, which allows an
`onlooking shopkeeper (who is assumed able to assess
`the genuineness of a card) to have confidence that the
`transaction code will be honored for the amount dis
`played. (The shop's security would of course be im
`proved if it instead communicated through its own
`computer.)
`One fundamental shortcoming of this first approach is
`that security derives completely from tamper-resist
`ance. Little has been published on the topic of tamper
`resistance of portable computers (but see "Design con
`cepts for tamper-responding systems,' by the present
`applicant, in Proceedings of CRYPTO 82, D. Chaum,
`R. Rivest & A. Sherman, Eds., Plenum 1983). Never
`theless, the threat level such devices available today can
`withstand is certainly above that which could be perpe
`trated without sophisticated tools, but is also almost
`surely below that of a determined attack by a "national
`laboratory.' Moreover, a security system employing a
`single such technologically-based countermeasure may
`be quite vulnerable to unanticipated modes of attack.
`Such systems can even be a national vulnerability, as
`evidenced by attacks on consumer payment systems
`during international hostilities. If payments are to be a
`major early application of card systems, the above con
`siderations suggest that security which relies on tamper
`resistance alone should be copsidered unaccepta
`ble-particularly if each card contains the same master
`key.
`A second intrinsic shortcoming, of this approach
`based wholly on tamper-resistant devices, is that indi
`viduals have no effective way of ensuring the protec
`tion of their own interests. Few may regard a large
`card-issuing organization deliberately cheating them
`out of money in transactions of modest value as a credi
`ble scenario. Nevertheless, it is quite another thing to
`rule out cheating for economic gain by employees or
`others who gain access to all or even part of a system.
`The resulting economic losses to individuals are at least
`potentially detectable and recoverable. There are other
`aspects of a system, such as the ability to issue and re
`voke privileges, whose abuse may be detectable but is
`not fully recoverable: damage from a personal auton
`omy point of view is done by the initial denial of access
`to privileges and cannot be recovered once lost. Other
`dangers may not even be detectable: much data col
`lected in transactions can be considered sensitive from a
`personal privacy perspective. Cards might leak such
`sensitive data directly, or if they reveal universally
`identifying numbers or the like, much such data could
`be linked and collected together. Moreover, the privacy
`related data and the autonomy related decision making
`power of a system may come under control of an entity
`with significantly different intentions than that under
`which the system was originally accepted.
`A second known approach to secure transactions is
`based on apparatus comprising an externally interfaced
`tamper-resistant part that acts as an intermediary be
`tween external systems and a user-controlled worksta
`tion. An example of this approach is disclosed in U.S.
`Pat. No. 4,529,870, titled "Cryptographic identification,
`financial transaction, and credential device," issued to
`
`50
`
`55
`
`TCL Exhibit 1010
`
`

`

`10
`
`4,926,480
`4.
`3
`and stored in the workstation. When such a signature is
`the present applicant. The difference between the first
`released by the individual, the shop receiving it can
`and this second approach derives from the workstation:
`verify its validity. But the shop cannot be sure that
`it need not be trusted by anyone but the individual. This
`copies of the same signature have not also been given to
`allows the individual to develop substantial trust in the
`other shops, in general, without consulting some sort of
`workstation, because the individual is free to obtain its
`central registry of accepted signatures. Particularly for
`hardware and software from any source (or even to
`low value transactions, the cost of consulting such a
`construct it) and this personal workstation need not
`directory may be considerable. This problem can be
`have any structure or data that its owner cannot know
`addressed partly by new techniques that compromise
`or modify.
`the privacy of those attempting to show the same signa
`An advantage of such trustin workstations obtainable
`ture more than once, as described in co-pending appli
`by individuals is that it allows individuals to directly
`cation of the present applicant, titled "One-show blind
`benefit from the now widely known "public key digital
`signature systems,” filed 3/16/88, with U.S. Ser. No.
`signatures.” These can provide, for each transaction, a
`numerical receipt checkable by the individual's work
`168,802, now abandoned.
`More fundamental (but related) problems occur with
`station-and also verifiable by any third party arbiter or
`15
`digital signatures representing "credentials,” which are
`judge. A comprehensive set of such receipts retained by
`statements issued by organizations about individuals.
`the workstation can protect many of an individual's
`Such credentials are obtained by a special crypto
`recoverable interests. They allow, for instance, ulti
`graphic process using blind signatures and are then
`mately at least a proper settling of accounts.
`presented to gain access to privileges. A problem is that
`Other advantages are offered by trustable worksta
`tions. One is that they essentially open the possibility for
`a credential issued to one person for the purpose of
`allowing that person to gain access to some facility or
`a market in suitable hardware and software. This may
`service might too easily be lent to another person. In
`be able to meet the needs of individuals more effectively
`than tamper-resistant devices issued by organizations.
`deed, the signature itself might not even be lent, but
`Special devices adapted to various user preferences or
`communication with the (possibly remote) legitimate
`25
`holder of the credential may allow passable responses to
`disabilities are possible, for example, and the latest ad
`. queries by the person wishing to show the credential at
`vances in technology can be employed. Card issuing
`the point of access. Further problems may also result if
`organizations benefit, since they are freed from the
`additional credentials are obtained using such a bor
`burden of supplying the user interface part and of meet
`ing the demand for its features. The cost of these work
`rowed credential. Some of the credentials so obtained
`30
`might be "positive,” in the sense that it would be in the
`station features are instead shifted to the user, and can in
`effect be shared between issuer organizations, since a
`individual's interest to show them. Thus the lender
`might improperly benefit from the credentials earned by
`single workstation could even accommodate several
`tamper-resistant parts.
`the borrower. Others of these new credentials might be
`"negative,' in that they would be to the disadvantage of
`One thing that cannot be accomplished under this
`approach, however, is preventing the tamper-resistant
`the lender (and thus might inhibit such lending). No
`part from causing a loss of autonomy by partially disen
`matter how such negative credentials are obtained,
`though, they do raise what may be a fundamental prob
`franchising or locking individuals out of a system alto
`lem: individuals, even if they did initially agree to ac
`gether. Such a lockout might even be caused by a co
`vert message or signal sent to the tamper-resistant part
`cept a negative credential, may hide the existence of
`during an ordinary transaction, and the possibilities are
`such credentials (at least for some time) simply by dis
`carding them.
`greatly increased because the tamper-resistant part is
`A further limitation of published practical credential
`privy to all the individual's transaction data. Another
`mechanisms is that they do not provide the possibility
`fundamental limit on the protections obtainable under
`this approach, as with the first approach, relates to
`for credentials containing values secret from the indi
`45
`personal privacy. An individual is unable to effectively
`vidual. Such secrets are used today, for instance, as with
`ensure that the tamper resistant part does not in some
`some medical records.
`way secretly leak sensitive or identifying information
`OBJECTS OF THE INVENTION
`during transactions.
`Accordingly, it is an object of the present invention
`The third known approach may be characterized by
`50
`the complete absence of a tamper-resistant part: all
`to:
`improve organization's security in systems using per
`security derives from cryptographic protocols con
`sonal workstations, without diminishing the protections
`ducted between an external system and an individual's
`workstation. Individuals are ensured of protections for
`offered to individuals;
`their interests, including recoverability, autonomy, and
`improve individual's protections in systems based on
`tamper-resistance, without reducing the legitimately
`privacy. The shortcomings of this approach, in contrast
`needed security for organizations;
`with the previous two approaches, relate instead to
`accomplish the previous objects by providing for
`some aspects of security for organizations.
`cooperation between tamper-resistant parts and per
`An essential concept of this approach is "blind signa
`tures," as described in European Patent Publication
`sonal workstations;
`allow a tamper-resistant part to obtain a signature,
`0139313, titled "Blind signature systems,' dated 2/5/85,
`claiming priority on U.S. Ser. No. 524,896, now U.S.
`unobtainable by a workstation, from an external system,
`Pat. No. 4,759,063 by the present applicant, which is
`without allowing any additional information to be in
`incorporated herein by reference. In making a payment,
`cluded in or along with the signature;
`allow a tamper-resistant part to convince an external
`for instance, with this approach the individual obtains
`public key digital signatures through a blind signature
`system that it has obtained a signature as in the previous
`process. Each signature might represent the equivalent
`objective, without allowing it to leak any additional
`of one dollar, for example, and would be obtained by
`information;
`
`65
`
`35
`
`55
`
`TCL Exhibit 1010
`
`

`

`10
`
`30
`
`. 4,926,480
`6
`5
`FIG. 6 shows a flowchart of a preferred embodiment
`allow a tamper resistant part a role in creating a pri
`of a signature issuing protocol with blinding in accor
`vate key that gives it knowledge, unavailable to the
`dance with the teachings of the present invention.
`workstation, which is needed to use that private key,
`FIG. 7 shows a flowchart of a preferred embodiment
`while ensuring that the tamper-resistant part cannot
`of a signature possession showing protocol with sanitiz
`include any secret information in the corresponding
`ing in accordance with the teachings of the present
`public key;
`allow a certificate for a public key as in the previous
`invention.
`FIG. 8 shows a flowchart of a preferred embodiment
`object to be obtained from the external system by the
`of a protocol for a tamper-resistant part providing a
`workstation, without the system learning which public
`single bit to an external system with hiding in accor
`key it is certifying, thereby removing the need for uni
`dance with the teachings of the present invention.
`versal master keys in tamper-resistant parts;
`-
`allow a tamper-resistant part to issue signatures certi
`FIG. 9 shows a flowchart of a preferred embodiment
`of a protocol for a tamper-resistant part receiving a
`fying its agreement with certain messages;
`single bit from an external system with modifying in
`allow selection of such messages of the previous ob
`15
`accordance with the teachings of the present invention.
`ject to depend on state maintained by the tamper-resist
`ant part, including information not necessarily in the
`BRIEF SUMMARY OF THE INVENTION
`interest of an individual to retain (such as which one
`In accordance with these and other objects of the
`time-use signatures have already been shown or which
`present invention, a brief summary of an exemplary
`pseudonyms or credentials are owned by the individ
`20
`embodiment is presented. Some simplifications and
`ual);
`omissions may be made in the following summary,
`allow proximity of a tamper-resistant part associated
`which is intended to highlight and introduce some as
`with a workstation to be determined by a sensing sta
`pects of the present-invention, but not to limit its scope.
`tion;
`Detailed descriptions of preferred exemplary embodi
`allow the workstation to ensure that the external
`25
`ments adequate to allow those of ordinary skill in the art
`system cannot leak messages or signals to the tamper
`to make and use the inventive concepts will be provided
`resistant part in the above transactions;
`allow the workstation to ensure that the tamper
`later.
`A card computer C is held by an individual who can
`resistant part cannot leak messages or signals to the
`control its internal operation (almost) completely. The
`external system in the above transactions;
`individual has a tamper-resistant part T, over the inter
`allow a workstation to permit strictly limited
`nal operation of which the individual has essentially no
`amounts of data to be provided from an external system
`control. The individual also conducts transactions with
`to a tamper-resistant part, without the workstation
`one or more organizations or individuals that may col
`being able to learn the content of that data;
`lectively be called the external system S. The physical
`allow a workstation to permit a tamper-resistant part
`arrangement is such that all information transferred
`to issue strictly limited amounts of data to an external
`between T and S must pass through C as is shown in
`system, without such data becoming accessible to the
`FIG. 1. This gives C the chance to "moderate' such
`workstation;
`transfers by stopping a transfer altogether, allowing a
`allow the tamper-resistant part to convince the work
`transfer as requested by T or S, or modifying a transfer
`station of relationships between such strictly limited
`before it reaches the other party.
`data it receives and that which it issues; and
`A transaction protocol of the preferred embodiment
`allow efficient, economical, and practical apparatus
`shown in FIG. 2 allows a blind signature to be obtained
`and methods fulfilling the other objects of the inven
`by C from S. Within the signature is contained, in
`tion.
`blinded form, a public key q developed by cooperation
`Other objects, features, and advantages of the present
`45
`between C and T. The ability to form public key digital
`invention will be appreciated when the present descrip
`signatures that can be checked with q is at least in part
`tion and appended claims are read in conjunction with
`the drawing figures.
`held by T. Yet, C is ensured that q does not reveal any
`information chosen by T. Thus, C may be said to “neu
`BRIEF DESCRIPTION OF THE DRAWING
`tralize' a public key created by T and obtain a signed
`FIGURES
`certificate for it.
`Another transaction protocol, shown in FIG. 3, al
`FIG. 1 shows a combination block and functional
`diagram of a preferred embodiment including a tamper
`lows S, T, and C to develop essentially the same value,
`m, resulting from a challenge response sequence be
`resistant part, workstation, and external system in ac
`tween S and T. The protocol allows C to pad the value
`cordance with the teachings of the present invention.
`55
`of m and the exchanged messages by which it is devel
`FIG. 2 shows a flowchart of a preferred embodiment
`oped: neither Snor Tcan influence m (or the messages
`of a public key neutralization protocol in accordance
`sent in developing it) in such a way that any information
`with the teachings of the present invention.
`chosen by S or T is revealed to the other of the two.
`FIG. 3 shows a flowchart of a preferred embodiment
`of a distance bounding protocol with both outflow and
`Yet, both S and T are ensured that m results from and is
`60
`dependent on their respective challenge and response.
`inflow protection in accordance with the teachings of
`In developing m, single bits of challenge issued by S are
`the present invention.
`responded to by single bits from T. Because the amount
`FIG. 4 shows a flowchart of a preferred embodiment
`of computation required by the parties to process each
`of a digital signature protocol with obscuring in accor
`such single bit is extremely small, timing by S of the
`dance with the teachings of the present invention.
`65
`interval between its issue of a challenge bit and its re
`FIG. 5 shows a flowchart of a preferred embodiment
`ceipt of the corresponding response bit allows S to
`of a undeniable signature protocol with disguising in
`accordance with the teachings of the present invention.
`determine an upper bound on the distance to T.
`
`35
`
`50
`
`TCL Exhibit 1010
`
`

`

`5
`
`15
`
`4,926,480
`8
`7
`ated, C might also be any computer of any ownership or
`. A further protocol of the preferred embodiment,
`use. For clarity in exposition, however, C will be said to
`shown in FIG. 4, allows T to develop a digital signature
`on a message, m for instance, using the private key
`be held or owned by an individual that will use it in
`corresponding to public key q. This signature is trans
`transactions.
`It may be that C contains parts that are in general
`ferred from T to S by C in a way that allows C to ensure
`difficult for its owner to examine or modify, but the
`its correctness; the content of the message signed is
`security for organizations against abuses that might be
`controlled by T but verifiable by C. Because the result
`perpetrated against them by the individual holding C
`obtained by S is a public key digital signature, S can
`should not rely on this tamper-resistance. For example,
`verify that it was formed by the holder of the private
`it is anticipated that part of C may include memory
`key corresponding to q, and convince any third party of
`10
`this fact just by showing the signature. The signature is
`elements whose contents must be changed if C is to be
`useful to a different person. Another example is mem
`obscured by C to ensure that it does not leak any infor
`ory elements that are not usually readable, unless some
`mation from T.
`A related protocol of the preferred embodiment,
`pre-arranged PIN code, biometric, or the like is entered;
`such arrangements might protect the holder's data from
`shown in FIG. 5, allows T to show an undeniable signa
`inspection by someone else coming into possession of C.
`ture on a message, also using the private key corre
`sponding to public key q. Undeniable signatures are
`While such tamper-resistance does prevent the holder
`disclosed in a co-pending application, titled "Undeni
`from certain accesses and may provide improved secu
`rity for individuals, and indirectly for organizations, the
`able signature systems,” with U.S. Ser. No. 123,703,
`security of organizations against abuses by individuals
`filed 23/11/87, by the present applicant, which is in
`does not rely on it, and it primarily acts as a protection
`cluded herein by reference. Such showing of an undeni
`able signature by T involves S forming a challenge that
`of the owner against other individuals.
`can be convincingly responded to by T (with all but
`Tamper-resistant part T 120 is an information pro
`substantially negligible probability) only if T has
`cessing device, perhaps a general microcomputer. It
`formed the undeniable signature properly and particia
`derives input from interface 125 that is provided by C
`25
`pates informing the response. Such an undeniable signa
`110 and provides output through interface 125 to C 110.
`ture can be re-shown as often as desired, but only by
`It is intended to at least maintain some secrets from the
`cooperation of Teach time. Again, C is able to ensure
`individual who holds it and to have at least some struc
`that communication between T and S during this trans
`ture that is unmodifiable by the individual, that which at
`action is completely disguised, apart from the showing
`least prevents the individual from making some accesses
`30
`of the undeniable signature.
`to the secrets it contains. These secret values need not
`be explicitly stored in ordinary memory, elements; they
`A pair of yet other transaction protocols, whose uses
`may be encoded in the structure of T in some other
`are in some sense analogous to those of FIG. 2 and FIG.
`way, possibly in efforts to keep them more securely
`5, are shown in FIG. 6 and FIG. 7, respectively. The
`protocol of FIG. 6 allows T to receive a digital signa
`from individuals. Some of the secrets of T may of
`35
`course be stored in encrypted form by C.
`ture from S that is unobtainable by C, but C is able to
`It is anticipated that Ts might be supplied by organi
`ensure that only the signature on the desired message is
`learned by T. The protocol of FIG. 7 allows T to later
`zations to individuals. One way this might be accom
`convince S that it does have the signature of the particu
`plished is by direct issue of one. Tselected by an organi
`lar message and is responding to challenges, without
`zation to a specific individual. Another issuance proce
`allowing C to obtain the signature.
`dure, which may have advantages to individuals, allows
`Yet another pair of transaction protocols shown in
`the individual to choose between a plurality of Ts, per
`haps even in a way that prevents the organization from
`FIG. 8 and FIG. 9 allow the transfer of a s