Commitment scheme

A commitment scheme is a two-phase protocol between a committer and a verifier in which the committer binds to a value during the commit phase (without revealing it), and then reveals the value in the open phase. The binding property ensures the committer cannot change the value after committing; the hiding property ensures the verifier learns nothing about the value before opening.

Syntax

A commitment scheme is a tuple of efficient algorithms $COM = (Gen, \Com, \Open)$ with respect to a message space $M$ , commitment space $C$ , and decommitment space $D$ :

$Gen (1^{λ}) \to pp,$ is a randomized algorithm that outputs public parameters $pp,$
$\Com (pp, m; r) \to (c, d),$ is a randomized algorithm that takes a message $m \in M$ and randomness $r$ , and outputs a commitment $c \in C$ and decommitment string $d \in D,$
$\Open (pp, c, d) \to m or ⊥,$ is a deterministic algorithm that opens a commitment $c$ using decommitment $d$ , returning the message or $⊥$ on failure.

Properties

Correctness

For all $λ \in N$ , $m \in M$ , and $(c, d) \leftarrow \Com (pp, m; r)$ with $r \leftarrow $ {0, 1}^{*}$ , we have $\Open (pp, c, d) = m$ with probability 1.

Hiding

The commitment $c$ reveals no information about $m$ before opening. Computationally:

$Adv_{COM, A}^{hide} (λ) := 2 Pr [G_{COM, A}^{hide} (λ) = 1] - 1$

is negligible, where the game samples $pp \leftarrow Gen (1^{λ})$ , receives $(m_{0}, m_{1})$ from $A$ , picks $b \leftarrow $ {0, 1}$ , sends $(c, d) \leftarrow \Com (pp, m_{b}; r)$ to $A$ , and $A$ outputs $b^{'}$ .

A commitment is statistically hiding if this holds even against computationally unbounded adversaries.

Binding

No efficient committer can open a commitment to two different messages:

$Adv_{COM, A}^{bind} (λ) := Pr [G_{COM, A}^{bind} (λ) = 1]$

is negligible, where the game samples $pp \leftarrow Gen (1^{λ})$ , receives $(c, d_{0}, d_{1})$ from $A$ , and outputs 1 iff $\Open (pp, c, d_{0}) \neq = ⊥$ , $\Open (pp, c, d_{1}) \neq = ⊥$ , and $\Open (pp, c, d_{0}) \neq = \Open (pp, c, d_{1})$ .

A commitment is statistically binding if this holds even against computationally unbounded adversaries.

Note: Perfect (simultaneously statistically hiding and statistically binding) commitment schemes are impossible by a simple entropy argument. The four regimes are: (1) perfectly binding / computationally hiding, (2) computationally binding / statistically hiding, (3) computationally binding / computationally hiding, and (4) perfectly binding / perfectly hiding — which is impossible.

Variations

Trapdoor commitments

A trapdoor commitment (or equivocable commitment) is a commitment scheme with an additional trapdoor $td$ (generated alongside $pp$ ) that allows equivocation: given $td$ , for any commitment $c$ and any two messages $m_{0}, m_{1}$ , one can produce decommitment strings $d_{0}, d_{1}$ with $\Open (pp, c, d_{0}) = m_{0}$ and $\Open (pp, c, d_{1}) = m_{1}$ . Used in zero-knowledge proof constructions.

Vector commitments

A vector commitment allows committing to an ordered vector $(m_{1}, \dots, m_{n})$ such that one can later open any single position $m_{i}$ with a short proof. Used in verifiable data structures and SNARKs.

Other results

COM from PRG (and hence from OWF): Naor’s construction uses a PRG to commit to a single bit in a statistically binding, computationally hiding scheme — Naor91
COM is complete for MPC in the semi-honest model: any two-party functionality can be computed given a commitment scheme — GMW87
OT can be constructed from any non-trivial commitment scheme — Kil88
COM from any CPA-secure PKE scheme: encrypt $m$ under a freshly generated public key; the ciphertext is a statistically binding commitment
Statistically hiding COM is equivalent to SZK $\neq =$ BPP — standard
COM from DDH: the Pedersen commitment scheme is perfectly hiding and computationally binding

Cryptology City

Explorer