United States Patents Authored

Random sample elections

Hidden-code voting and marking systems

Scan-integrity election systems

Near to eye display system and appliance

System and apparatus for eyeglass appliance platform

Video copy prevention systems with interaction and compression

Ballot integrity systems

Secret-ballot systems with voter-verifiable integrity

Distributed communication security systems

Multi-purpose transaction card system

Multi-purpose transaction card system

Electronic lock that can learn to recognize any ordinary key

Random number generator security systems

Physical and digital secret ballot systems

Partitioned information storage systems with controlled retrieval

Limited-traceability systems

Private signature and proof systems

Automatic real-time highway toll collection from moving vehicles

Compact endorsement signature systems

Designated-confirmer signature systems

Optionally moderated transaction systems

Optionally moderated transaction systems

Selected-exponent signature systems

Unpredictable blind signature systems

One-show blind signature systems

Returned-value blind signature systems

Undeniable signature systems

Card-computer moderated systems

One-show blind signature systems

Blind unanticipated signature systems

Blind signature systems

Cryptographic identification, financial transaction, and credential device

Random sample elections

Inventor: David Chaum

Abstract: A novel method allows a random sample of a large population of voters to cast votes and for both the unpredictability/un-manipulability of the sample selection and the integrity of the tally to be verified by any interested parties using public information. The problem of vote selling is addressed. Also, a variant allows voters to remain substantially anonymous.

 

Hidden-code voting and marking systems

Inventor: David Chaum

Abstract: An improved paper ballot voting system allows voters to verify that their ballots are correctly counted and provide substantiating evidence if they are not. Codes are revealed to voters by the act of marking the ballot during voting and voters can check that these codes are posted. If these codes are not posted as marked, voters can make the codes they obtained public. These codes made public by voters can be compared against codes that were cryptographically committed to in advance of the election. If the codes from voters do in fact match codes committed to, evidence of incorrectness of the vote tallying is provided.

 

Scan-integrity election systems

Inventor: David Chaum

Abstract: A paper-ballot voting system is disclosed in which voters can retain symbols printed adjacent to the particular candidates or ballot question positions that they mark. Including ballot serial numbers on the forms allows voters to check online the symbols recorded for their ballots while maintaining ballot secrecy. In case of dispute, a physical resolution procedure lets voters establish whether the recorded symbols are correct with respect to the actual physical ballots. Some examples allow forms to be obtained online and voted by physical or facsimile delivery. Voters who cannot read ballots or cannot mark ballots can nevertheless vote while maintaining ballot secrecy. The overall integrity of the outcome is provided transparently.

 

Near to eye display system and appliance

Inventors: David Chaum, Thomas W. Mossberg, John R. Rogers

Abstract: A near-to-eye display system for forming an image as an illuminated region on a retina of at least one eye of a user is disclosed. The system includes a source of modulated light, a proximal optic positionable adjacent an eye of the user to receive the modulated light. The proximal optic has a plurality of groups of optically redirecting regions. The optically redirecting regions are configured to direct a plurality of beams of the modulated light into a pupil of the eye to form a contiguous illuminated portion of the retina of the eye. A first group of the optically redirecting regions is configured to receive modulated light from the source and redirect beams of the modulated light into the pupil of the eye for illumination of a first portion of the retina. A second group of the optically redirecting regions is configured to receive modulated light from the source and redirect beams of the modulated light into the pupil of the eye for illumination of a second portion of the retina.

 

System and apparatus for eyeglass appliance platform

Inventor: David Chaum

Abstract: The present invention relates to a personal multimedia electronic device, and more particularly to a head-worn device such as an eyeglass frame having a plurality of interactive electrical/optical components. In one embodiment, a personal multimedia electronic device includes an eyeglass frame having a side arm and an optic frame; an output device for delivering an output to the wearer; an input device for obtaining an input; and a processor comprising a set of programming instructions for controlling the input device and the output device. The output device is supported by the eyeglass frame and is selected from the group consisting of a speaker, a bone conduction transmitter, an image projector, and a tactile actuator. The input device is supported by the eyeglass frame and is selected from the group consisting of an audio sensor, a tactile sensor, a bone conduction sensor, an image sensor, a body sensor, an environmental sensor, a global positioning system receiver, and an eye tracker. In one embodiment, the processor applies a user interface logic that determines a state of the eyeglass device and determines the output in response to the input and the state.

 

Video copy prevention systems with interaction and compression

Inventor: David Chaum

Abstract: Disclosed are systems and methods for providing video content while inhibiting the copying of that content for later viewing. Video images may be made difficult to copy for presentation at later times by the omission or addition of content developed in relation to the particular initial viewing. For instance, video information may be customized by omitting information that is not likely to be substantially perceived by the initial viewer but that is substantially likely to be perceived as missing by at least some other viewers.

 

Ballot integrity systems

Inventor: David Chaum

Abstract: Disclosed are voting systems based on paper ballots that provide integrity of the election outcome through the novel use of encrypted votes and other techniques. In some example embodiments, holes through layers allow voters to see and mark symbols on lower layers, carbonless coatings allow voters to obtain substantially identical marks on facing surfaces, self-adhesive stickers are removed from one position and placed by voters hiding vote-revealing indicia on a second position, and scratch-off layers bearing vote-revealing indicia are destroyed while being removed to expose coded information. Simplified cryptography for realizing these systems is also presented. Related systems allow those with various disabilities to develop and check voted ballot forms that are substantially indistinguishable from those voted by other voters. Inclusion of write-in votes is provided for. Also provided are inclusion of provisional ballots and spoilt ballots and integration with registration sign-in.

 

Secret-ballot systems with voter-verifiable integrity

Inventor: David Chaum

Abstract: An election system provides, in one example, each voter with multiple physical “layers” that the voter is able to choose between. The voter takes part of the layers as a kind of receipt and the other layers are retained and/or destroyed by the system. The actual vote is not readily revealed by the layers taken by the voter, thus protecting against improper influence. In the voting booth, when all the layers are combined, however, the voter is readily able to verify the vote. Moreover, posted images of the layers not taken by the voter can be used to compute the election results in a way that is verifiable by interested parties. The results cannot be changed without substantial probability of detection and privacy of votes can be maintained unless a number of parties are compromised or collude.

 

Distributed communication security systems

Inventor: David Chaum

Abstract: Solutions to the so-called “man in the middle” problem are disclosed. One example uses a mutually-random value that is the same for each of two communicants absent a man in the middle, but differs between the communicants in case a man-in-the-middle is present. Communicants become aware if their random values differ, for example, through stock content inserted into the communication stream, interactive games, or derived limitations on the channel. In other examples, opening of encrypted parts of the communication is delayed until certain other communication takes place and/or is imminent. In still further examples, a man in the middle becomes apparent because of increased latency of communication between the participants and the effect is optionally accentuated through mutually-random values that shift latency. Further aspects allow parties to apply authentication related to participants they have communicated with when they were convinced that no man in the middle was present.

 

Multi-purpose transaction card system

Inventors: David Chaum, Niels Ferguson, Jelte Van Der Hoek

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.

 

Multi-purpose transaction card system

Inventors: David Chaum, Niels Ferguson, Jelte Van Der Hoek

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.

 

Electronic lock that can learn to recognize any ordinary key

Inventor: David Chaum

Abstract: An electronic lock that can be pre-programmed or trained in the field to recognize ordinary flat metal keys by sensing their shape and comparing to a database is disclosed. The lock can be contained in standard configurations for door locks, communicates with external systems, provides control logic for querying and amending its database of allowed keys and rules, provides controlled access to logs of selected data, allows convenient but protected access to replacement batteries, can have all its electronics in the rotatable plug, can communicate and obtain power from devices in the adjacent door jam, can recognize special series key-blanks, can receive coded information entered using an unknown key that makes it useable, can be operated without a key to gain access with a code, can resist manipulation of the latching mechanism, can unlatch with very low power requirements, and provides for integration of almost all mechanism in silicon.

 

Random number generator security systems

Inventor: David Chaum

Abstract: Random number generation and systems for their use are disclosed in which parts of some contributing values are committed to or hidden or uncontrollable before they are revealed or combined. Plural parties generally contribute to the process of developing the random values and in some exemplary systems incorporating the random generator concepts other parties perform and verify the operation of the system. In some preferred embodiments, commitments or physical locking are believed to impede various cheating and collusion strategies. In other exemplary embodiments values that are committed to by a system remain hidden while a user influences other values that are ultimately combined with committed values to determine the results. In some further exemplary embodiments users of ordinary skill are able to control their contributions and in other examples users are believed to be unable to deliberately choose their contribution.

 

Physical and digital secret ballot systems

Inventor: David Chaum

Abstract: Election automation systems are disclosed that allow plural entities, for example trustees, to ensure various properties of an election, including correctness of the outcome, by initially using confidential information to form printed ballots and transferring the ballots to voters. Later when voters electronically cast ballots, such as over networks, they use the confidential information and optionally physical ballot structures to authenticate information provided them, including information indicating whether their votes were received by the trustees. Voters can also use the information in ballots to ensure the secrecy of their vote while it is transmitted to the trustees. The trustees can tabulate results while preventing colluding subsets of trustees from being able to improperly modify the outcome of the election or violate the privacy of individual voters.

 

Partitioned information storage systems with controlled retrieval

Inventors: David Chaum, Niels Ferguson, Berry Schoenmakers, Erik W. Voskuil

Abstract: An information storage system includes one or more information update terminals, a mapper, one or more partial-databases, and one or more query terminals, exchanging messages over a set of communication channels. An identifier-mapping mechanism provides (to an update terminal) a method for delegating control over retrieval of the data stored at the partial-databases to one or more mappers, typically operated by one or more trusted third parties. Update terminals supply information, that is stored in fragmented form by the partial-databases. Data-fragment identifiers and pseudonyms are introduced, preventing unauthorized de-fragmentation of information--thus providing compliance to privacy legislation--while at the same time allowing query terminals to retrieve (part of) the stored data or learn properties of the stored data. The mapper is necessarily involved in both operations, allowing data access policies to be enforced and potential abuse of stored information to be reduced.

 

Limited-traceability systems

Inventor: David Chaum

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.

 

Private signature and proof systems

Inventor: David Chaum

Abstract: Cryptographic methods and apparatus for forming (102) and verifying (103) private signatures and proofs (203,204, 207, and 209) are disclosed. Such a signature convinces the intended recipient that it is a valid undeniable or designated-confirmer signature. And such a proof convinces the intended recipient, just as any cryptographic proof. Even though the signatures and proofs are convincing to the intended recipient, they are not convincing to others who may obtain them. Unlike previously known techniques for convincing without transferring the ability to convince others, those disclosed here do not require interaction--a signature or proof can simply be sent as a single message. Because the intended recipient can forge the signatures and proofs, they are not convincing to others; but since only the intended recipient can forge them, they are convincing to the intended recipient. Exemplary embodiments use a cryptographic challenge value that is said to pivot on a trap-door function, in that the value can be manipulated by those with the corresponding trap-door information, and is believed impractical to manipulate without it.

 

Automatic real-time highway toll collection from moving vehicles

Inventors: David Chaum, Peter Hendrick

Abstract: One or more roadside collection stations (RCS) communicate over a short-range, high speed bidirectional microwave communication link with one or more in-vehicle units (IVU) associated with one or more respectively corresponding vehicles in one or more traffic lanes of a highway. At least two up-link (IVU to RCS) communication sessions and at least one downlink (RCS to IVU) communication session are transacted in real time during the limited duration of an RCS communication footprint as the vehicle travels along its lane past a highway toll plaza. Especially efficient data formatting and processing is utilized so as to permit, during this brief interval, computation of the requisite toll amount and a fully verified and cryptographically secured (preferably anonymous) debiting of a smart card containing electronic money. Preferably an untraceable electronic check is communicated in a cryptographically sealed envelope with opener. Transaction linkage data is utilized in each phase of the complete toll payment transaction to facilitate simultaneous multi-lane RCS/IVU operation. A plaza computer local area network and downlink plaza controller is also used to facilitate simultaneous multi-lane transactions.

 

Compact endorsement signature systems

Inventor: David Chaum

Abstract: Cryptographic methods and apparatus for issuing (101), endorsing (102), and verifying (103, 104) compact endorsement signatures are disclosed. Such signatures allow an endorser to provide a public-key verifiable signature on a chosen message more efficiently than if the endorser were to make a public key signature, since the endorser needs only to perform conventional cryptographic operations and has to store less data per signature than required by previously known endorsement schemes. A hierarchy of compression functions takes a plurality of one-time signatures into the value upon which the public key signature is formed. Each endorsement uses up one of the one-time signatures and provides a subset of inputs to the compression hierarchy sufficient to allow its evaluation. Preparation for subsequent endorsements is made by pre-evaluating one-time signatures and saving only some of the intermediate values of the compression hierarchy.

 

Desinated-confirmer signature systems

Inventor: David Chaum

Abstract: Cryptographic methods and apparatus for signing (101), receiving (102), verifying (103), and confirming (104) designated-confirmer signatures are disclosed. Such a signature (11) convinces the receiver that the confirmer can convince others that the signer issued the signature. Thus, more protection is provided to the recipient of a signature than with prior art zero-knowledge or undeniable signature techniques, and more protection is provided to the signer than with prior art self-authenticating signatures. A designated confirmer signature is formed in a setting where the signer creates and issues a public key (201) and the confirmer also creates and issues a public key (202). Should the confirmer offer a confirmation (13), the verifier is convinced that the signature was issued by the signer. Such confirmation can itself be, for example, self-authenticating, unconvincing to other parties, or designated confirmer. With plural confirmers, various combinations may be realized, some even including confirmer anonymity.

 

Optionally moderated transaction systems

Inventor: David Chaum

Abstract: A tamper-resistant part is disclosed that can conduct transactions with an external system through a moderating user-controlled computer or that can on other occasions be brought into direct connection with the external system. In the moderated configuration, the moderating computer is able to ensure that certain transactions with the external system are unlinkable to each other. In the unmoderated configuration the tamper-resistant part can also ensure the unlinkability of certain transactions. Also testing configurations are disclosed that allow improper functioning of the tamper-resistant part, such as that which could link transactions, to be detected by user-controlled equipment. Another testing configuration can detect improper functioning of an external system that could, for instance, obtain linking information from a tamper-resistant part.

 

Optionally moderated transaction systems

Inventor: David Chaum

Abstract: A tamper-resistant part is disclosed that can conduct transactions with an external system through a moderating user-controlled computer or that can on other occasions be brought into direct connection with the external system. In the moderated configuration, the moderating computer is able to ensure that certain transactions with the external system are unlinkable to each other. In the unmoderated configuration, the tamper-resistant part can also ensure the unlinkability of certain transactions. Also testing configurations are disclosed that allow improper functioning of the tamper-resistant part, such as that which could link transactions, to be detected by user-controlled equipment. Another testing configuration can detect improper functioning of an external system that could, for instance, obtain linking information from a tamper-resistant part.

 

Selected-exponent signature systems

Inventor: David Chaum

Abstract: Digital signature techniques are disclosed in which exponents may be selected by the message to be signed itself, by the signing party, by the party providing the message to the signing party for signature, and/or by a party to whom the signature is shown. When a message selects the exponent(s), the need for "hash functions" in known signature schemes is overcome. When the exponent is chosen by the party receiving the signature, to take another example, computation, storage and bandwidth requirements of known one-show blind signature systems may be improved. Also, the bank cannot falsely incriminate a payer for showing a signature more than once, even if the bank has unlimited computing resources.

 

Unpredictable blind signature systems

Inventor: David Chaum

Abstract: Blind signature systems secure against chosen message attack are disclosed. Multiple candidate original messages can be accommodated. Each of plural candidates in the final signature can be marked by the party issuing the signature in a way that is unmodifiable by the party receiving the signatures. The exponents on the candidates in the final signature need not be predictable by either party. In some embodiments, these exponents are not at all or are only partly determined by the candidates in the signature shown. Single candidate signatures are also accommodated.

 

One-show blind signature systems

Inventor: David Chaum

Abstract: Numbers standing for cash money can be spent only one time each, otherwise the account from which they were withdrawn would be revealed. More generally, a technique for issuing and showing blind digital signatures ensures that if they are shown responsive to different challenges, then certain information their signer ensures they contain will be revealed and can be recovered efficiently. Some embodiments allow the signatures to be unconditionally untraceable if shown no more than once. Extensions allow values to be encoded in the signatures when they are shown, and for change on unshown value to be obtained in a form that is aggregated and untraceable.

 

Returned-value blind signature systems

Inventor: David Chaum

Abstract: A payer party obtains from a signer party by a blind signature system a first public key digital signature having a first value in a withdrawal transaction; the payer reduces the value of the first signature obtained from the first value to a second value and provides this reduced-value form of the signature to the signer in a payment transaction; the signer returns a second digital signature to the payer by a blind signature system in online consummation of the payment transaction; the paper derives from the first and the second signature a third signature having a value increased corresponding to the magnitude of the difference between the first and the second values. Furthermore, the following additional features are provided: payments are unlinkable to withdrawals; a shop between the payer and signer can be kept from obtaining more value than desired by the payer; the first value need not be revealed to the signer or intermediary in the payment transaction; the returned difference can be accumulated across multiple payment transactions; and the returned difference can be divided between a plurality of payment transactions.

 

Undeniable signature systems

Inventor: David Chaum

Abstract: Cryptographic methods and apparatus for forming, checking, blinding, and unblinding of undeniable signatures are disclosed. The validity of such signatures is based on public keys and they are formed by a signing party with access to a corresponding private key, much as with public key digital signatures. A difference is that whereas public key digital signatures can be checked by anyone using the corresponding public key, the validity of undeniable signatures is in general checked by a protocol conducted between a checking party and the signing party. During such a protocol, the signing party may improperly try to deny the validity of a valid signature, but the checking party will be able to detect this with substantially high probability. In case the signing party is not improperly performing the protocol, the checking party is further able to determine with high probability whether or not the signature validly corresponds to the intended message and public key. Blinding can be used while obtaining undeniable signatures, while providing them to other parties, and while checking their validity.

 

Card-computer moderated systems

Inventor: David Chaum

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.

 

One-show blind signature systems

Inventor: David Chaum

Abstract: Numbers standing for cash money can be spent only one time each, otherwise the account from which they were withdrawn would be revealed. More generally, a technique for issuing and showing blind digital signatures ensures that if they are shown responsive to different challanges, then certain information their signer ensures they contain will be revealed and can be recovered efficiently. Some embodiments allow the signatures to be unconditionally untraceable if shown no more than once. Extensions allow values to be encoded in the signatures when they are shown, and for change on unshown value to be obtained in a form that is aggregated and untraceable.

 

Blind unanticipated signature systems

Inventor: David Chaum

Abstract: An improved blind signature system not requiring computation during blinding for anticipating which of a plurality of possible signatures will be made during signing, while still allowing the blinding party to unblind and recover the unanticipated kind of signature on what was blinded. An exemplary embodiment blinds by forming a product including a plurality of generators raised to powers normally secret from the signing party, and unblinds by forming a product with the multiplicative inverse of a signed form of the generators raised to the original powers. Re-blinding allows a signature on a value to be transformed into a signature on a particular blinded form of the value.

 

Blind signature systems

Inventor: David Chaum

Abstract: A cryptographic system allows, in one exemplary use, a supplier to cryptographically transform a plurality of messages responsive to secret keys; the transformed messages to be digitally signed by a signer; and the signed transformed messages returned to the supplier to be transformed by the supplier, responsive to the same secret keys, in such a way that a digital signature related to each original message is developed by the supplier. One important property of these systems is that the signer cannot determine which transformed message received for signing corresponds with which digital signature--even though the signer knows that such a correspondence must exist.

 

Cryptographic identification, financial transaction, and credential device

Inventor: David Chaum

Abstract: The invention provides a cryptographic apparatus which may be "personalized" to its owner. The apparatus may be utilized by its owner to identify himself to an external computer system, to perform various financial transactions with an external system, and to provide various kinds of credentials to an external system. The apparatus, in one embodiment, is separable into a cryptographic device, packaged in a tamper resistant housing, and a personal terminal device. The cryptographic device includes interface circuitry to permit information exchange with the external system, a memory device for storage of data necessary to allow identification of the owner, and control logic for controlling the exchange of data with the external system to identify the owner. Certain data which must be utilized to perform the identification information exchange is stored in the memory device in encrypted form. The decryption of this data requires the entry of a secret ID, known to the owner. The personal terminal device includes a data entry capability to allow the owner to enter his secret ID. Certain embodiments of the personal terminal device include data display capability to provide transaction information to the owner. Other embodiments include memory devices and a processor to allow storage and manipulation of relatively unsecured data of the owner.