Cryptography: Commitment Schemes

UCL Course COMP0143 Cryptocurrencies: Prerequisite Cryptography Part IV

Scenario: Sealed-Bid AuctionsPermalink

Process

• Bidding Stage: Bidders submit their sealed bids.

• Opening Stage: All bids are opened and the highest one wins.

Protection against Cheating

• Bidding Stage: A sealed bid $c_i$ should not leak any information about the bid $b_i$.

• Opening Stage: A bidder should not be able to open its bid to another one $b_i^{\prime }\ne b_i$.

DefinitionPermalink

Commitment Scheme is an interactive protocol between a sender $S$ and a receiver $R$.

ComponentsPermalink

• Commit

  Sender $S$ sends a commitment $c:=\text{Commit}(m,r)$ to receiver $R$
  where $m$ is the message and $r$ is a randomness.

• Reveal

  Sender $S$ reveals $c$ by sending $m$ and $r$ to receiver $R$
  who accepts if $c=\text{Commit}(m,r)$.

Security GoalPermalink

• Hiding

  Receiver $R$ should not be able to obtain any information about $m$ from $c$.

• Binding

  Sender $S$ should not be able to reveal $c$ to any other message $m^{\prime }\ne m$.

Adversary TypesPermalink

• Hiding-Adversary $\mathcal{A}$ (role as Receiver $R$)

  who aims to learn information about $m$ from $c:=\text{Commit}(m,r)$.

• Binding-Adversary $\mathcal{A}$ (role as Sender $S$)

  who aims to find $(m,r)$ and $(m^{\prime },r^{\prime })$ that meets $\text{Commit}(m,r)=\text{Commit}(m^{\prime },r^{\prime })$ and $m\ne m^{\prime }$.

Pedersen CommitmentPermalink

ProtocolPermalink

Let $<\mathbb{G},q,g>$ be a cyclic group where $|\mathbb{G}|=q$
and $g$ is the generator in which the Discrete Logarithm Problem is computationally hard.

Let $h$ be a randomly chosen generator of $\mathbb{G}$ with $g\ne h$
and assume the discrete logarithm $x$ such that $h=g^x$ is unknown.

• Commit

  Sender $S$ chooses $m\in {\mathbb{Z}}_q$ and picks $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_q$.

  Sender $S$ sends commitment $c:=g^m{h}^r$ to receiver $R$.

• Reveal

  Sender $S$ reveals $c$ by sending $m$ and $r$ to receiver $R$ who accepts if $c=g^m{h}^r$.

Hiding Security of Pedersen CommitmentPermalink

The Hiding of Pedersen Commitment provides Perfect Security.

Proof

Assume adversary $\mathcal{A}$ is even information-theoretic (knows $x=lo{g}_{g}h⟹h=g^x$).

Then, the commitment $c:=g^m{h}^r=g^m(g^x{)}^r=g^{m+xr}$.

The value $a=m+xr$ is uniformly distributed in ${\mathcal{Z}}_q$ since $r\stackrel{\$}{\leftarrow }{\mathcal{Z}}_q$.

Then, for any given message $m^{\prime }\in {\mathcal{Z}}_q$, there exists an unique $r^{\prime }\in {\mathcal{Z}}_q$ meets $a=m^{\prime }+x{r}^{\prime }$.

Then, for any message $m^{\prime }$ with $m^{\prime }=m$ or $m^{\prime }\ne m$, there exists $r^{\prime }$ meets $c=g^{m^{\prime }}{h}^{r^{\prime }}$.

Therefore, adversary $\mathcal{A}$ cannot distinguish which message is hidden in $c$.

Binding Security of of Pedersen CommitmentPermalink

The Binding of Pedersen Commitment provides Computational Security

Proof

By Contradiction and Reduction

Assume Pedersen commitment scheme does not provide computationally secure binding
when the Discrete Logarithm Problem is computationally hard.

Let $\mathcal{A}$ be a PPT adversary which breaks the binding property.

Let $\mathcal{B}$ be a PPT adversary against Discrete Logarithm Problem that simulates Pedersen Commitment for $\mathcal{A}$.

• $\mathcal{A}$ requests a new commitment from $\mathcal{B}$

  such that $\mathcal{B}$ chooses $m\in {\mathcal{Z}}_q$, picks $r\stackrel{\$}{\leftarrow }{\mathcal{Z}}_q$, and returns $c=g^m{h}^r$ to $\mathcal{A}$.

• $\mathcal{A}$ requests to de-commit $c$ from $\mathcal{B}$

  such that $\mathcal{B}$ sends $(m,r)$ to $\mathcal{B}$.

• According to the assumption of $\mathcal{A}$’s capability,

  $\mathcal{A}$ can return $(m,r)$ and $(m^{\prime },r^{\prime })$ to $\mathcal{B}$ and break binding successfully,

  which means that $c=g^m{h}^r=g^{m^{\prime }}{h}^{r^{\prime }}=c^{\prime }$,

  which means that $m+xr\equiv m^{\prime }+x{r}^{\prime }(modp)$ when $h=g^x$,

  which means that $x\equiv (m-m^{\prime })\cdot (r^{\prime }-r{)}^{-1}(modp)$,

  which means $\mathcal{B}$ can get $x$ to break DLP (Given $h$ and $g$ to get $x$ when $h=g^x$).

Note: the Pedersen Commitment cannot provides perfectly secure binding since DLP is only computationally hard.

CRHF-based Commitment SchemesPermalink

Let $H$ be a Collision Resistant Hash Function (CRHF)
in the Random Oracle Model (ROM) accepting arbitrary size inputs.

• Commit

  Sender $S$ chooses $m\in \{0,1{\}}^{\ast }$ and picks $r\stackrel{\$}{\leftarrow }\{0,1{\}}^n$.

  Sender $S$ sends commitment $c:=H(m||r)$ to receiver $R$.

  Note: $n$ should be large enough to defend brute force attacks.

• Reveal

  Sender $S$ reveals $c$ by sending $m$ and $r$ to receiver $R$ who accepts if $c=H(m||r)$.

The hiding of CRHF-based Commitment provide
Computational Security since an adversary queries $H(\ast \parallel r)$ only with negligible probability.

The binding of CRHF-based Commitment provide
Computational Security since $H$ is collision-resistant.

Merkle trees allow to commit efficiently to large sets of values and are very often used in practice (e.g., Blockchain).

Application: Coin Flip ProtocolPermalink

Alice and Bob want to agree remotely on a random bit $b$
which needs a function with joint inputs from Alice and Bob,
such that neither Alice and Bob can bias/control the result of $b$.

Let $b_A$ be the function result of Alice, and $b_B$ be the function result of Bob.

We say that the Coin Flip protocol is correct if $b_A=b_B$.

Strawman Implementation in Coin Flip Protocol

Alice chooses $b_A\stackrel{\$}{\leftarrow }\{0,1\}$ and Bob $b_B\stackrel{\$}{\leftarrow }\{0,1\}$, then both compute $b=b_A\oplus b_B$.

However, this Coin Flip Protocol is insecure:

1. Bob waits until it receive $b_A$

2. Bob then picks a wanted result $b^{\prime }$ and replies $b_B=b_A\oplus b^{\prime }$ to Alice

3. Both Alice and Bob will output $b^{\prime }$

Commitment-based Implementation in Coin Flip Protocol

Process

1. Alice chooses $b_A\stackrel{\$}{\leftarrow }\{0,1\}$ and $r\stackrel{\$}{\leftarrow }\{0,1{\}}^n$

2. Alice sends the commitment $c:=\text{Commit}(b_A,r)$ to Bob

3. Bob chooses $b_B\stackrel{\$}{\leftarrow }\{0,1\}$

4. Bob sends the $b_B$ to Alice

5. Alice reveals $c$ by sending pair $(b_A,r)$ to Bob, then computes $b=b_A\oplus b_B$

6. Bob accepts if $c=\text{Commit}(b_A,r)$ (reject otherwise), then computes $b=b_A\oplus b_B$

Security

• If the receiver is dishonest (Bob is the adversary $\mathcal{B}$)

  and if $\mathcal{B}$ can distinguish $b_A=0$ and $b_A=1$

  then, $\mathcal{B}$ can break the hiding security of commitment scheme.

• If the sender is dishonest (Alice is the adversary $\mathcal{A}$)

  and if $\mathcal{A}$ can prepare $c$ and valid pair $(b_A,r)$ for both $b_A=0$ and $b_A=1$

  then, $\mathcal{A}$ can break the binding security of commitment scheme.

Problem

When the sender (Alice) receives the reply from the receiver (Bob), Alice can compute $b=b_A\oplus b_B$.

If $b$ is not the result Alice wants, Alice can choose not to reveal $c$ to Bob, then Alice can abort the protocol as she wants.

The possible solution is to use Secret Sharing Schemes.

Application: Sealed-Bid AuctionsPermalink

• Bidding Stage

  Each bidder $B_i$ chooses a bid $b_i$, picks a randomness $r_i$, and publishes $c_i=\text{Commit}(b_i,r_i)$.

  Since commitment schemes are hiding, $c_i$ does not leak any information about $b_i$.

• Opening Stage

  Bidder $B_i$ reveals $c_i$ by receiving $b_i$ and $r_i$.

  Since commitment schemes are binding, $B_i$ cannot change its bid to $b_i^{\prime }\ne b_i$ after $c_i$ has been published.

• Evaluation Stage

  The highest bid $b=max(b_i)$ wins.