Zero knowledge document comparison between mutually distrustful parties
AssigneeInternational Business Machines Corporation
InventorKyle Nathan Patrick
Life of this patent
Estimating the term…
Abstract
Prior zero-knowledge protocols are used for exchanging secret keys, but not for comparing documents. The present invention provides a method of zero-knowledge document comparison between mutually distrustful parties by having each party exchange a set of random data and a shared hash function, applying the hash function to concatenations of the document and the sets of random data, and comparing the hashes.
Claims21
A method of securely comparing a first document in possession of a first party and a second document in possession of a second party, without revealing the contents of the first document to the second party or the contents of the second document to the first party, said method comprising the steps of:
- i) said first and second parties each generating its own set of random data;
- ii) each party exchanging said set of random data and a shared hash function with the other party;
- iii) each party computing a first value consisting of the output of said shared hash function where the input to the hash function is the consecutive concatenation of the document in each said party's possession, followed by that party's set of random data, followed by the other party's set of random data;
- iv) each party computing a second value consisting of the output of said shared hash function where the input to the hash function is the consecutive concatenation of the document in each said party's possession, followed by the other party's set of random data, followed by that party's set of random data;
- v) each party sending its first value to the other party and receiving the other party's first value;
- and
- vi) each party comparing said other party's first value to its second value;
- vii) each party concluding that if the said values are the same, then the two documents are the same, but that otherwise said two documents are different.
A computer program product for securely comparing a first document in possession of a first party and a second document in possession of a second party, without revealing the contents of the first document to the second party said computer program product comprising:
- a computer usable medium having computer readable program code means embodied in said medium for:
- i) generating a set of random data for said first party;
- ii) exchanging said set of random data and a shared hash function with the other party;
- iii) computing a first value consisting of the output of said shared hash function where the input to the hash function is the consecutive concatenation of the document in each said party's possession, followed by that party's set of random data, followed by the other party's set of random data;
- iv) computing a second value consisting of the output of said shared hash function where the input to the hash function is the consecutive concatenation of the document in each said party's possession, followed by the other party's set of random data, followed by that party's set of random data;
- v) sending said first value to the other party and receiving the other party's first value;
- and
- vi) comparing said other party's first value consisting of the output of said shared hash function where the input to the hash function is the consecutive concatenation of the document in said other party's possession, followed by said set of random data, followed by the other party's set of random data, to its second value;
- vii) concluding that if the said values are the same, then the two documents are the same, but that otherwise said two documents are different.
An article comprising:
- a computer readable modulated carrier signal;
- means embedded in said signal for securely comparing a first document in possession of a first party and a second document in possession of a second party, without revealing the contents of the first document to the second party by:
- i) generating a set of random data for said first party;
- ii) exchanging said set of random data and a shared hash function with the other party;
- iii) computing a first value consisting of the output of said shared hash function where the input to the hash function is the consecutive concatenation of the document in each said party's possession, followed by that party's set of random data, followed by the other party's set of random data;
- iv) computing a second value consisting of the output of said shared hash function where the input to the hash function is the consecutive concatenation of the document in each said party's possession, followed by the other party's set of random data, followed by that party's set of random data;
- v) sending said first value to the other party and receiving the other party's first value;
- and
- vi) comparing said other party's first value consisting of the output of said shared hash function where the input to the hash function is the consecutive concatenation of the document in said other party's possession, followed by said set of random data, followed by the other party's set of random data, to its second value;
- vii) concluding that if the said values are the same, then the two documents are the same, but that otherwise said two documents are different.
Dependencies are inferred from the claim text.