Join
today

Boliven PRO is more than just patent search

  • Build and save lists using the powerful Lists feature
  • Analyze and download your search results
  • Share patent search results with your clients

Patents »

US4926479: Multiprover interactive verification system

Share

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 ·
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 CodeA
International Classifications 38023-25;28;30;2;18;21;40;49;50 ·
20 Claims, No Drawings


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.

References Cited

U.S. Patent Documents

Document NumberAssigneesInventorsIssue/Pub Date
US3781472 DATOTEK Goode et al. Dec 1973
US3886313 DATOTEK Branscome et al. May 1975
US4013837 Datotek, Inc. Branscome et al. Mar 1977
US4020285 Datotek, Inc. Branscome et al. Apr 1977
US4091423 Datotek, Inc. Branscome May 1978
US4140873 Datotek, Inc. Kinch, Jr. et al. Feb 1979
US4368357 International Telephone and Telegraph Corporation Gurak Jan 1983
US4731842 International Business Machines Corporation Smith Mar 1988
US4748668 Yeda Research and Development Company Limited Shamir et al. May 1988

Referenced By

Document NumberAssigneeInventorsIssue/Pub Date
US6324287 SCM Microsystems, Inc. Joseph C. Angert Nov 2001
US6075858 SCM Microsystems (U.S.) Inc. Nikolai L. Schwartzman Jun 2000
US5581615 Jacques Stern Dec 1996
US6148400 The Merdan Group, Inc. Terry Sutton Arnold Nov 2000
US5448641 Pitney Bowes Inc. Leon A. Pintsov et al. Sep 1995
US5787172 The Merdan Group, Inc. Terry Sutton Arnold Jul 1998
US6212637 Nippon Telegraph and Telephone Corporation Kazuo Ohta et al. Apr 2001
US6226618 International Business Machines Corporation Edgar Downs et al. May 2001
US6263313 International Business Machines Corporation Kenneth Louis Milsted et al. Jul 2001
US5751812 Bell Communications Research, Inc. Milton M. Anderson May 1998
US5799090 Joseph C. Angert Aug 1998
US5606609 Scientific-Atlanta Peter B. Houser et al. Feb 1997
US6983371 International Business Machines Corporation Marco M. Hurtado et al. Jan 2006
US7624451 Microsoft Corporation Marcus Peinado Nov 2009
US7245718 Mitsubishi Electric Research Laboratories, Inc. Ravi Sundaram et al. Jul 2007
US7590866 International Business Machines Corporation Marco M. Hurtado et al. Sep 2009
US6398245 International Business Machines Corporation George Gregory Gruse et al. Jun 2002
US6922780 The DIRECTV Group, Inc. Philip I. Siegel Jul 2005
US7277870 International Business Machines Corporation Magda Mourad et al. Oct 2007
US6611812 International Business Machines Corporation Marco M. Hurtado et al. Aug 2003
US7058808 Cyphermint, Inc. Oleg Anatolievich Zolotorev et al. Jun 2006
US6978375 International Business Machines Corporation Stefan Nusser et al. Dec 2005
US7213005 International Business Machines Corporation Magda Mourad et al. May 2007
US7269564 International Business Machines Corporation Kenneth Louis Milsted et al. Sep 2007
US7206748 International Business Machines Corporation George Gregory Gruse et al. Apr 2007
US6826687 International Business Machines Corporation Pankaj Rohatgi Nov 2004
US6701434 International Business Machines Corporation Pankaj Rohatgi Mar 2004
US6389403 International Business Machines Corporation John J. Dorak, Jr. May 2002
US6587837 International Business Machines Corporation Richard Spagna et al. Jul 2003
US6834110 International Business Machines Corporation Franco Marconcini et al. Dec 2004
US7110984 International Business Machines Corporation Richard L. Spagna et al. Sep 2006
US7529927 Microsoft Corporation Marcus Peinado et al. May 2009
US6389538 International Business Machines Corporation George Gregory Gruse et al. May 2002
US6345256 International Business Machines Corporation Kenneth Louis Milsted et al. Feb 2002
US6418421 International Business Machines Corporation Marco M. Hurtado et al. Jul 2002
US7549051 Microsoft Corporation Blair Brewster Dillaway et al. Jun 2009
US7487128 International Business Machines Corporation Richard L. Spagna et al. Feb 2009
US6574609 International Business Machines Corporation Edgar Downs et al. Jun 2003
US7103574 Microsoft Corporation Marcus Peinado et al. Sep 2006
US7236590 Matsushita Electric Industrial Co., Ltd. Gregory Michael Perkins et al. Jun 2007
US6859795 Cyphermint, Inc. Oleg Anatolivich Zolotorev et al. Feb 2005
US6683956 Hitachi, Ltd. Makoto Aikawa et al. Jan 2004
US6959288 International Business Machines Corporation Cesar Medina et al. Oct 2005
US7278025 IVI Smart Technologies, Inc. Tamio Saito et al. Oct 2007
US7890428 Microsoft Corporation Cecil Ray Brooks et al. Feb 2011
US7680744 Microsoft Corporation Arnold N. Blinn et al. Mar 2010
US7693280 Microsoft Corporation Brian P. Evans et al. Apr 2010
US7757077 Microsoft Corporation Marcus Peinado et al. Jul 2010
US7788496 Microsoft Corporation Andrey Lelikov et al. Aug 2010
US7801821 Microsoft Corporation Cecil Ray Brooks et al. Sep 2010
US7840806 Enterprise Information Management, Inc. Frank J. Hammond, II et al. Nov 2010
US7856404 Microsoft Corporation Brian P. Evans et al. Dec 2010
US6456716 Merdan Group, Inc. Terry Sutton Arnold Sep 2002
US7500109 International Business Machines Corporation Stefan Nusser et al. Mar 2009
US7979911 Microsoft Corporation Kristjan E. Hatlelid Jul 2011
US8005757 Microsoft Corporation Marcus Peinado et al. Aug 2011
US8091142 Microsoft Corporation Yeu Liu et al. Jan 2012
US8103592 Microsoft Corporation Andrey Lilikov et al. Jan 2012
US8130947 SAP AG Florian Kerschbaum et al. Mar 2012
US8122511 International Business Machines Corporation Yoshinobu Ishigaki et al. Feb 2012
US8239917 Enterprise Information Management, Inc. Frank J. Hammond, II et al. Aug 2012
US8290874 Microsoft Corporation Brian P. Evans et al. Oct 2012
US8321690 Microsoft Corporation Eduardo P. Oliveira et al. Nov 2012
US8325916 Microsoft Corporation Eduardo P. Oliveira et al. Dec 2012
US8411854 --
US8380634 --
US8422683 --
US8438645 --
US8700535 --

Patent Family

The current document is not in a family.