Multiprover interactive verification system

• US 4,926,479 A
• Filed: 04/29/1988
• Issued: 05/15/1990
• Est. Priority Date: 04/29/1988
• Status: Expired due to Fees

• Current Assignee: Yissum Research Development Company of the Hebrew University of Jerusalem Ltd. (Hebrew University of Jerusalem), Massachusetts Institute of Technology
• Original Assignee: Yissum Research Development Company of the Hebrew University of Jerusalem Ltd. (Hebrew University of Jerusalem), Massachusetts Institute of Technology
• Inventors: Wigderson, Avi, Kilian, Joseph, Goldwasser, Shafi, Ben-Or, Michael
• Primary Examiner(s): Buczinski, Stephen C.
• Assistant Examiner(s): Gregory, Bernarr Earl
• Application Number:
  US07/188,284
• Time in Patent Office: 746 Days
• Field of Search: 380/23-25, 380/28, 380/30, 380/2, 380/18, 380/21, 380/40, 380/49, 380/50, 364/200, 364/900, 340/825.31, 340/825.34
• US Class Current: 713/180
• CPC Class Codes: G06Q 20/3674 involving authentication
• CPC Class Codes: H04L 2209/50 Oblivious transfer
• CPC Class Codes: H04L 9/3221 interactive zero-knowledge proofs

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.

Claims

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. A method as claimed in claim 1 wherein the confidential verifier information and the confidential prover information are chosen at random.

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; and

decrypting the selected subset of encrypted information.

4. A method as claimed in claim 3 wherein the prover encryption information shared by the first and second prover units comprises random information.

5. A method as claimed in claim 4 wherein the verifier encryption information and the selection information are chosen at random.

6. A method as claimed in claim 3 wherein both the prover and verifier have access to an identification set of numbers and a target number and the prover alone has acess to the identity of a solution subset of the identification set, the sum of the numbers of the solution subset equalling the target number.

7. A method as claimed in claim 3 wherein the prover and verifier both have access to a graph and the prover alone has access to a Hamiltonian cycle within the graph.

8. A method as claimed in claim 3 wherein both the prover and verifier have access to an identification set of information and the prover alone has access to the identity of a solution subset of the identification set, the solution subset having a predetermined mathematical relationship with the identification set, the solution subset being readily verifiable as a proper solution but not being readily determinable from the identification set of information.

9. A method as claimed in claim 8 wherein the first prover unit, in a plurality of cycles with respect to identification sets of information permutated by the first prover unit, transfers each permuted identification set encrypted, and the selection information selects information including the full identification set or the solution subset, exclusively.

10. A method as claimed in claim 3 further comprising, in a plurality of cycles, permutating the information by the first prover unit which is encrypted and transferred to the verifier.

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; and

decrypting the selected encrypted information.

12. A method as claimed in claim 11 wherein the prover encryption information shared by the first and second prover units comprises random information.

13. A method as claimed in claim 12 wherein the verifier encryption information and the selection information are chosen at random.

14. A method as claimed in claim 11 wherein both the prover and verifier have access to an identification set of numbers and a target number and the prover alone has access to the identity of a solution subset of the identification set, the sum of the numbers of the solution subset equalling the target number.

15. A method as claimed in claim 14 wherein the permutated information comprises

A={v_i, 1≦

i≦

n} where v_i is chosen at random in ##EQU18## B={w_i, 1≦

i≦

n}, the identification set C={s_i, 1≦

i≦

n} where s_i =v_i +w_i for all 1≦

i≦

n

D=Σ

_jε

J v_j

E=J, the solution subset

F=T+E_jε

J v_j, where T is the target

and the selection information selects (A,B,C), (A,D,E) or (C,E,F).

16. A method as claimed in claim 11 wherein the prover and verifier both have access to a graph and the prover alone has access to a Hamiltonian cycle within the graph.

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.

18. A system as claimed in claim 17 wherein the confidential information of the first processor is information x to which a function F(x) is applied, F(x) being readily computed but being difficult to invert, the second processor has access to F(x) and the first and second processors communicate such that the first processor demonstrates to the second processor its possession of x without disclosure of x.

19. A system as claimed in claim 17 wherein the first unit of the first processor encrypts and transfers information to the second processor, the encryption being based on confidential information from the second processor and confidential information shared by the first and second units of the first processor, and the second unit of the first processor transfers shared confidential information required for decryption to the second processor.

20. A system as claimed in claim 19 wherein the second unit of the first processor responds to selection information from the second processor to transfer to the second processor the information required for decryption of one of plural subsets of the encrypted information.