Method and system for non-malleable and non-interactive cryptographic commitment in a network

• US 6,301,664 B1
• Filed: 11/18/1998
• Issued: 10/09/2001
• Est. Priority Date: 11/18/1997
• Status: Expired due to Term

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Inventors: Ostrovsky, Rafail, Ishai, Yuval, Di-Crescenzo, Giovanni
• Primary Examiner(s): Peeso, Thomas R.
• Application Number:
  US09/195,491
• Time in Patent Office: 1,056 Days
• Field of Search: 713/165, 713/166, 713/168, 713/189, 713/200, 713/201
• US Class Current: 713/189
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs

Abstract

A method and system perform non-malleable and non-interactive commitment of data, which is communicated by a sender to a receiver. At a commitment phase, the sender selects a first string having a first portion and a second portion, and based on the first portion of the first string, establishes a first commitment to an authentication key. The sender divides the second portion of the first string into a set of segments each including two or more sub-segments, and based on the first commitment, selects one of the subsegments in each of the segments. The sender combines the selected sub-segments together, and establishes a second commitment to the data based on the combined selected sub-segments such that the second commitment is equivocable. The sender authenticates the second commitment by using the authenticating key. At a de-commitment phase, the sender de-commits the data and the authentication key.

Claims

1. A method for non-malleable commitment to data communicated by a sender to a receiver, said method comprising the steps of:

selecting a first string having a first portion and a second portion;

establishing, based on the first portion of the first string, a first commitment to an authentication key;

dividing the second portion of the first string into a set of segments each including two or more sub-segments;

selecting, based on the first commitment, one of the sub-segments in each of the segments, and combining the selected sub-segments together;

establishing a second commitment to the data based on the combined selected sub-segments such that the second commitment is equivocable; and

authenticating the second commitment using the authenticating key.

2. The method of claim 1, wherein the step of selecting the first string comprises the step of randomly selecting the first string.

3. The method of claim 1, wherein the step of establishing the first commitment comprises the steps of:

generating a second string based on a random seed;

encoding the authentication key;

building a first commitment message that includes for each 0 bit in the first portion of the first string a corresponding first bit in the second string and that includes for each 1 bit in the first portion of the first string a corresponding second bit, wherein the corresponding second bit is determined by performing a bitwise exclusive OR operation on a corresponding third bit in the second string and a corresponding fourth bit in the encoded authentication key.

4. The method of claim 1, wherein the combining step comprises the step of performing a bitwise exclusive OR operation on the selected sub-segments.

5. The method of claim 1, wherein the step of establishing the second commitment comprises the steps of:

building a second commitment message that is computationally indistinguishable from a third commitment message.

6. The method of claim 1, wherein the authenticating step comprises the steps of:

generating, based on the authentication key, a second string having a first portion and a second portion;

multiplying the second commitment with the first portion of the second string; and

adding result of the multiplying step to the second portion of the second string.

7. The method of claim 1 further comprising the step of:

establishing a de-commitment for the data.

8. The method of claim 5, wherein the step of building the second commitment message comprises the steps of:

generating a second string based on a random seed; and

including in the second commitment message the second string for each 0 bit in the data; and

including in the second commitment message a third string for each 1 bit in the data, wherein the third string is determined by performing a bitwise exclusive OR operation on the second string and the combined selected sub-segments.

9. The method of claim 7, wherein the step of establishing the de-commitment comprises the step of:

sending to the receiver the authentication key and the data.

10. A computer-readable medium capable of configuring a sender to perform a method for non-malleable commitment to data communicated by the sender to a receiver, said method comprising the steps of:

selecting a first string having a first portion and a second portion;

establishing, based on the first portion of the first string, a first commitment to an authentication key;

dividing the second portion of the first string into a set of segments each including two or more sub-segments;

selecting, based on the first commitment, one of the sub-segments in each of the segments, and combining the selected sub-segments together;

establishing a second commitment to the data based on the combined selected sub-segments such that the second commitment is equivocable; and

authenticating the second commitment using the authenticating key.