Commitment scheme

From CRYPTUTOR

A commitment scheme is a cryptographic implementation of a locked box which can later be opened, and its contents revealed.

[edit]

Definition

A commitment scheme is a 2-party protocol with two phases:

Commit phase: The sender fixes a message $x$ , and the two engage in a protocol. The receiver obtains some commitment information $C$ .
Reveal phase: The sender sends $x$ along with some decommitment information $D$ . The receiver checks that these quantities are consistent with $C$ , and if so, accepts $x$ as the decommitted value.

The security properties required are called the binding and hiding properties of the scheme:

Binding: (security for the receiver) The commit phase determines a unique message $x$ . I.e, after the commit phase, a malicious sender can only successfully reveal a single value.
Hiding: (security for the sender) A malicious receiver cannot distinguish between commitments of two different messages.

We can consider statistical or computational versions of these two properties, depending on whether malicious senders and receivers are allowed to be unbounded or PPT, respectively.

[edit]

Example application

Suppose Alice wants to convince Bob that she can predict stock market prices, so that he will pay a lot of money to buy her insider tips. She can do this by first committing her prediction ("up" or "down") to Bob at the beginning of the day. Then after the market closes, she can reveal the prediction to him. Bob can be assured that Alice's prediction was determined before the stock market moved. Alice can be assured that Bob didn't learn her prediction until the end of the day (so he can't use it to make any money).

[edit]

Existence

A simple commitment scheme for single-bit messages can be built using any one-way function $f$ with a hard-core bit $B$ .

Commit phase: To commit to a bit $b$ , the sender chooses a random string $r$ and sends the pair $(f(r), b \oplus B(r))$ as the commitment information.
Reveal phase: To reveal, the sender tells the receiver $b$ and $r$ . The receiver verifies that the commitment information is consistent with these values.