Chapter status: ✅ in good shape ✅

Related puzzles: Puzzle 1

TODO:

Commitment Schemes

This section contains a brief introduction to commitment schemes, focusing on Pedersen commitments.

Contents

• Generalities
  • Syntax
  • Security
  • Homomorphic Commitments
• Pedersen Commitments
  • Description and Security
  • A Note About the Setup
  • Variants
• ElGamal Commitments
• Commitments and Hash Functions
• Further Resources

Generalities

A commitment scheme involves two parties, a committer (or prover) and a verifier. It allows the committer to send to the verifier a commitment $C$ to some secret value $m$ and later on to open this commitment to reveal $m.$ The commitment $C$ should not reveal any information about the message $m$ (hiding property) and the committer should not be able to open a commitment in two distinct ways (binding property).

For a physical analogy, imagine the committer as writing the message $m$ on a piece of paper and placing it in an opaque, unbreakable, locked box which he sends to the verifier. At this point, the verifier cannot learn anything about the message and the committer cannot modify the message. Later, when the committer wants to open the commitment, he sends the key opening the box to the verifier to reveal the message.

Syntax

More formally, a commitment scheme consists of three algorithms (the exact syntax can vary slightly in the literature):

• a probabilistic setup algorithm $\mathsf{Setup}$ which on input the security parameter $1^{\lambda }$ returns public parameters¹ $par$ which in particular specify a message space ${\mathcal{M}}_{par}$ (in the following, we simply denote the message space $\mathcal{M},$ leaving the dependency on $par$ implicit);
• a probabilistic commitment algorithm $\mathsf{Commit}$ which on input parameters $par$ and a message $m\in \mathcal{M}$ returns a commitment $C$ and a decommitment² $D;$
• a deterministic verification algorithm $\mathsf{Verif}$ which on input parameters $par,$ a commitment $C,$ a message $m\in \mathcal{M},$ and a decommitment $D,$ return 1 if the decommitment is valid for $(par,C,m)$ and 0 otherwise.

Quite often, the decommitment $D$ simply consists of the random coins $r$ used by the commitment algorithm, and the verification algorithm simply recomputes the commitment given $m$ and $r$ and compares with $C.$ When this is the case, we say that the commitment scheme has canonical verification and, overloading the notation, we let $\mathsf{Commit}(par,m;r)$ denote the function explicitly taking the random coins $r$ of the commitment algorithm as input and returning the commitment $C$ (letting the decommitment $D=r$ implicit in that case).

Note that what we just defined here is the syntax for a non-interactive commitment scheme, where the $\mathsf{Setup}$ algorithm is run once and for all and committing consists of a single message sent by the prover to the verifier. There exists more complex commitment schemes where committing requires some interaction between the prover and the verifier.

Correctness requires that for every security parameter $\lambda ,$ the following game capturing the nominal execution of algorithms returns true with probability 1:

$$\boxed{\begin{array}{rl}& par\leftarrow \mathsf{Setup}(1^{\lambda })\\ & m{\leftarrow }_{\$}\mathcal{M}\\ & (C,D)\leftarrow \mathsf{Commit}(par,m)\\ & b\leftarrow \mathsf{Verif}(par,C,m,D)\\ & \mathbf{assert}(b=1)\end{array}}$$

Security

A commitment scheme should satisfy two security properties informally defined as follows:

• hiding: the commitment $C$ should not reveal any information about the secret value $m$ to the verifier,
• binding: the committer should not be able to open the commitment in two different ways.

Let us formalize these two properties more precisely, starting with hiding, defined by the following game:

$$\boxed{\begin{array}{ll}\begin{array}{l}\text{Game HIDING:}\\ b{\leftarrow }_{\$}\{0,1\}\\ par\leftarrow \mathsf{Setup}(1^{\lambda })\\ b^{\prime }\leftarrow {\mathsf{A}}^{\text{Commit}}(par)\\ \mathbf{assert}(b=b^{\prime })\end{array}& \begin{array}{l}\text{Oracle Commit(m0,m1):}\\ \mathbf{assert}(m_0\in \mathcal{M})\\ \mathbf{assert}(m_1\in \mathcal{M})\\ (C,D)\leftarrow \mathsf{Commit}(par,m_b)\\ \mathbf{return}C\end{array}\end{array}}$$

In some cases, it might be necessary to check additional conditions and messages $m_0$ and $m_1$ queried to oracle $\text{Commit}$ (e.g., when $\mathcal{M}$ consists of bit strings of various lengths and $\mathsf{Commit}$ does not hide the message length, $m_0$ and $m_1$ should have the same length).

Binding is defined by the following game:

$$\boxed{\begin{array}{lc}\text{Game BINDING:}& \\ par\leftarrow \mathsf{Setup}(1^{\lambda })& \\ (C,m,D,m^{\prime },D^{\prime })\leftarrow \mathsf{A}(par)& \\ b\leftarrow \mathsf{Verif}(par,C,m,D)& \\ b^{\prime }\leftarrow \mathsf{Verif}(par,C,m^{\prime },D^{\prime })& \\ \mathbf{assert}(m\ne m^{\prime })& \\ \mathbf{assert}(b=1)& \\ \mathbf{assert}(b^{\prime }=1)& \end{array}}$$

For some commitment schemes, one of these two properties holds statistically (i.e., cannot be broken with non-negligible advantage even by a computationally unbounded adversary) or even perfectly. However, a commitment scheme cannot be both statistically hiding and statistically binding at the same time. Hence, at best, a commitment scheme can be either statistically hiding and computationally binding or computationally hiding and statistically binding.

Homomorphic Commitments

Informally, a commitment scheme is homomorphic if the message space $\mathcal{M}$ equipped with some binary operation $\star$ forms a group and given two commitments $C_1$ and $C_2$ to respectively $m_1$ and $m_2,$ anyone can compute a commitment $C$ that the committer can open to $m_1\star m_2.$

More formally, a commitment scheme is homomorphic (with respect to group operation $\star )$ if there exists two algorithms $\mathsf{HomCom}$ and $\mathsf{HomDecom}$ such that

• $\mathsf{HomCom}$ takes parameters $par$ and two commitments $C_1$ and $C_2$ and returns a commitment $C;$
• $\mathsf{HomDecom}$ takes parameters $par$ and two decommitments $D_1$ and $D_2$ and returns a decommitment $D;$
• for any security parameter $\lambda ,$ the following game returns true with probability 1: $$\boxed{\begin{array}{rl}& par\leftarrow \mathsf{Setup}(1^{\lambda })\\ & m_1,m_2{\leftarrow }_{\$}\mathcal{M}\\ & (C_1,D_1)\leftarrow \mathsf{Commit}(par,m_1)\\ & (C_2,D_2)\leftarrow \mathsf{Commit}(par,m_2)\\ & C\leftarrow \mathsf{HomCom}(par,C_1,C_2)\\ & D\leftarrow \mathsf{HomDecom}(par,D_1,D_2)\\ & b\leftarrow \mathsf{Verif}(par,C,m_1\star m_2,D)\\ & \mathbf{assert}(b=1)\end{array}}$$

Algorithms $\mathsf{HomCom}$ and $\mathsf{HomDecom}$ are often quite simple (e.g., when the commitment and decommitment spaces also have a group structure, they simply consist in applying the corresponding group operation to $C_1$ and $C_2$ or $D_1$ and $D_2$ respectively).

Pedersen Commitments

Description and Security

The Pedersen commitment scheme, initially introduced in [Ped91], is widely used, in particular to build zero-knowledge proof systems. It is specified as follows. Let $\mathsf{GroupSetup}$ be a group setup algorithm. Then:

• the setup algorithm $\mathsf{Setup},$ on input $1^{\lambda },$ runs $(\mathbb{G},p)\leftarrow \mathsf{GroupSetup}(1^{\lambda }),$ draws two random generators $G$ and $H$ of $\mathbb{G},$ and returns parameters $par=(\mathbb{G},p,G,H);$ the message space is $\mathcal{M}={\mathbb{Z}}_p;$

• the commitment algorithm $\mathsf{Commit},$ on input parameters $par=(\mathbb{G},p,G,H)$ and a message $m\in {\mathbb{Z}}_p,$ draws $r{\leftarrow }_{\$}{\mathbb{Z}}_p$ and returns a commitment $C=mG+rH$ and a decommitment $D=r;$

• the verification algorithm $\mathsf{Verif},$ on input parameters $par=(\mathbb{G},p,G,H),$ a commitment $C\in \mathbb{G},$ a message $m\in {\mathbb{Z}}_p,$ and a decommitment $D=r\in {\mathbb{Z}}_p,$ returns 1 if $mG+rH=C$ and 0 otherwise.

Theorem 18.1. The Pedersen commitment scheme is perfectly hiding, computationally binding under the discrete logarithm assumption, and homomorphic with respect to addition over ${\mathbb{Z}}_p.$

Proof

Let us sketch the proof of each property:

• perfectly hiding: as $r$ is uniformly random in ${\mathbb{Z}}_p,$ for any message $m,$ $C$ is uniformly random in $\mathbb{G}$ and hence does not reveal any information about $m;$
• computationally binding: assume an adversary can output two message/decommitment pairs $(m,r)$ and $(m^{\prime },r^{\prime })$ with $m\ne m^{\prime }$ for the same commitment $C;$ then $$(m-m^{\prime })G=(r^{\prime }-r)H,$$ which yields the discrete logarithm of $H$ in base $G$ (note that $m-m^{\prime }\ne 0$ implies $r^{\prime }-r\ne 0$ as $G$ and $H$ are generators of $\mathbb{G});$
• additively homomorphic: given two commitments $C_1=m_{1}G+r_{1}H$ and $C_2=m_{2}G+r_{2}H,$ anyone can compute $C:=C_1+C_2=(m_1+m_2)G+(r_1+r_2)H,$ and the committer can compute $r_1+r_2$ which is a valid decommitment for $C$ and message $m_1+m_2.$

A Note About the Setup

Importantly, the setup algorithm should ensure that nobody knows the discrete logarithm of $H$ in base $G.$ In particular, it is not safe to allow the committer to choose the public parameters: if the committer knows the discrete logarithm of $H$ in base $G,$ then the scheme is not binding anymore. Say the committer knows $h$ such that $H=hG.$ Then it can send $C=cG$ as commitment; later, it can open this commitment to any value $m\in {\mathbb{Z}}_p$ it wants by computing $r=h^{-1}(c-m)\mathrm{mod}p$ and sending decommitment $D=(m,r):$ it satisfies $mG+rH=(m+rh)G=cG=C.$

For this reason, Pedersen's scheme is sometimes referred to as a trapdoor (or equivocal) commitment scheme, which can be useful in security proofs but should also make us wary. However, there are secure ways to select the commitment key without a trusted third party, such as using a hash-to-group function (a.k.a. hash-to-curve function in case $\mathbb{G}$ is based on an elliptic curve) applied to some NUMS (nothing-up-my-sleeve) input. Hence, even though Pedersen commitments do not require a trusted setup, one should always verify that parameters were correctly generated. For a real-world example where this trapdoor property could have been used, see Section VI of [HLPT20] about the Scytl/SwissPost e-voting system.

Variants

The Pedersen commitment scheme can be generalized to messages which are vectors $\mathbf{m}=(m_0,\dots ,m_{n-1})\in ({\mathbb{Z}}_p{)}^n:$ the parameters are extended to $par=(\mathbb{G},p,G_0,\dots ,G_{n-1},H)$ where $G_0,\dots ,G_{n-1},$ and $H$ are uniformly random and independent generators of $\mathbb{G},$ and the commitment for message $\mathbf{m}=(m_0,\dots ,m_{n-1})$ with randomness $r$ is $$C:=\sum _{i=0}^{n-1}{m}_i{G}_i+rH.$$ This is usually called the generalized Pedersen commitment scheme, or sometimes the Pedersen vector commitment scheme, although this is somehow a misnomer as it does not have all the properties required from a vector commitment scheme [CF13]. As for the basic variant, it can be shown to be perfectly hiding, computationally binding under the DL assumption, and homomorphic with respect to addition over $({\mathbb{Z}}_p{)}^n.$

The "random" part of the commitment $rH$ is sometimes omitted, in which case the commitment algorithm becomes deterministic and the commitment is simply $$C:=\sum _{i=0}^{n-1}{m}_i{G}_i.$$ In that case, the scheme is still computationally binding under the DL assumption (and even perfectly binding for $n=1$ as the commitment function is bijective), but it is not hiding anymore (given two messages ${\mathbf{m}}_0$ and ${\mathbf{m}}_1$ and a commitment $C$ to ${\mathbf{m}}_b$ for some random bit $b,$ one can recover $b$ by simply computing the commitments corresponding to respectively ${\mathbf{m}}_0$ and ${\mathbf{m}}_1$ and comparing with $C).$ For this reason, it is sometimes referred to as the non-hiding Pedersen commitment scheme. It is however preimage-resistant under the DL assumption, meaning that given a random commitment $C\in \mathbb{G},$ it is hard to compute a message $\mathbf{m}$ such that $\mathsf{Commit}(par,\mathbf{m})=C.$

ElGamal Commitments

The Pedersen commitments scheme has a relative known as the ElGamal commitment scheme where the commitment key $ck$ is $(\mathbb{G},p,G,H)$ as for Pedersen and the commitment for message $m\in {\mathbb{Z}}_p$ with randomness $r{\leftarrow }_{\$}{\mathbb{Z}}_p$ is the pair $(C_1,C_2)=(rG,mG+rH).$ (Note the similarity with ElGamal encryption w.r.t. public key $H.$) This scheme is perfectly binding, computationally hiding under the DDH assumption, and additively homomorphic.

If the message is encoded as a group element $M\in \mathbb{G}$ and the commitment computed as $(C_1,C_2)=(rG,M+rH),$ the scheme has a trapdoor property allowing anyone with knowledge of the discrete logarithm $h$ of $H$ in base $G$ to extract the message $M$ (by "decrypting" the commitment as in ElGamal encryption, i.e., computing $M=C_2-h{C}_1).$

Commitments and Hash Functions

There is a strong connection between commitment schemes and collision-resistant hash functions.

First, let us consider the following strengthening of the binding property: We say that a commitment scheme if strongly binding if it is hard to find a commitment $C$ and two distinct message-decommitment pairs $(m,D)$ and $(m^{\prime },D^{\prime })$ such that $\mathsf{Verif}(par,C,m,D)=1$ and $\mathsf{Verif}(par,C,m^{\prime },D^{\prime })=1.$ That is, the adversary wins also when the messages $m$ and $m^{\prime }$ are equal but the decommitments $D$ and $D^{\prime }$ are different.

Given a hash function family $H_{par}:\{0,1{\}}^{\ast }\to \{0,1{\}}^{2\lambda }$ indexed by some parameter $par,$ one can define a simple commitment scheme with $$\mathsf{Commit}(par,m;r):=H_{par}(m\Vert r)$$ where $r{\leftarrow }_{\$}\{0,1{\}}^{\lambda }.$ It can be shown to be (computationally) strongly binding assuming the family $(H_{par})$ is collision-resistant. On the other hand, there is no reason for this scheme to be hiding in general ($H$ could for example reveal the first bit of the message, allowing to distinguish commitments to two messages with distinct first bits). It is however easily seen to be (computationally) hiding in the random oracle model.

Reciprocally, it is straightforward to derive a collision-resistant hash function family from a strongly binding commitment scheme.

Proposition 18.1. Consider a commitment scheme $\Pi$ with a $\mathsf{Commit}$ function taking parameters $par,$ a message $m\in \mathcal{M},$ and explicit random coins $r\in \mathcal{R}.$ If $\Pi$ is strongly binding, then the function family $$H_{par}:(m,r)\mapsto \mathsf{Commit}(par,m;r)$$ is collision-resistant.

Proof

Assume that $H$ is not collision-resistant and that there is an adversary which on input $par$ returns $(m,r)\ne (m^{\prime },r^{\prime })$ such that $H_{par}(m,r)=H_{par}(m^{\prime },r^{\prime }).$ Let $C:=H_{par}(m,r)=H_{par}(m^{\prime },r^{\prime }).$ Then $\mathsf{Verif}(par,C,m,r)=\mathsf{Verif}(par,C,m^{\prime },r^{\prime })=1,$ hence this adversary can be used to break strong binding of $\Pi .$

Note that the assumption that $\Pi$ is binding is not sufficient: it could be easy to find $(m,r)\ne (m^{\prime },r^{\prime })$ such that $\mathsf{Commit}(par,m;r)=\mathsf{Commit}(par,m^{\prime };r^{\prime })$ but with $m=m^{\prime },$ which would break collision-resistance but not binding.

It is not hard to see that the Pedersen commitment scheme is actually strongly binding, which directly gives an algebraic family of collision-resistant hash functions usually called Pedersen hashing. A specific instance of the family is specified by a tuple of parameters $par=(\mathbb{G},p,G_0,\dots ,G_{n-1})$ where $n\ge 2,$ $\mathbb{G}$ is a cyclic group of order $p,$ and $G_0,\dots ,G_{n-1}$ are generators chosen in a way such that nobody knows any discrete logarithm relation between them. Then $H_{par}$ has domain $({\mathbb{Z}}_p{)}^n,$ range $\mathbb{G},$ and is defined by $$H_{par}(m_0,\dots ,m_{n-1})=\sum _{i=0}^{n-1}{m}_i{G}_i.$$ (Note that in the context of hashing, there is no distinction between the "message" and the "randomness" as in the context of commitment schemes.)

This family of hash functions is collision-resistant assuming the discrete logarithm problem is hard.

Variants are possible: for example, if inputs are bit strings of length exactly $L,$ one can split the input $m$ into chunks of $w$ consecutive bits with $2^w\le p$ and $L=nw,$ convert the $i$-th chunk into an integer $m_i,$ and let $H_{par}(m)={\sum }_{i=0}^{n-1}{m}_i{G}_i.$

Further Resources

For more background on commitment schemes, see for example this article by Damgård and Nielsen and this lecture by Dodis.

---

1: The name can vary; these parameters are sometimes called a commitment key or a public key.

2: Again, the name can vary and it is sometimes called an opening or a hint.