Filing Information

Inventor(s)	Shafi Goldwasser · Joseph Kilian · Avi Wigderson · Michael Ben-Or ·
Assignee(s)	Massachusetts Institute of Technology · Yissum Research Development Company of the Hebrew University of Jerusalem ·  View assignee updates
Attorney/Agent(s)	Hamilton, Brook, Smith & Reynolds ·
Primary Examiner	Stephen C. Buczinski ·
Assistant Examiner	Bernarr Earl Gregory ·
Application Number	US7188284
Filing date	04/29/1988
Issue date	05/15/1990
Predicted expiration date	04/29/2008
U.S. Classifications	380/23  · 380/25  ·
International Classifications	H04K 100  ·
Kind Code	A
International Classifications	38023-25;28;30;2;18;21;40;49;50 ·

Patent Family

Abstract

In a multiparty verification system, a prover and a verifier are coupled torocess respective outputs to provide a system output such as an identification verification. The prover is formed of plural units which share confidential information used to encrypt information carried by the prover. Communication between the prover units is prevented. The first prover unit encrypts the information based on additional information received from the verifier and transfers the encrypted information to the verifier. Subsequently, the verifier obtains from the second prover unit the shared confidential information required to decrypt a subset of the transmitted encrypted information.

Independent Claims | See all claims (20)

1. 1. A method in a multiparty verification system for processing respective outputs from a prover and a verifier, the prover comprising first and second prover units which share information, the method comprising:limiting communications between the first and second prover units;in the first prover unit encrypting identification information based on confidential verifier information from the verifier and confidential prover information shared by the first and second prover units;providing prover information required for decryption from the second prover unit to the verifier.
2. 3. A method in a multiparty verification system for processing respective outputs from a prover and a verifier, the prover comprising first and second prover units which share confidential information for generating outputs therefrom, communication between the first and second prover units being limited when the prover and verifier are coupled, the method comprising:providing verifier encryption information from the verifier to the prover;causing the first prover unit to commit to a transfer of information to the verifier, the transferred information being encrypted by the first prover unit based on the verifier encryption information and prover encryption information shared by the first and second prover units;providing selection information from the verifier to the second prover unit to select one of plural subsets of the encrypted information for decryption;providing prover encryption information, corresponding to the selected subset of the encrypted information, exclusively, from the second prover unit to the verifier; anddecrypting the selected subset of encrypted information.
3. 11. An identification method in a multiparty verification system for processing respective outputs from a prover and a verifier to identify the prover, the prover and verifier sharing an identification set of information, the prover comprising first and second prover units which share confidential information comprising a solution subset of information having a predetermined mathematical relationship with the identification set of information, the solution subset being readily identifiable as a proper solution but not being readily determinable from the identification set of information, communication between the first and second prover units being limited when the prover and verifier are coupled, the method comprising, in a plurality of cycles with respect to identification sets of information permutated by the first prover unit:providing verifier encryption information from the verifier to the first prover unit;in the first prover unit encrypting, based on the verifier encryption information and prover encryption information shared by the first and second prover units, permutated information derived from the identification set of information, and forwarding the encrypted information to the verifier;providing selection information from the verifier to the second prover unit to select the identification set of information or the solution subset of the encrypted permutated information for decryption;providing prover encryption information corresponding to the selected encrypted information from the second prover unit to the verifier; anddecrypting the selected encrypted information.
4. 17. A data processing system for implementing a verification sequence comprising first and second processors in communication with each other, the first processor comprising at least first and second units which share confidential information and which are prevented from communicating with each other regarding verification information when in communication with the second processor during the verification sequence, the first and second processors cooperating in communication with each other to provide an output as a function of the confidential information of the first processor without disclosure of the confidential information of the first processor such that the second processor is assured of the validity of the output due to its separate communication with the first and second units of the first processor.