Endong Liu

Stay Hungry, Stay Foolish

7 minute read

UCL Course COMP0143 Cryptocurrencies: Prerequisite Cryptography Part IV

Scenario: Sealed-Bid Auctions

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^\prime_i \neq b_i\).

Definition

Commitment Scheme is an interactive protocol between a sender \(S\) and a receiver \(R\).

Components

  • 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 Goal

  • 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 \neq m\).

Adversary Types

  • 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 \neq m^\prime\).

Pedersen Commitment

Protocol

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 \neq 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 \xleftarrow{$} \mathbb{Z}_q\).

    Sender \(S\) sends commitment \(c := g^mh^r\) to receiver \(R\).

  • Reveal

    Sender \(S\) reveals \(c\) by sending \(m\) and \(r\) to receiver \(R\) who accepts if \(c = g^mh^r\).

Hiding Security of Pedersen Commitment

The Hiding of Pedersen Commitment provides Perfect Security.

Proof

Assume adversary \(\mathcal{A}\) is even information-theoretic (knows \(x = log_gh \implies h = g^x\)).

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

The value \(a = m + xr\) is uniformly distributed in \(\mathcal{Z}_q\) since \(r \xleftarrow{$} \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 + xr^\prime\).

Then, for any message \(m^\prime\) with \(m^\prime = m\) or \(m^\prime \neq 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 Commitment

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 \xleftarrow{$} \mathcal{Z}_q\), and returns \(c = g^mh^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^mh^r = g^{m^\prime}h^{r^\prime} = c^\prime\),

    which means that \( \ m + xr \equiv m^\prime + xr^\prime \ (mod \ p) \ \) when \(h = g^x\),

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

    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 Schemes

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\}^*\) and picks \(r \xleftarrow{$} \{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( * \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 Protocol

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 \xleftarrow{$} \{0,1\}\) and Bob \(b_B \xleftarrow{$} \{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’\) 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 \xleftarrow{$} \{0,1\}\) and \(r \xleftarrow{$} \{0,1\}^n\)

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

  3. Bob chooses \(b_B \xleftarrow{$} \{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 Auctions

  • 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^\prime_i \neq b_i\) after \(c_i\) has been published.

  • Evaluation Stage

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

You may also enjoy