Pedersen commitments

A Pedersen commitment is a commitment scheme (see what a commitment scheme is if you haven’t read that yet) built directly out of group arithmetic instead of a hash function. That choice buys two things a hash commitment can’t give you: perfect hiding, and a homomorphic property that lets you add committed values without opening them.

It’s named for Torben P. Pedersen, who introduced the construction in “Non- Interactive and Information-Theoretic Secure Verifiable Secret Sharing,” presented at CRYPTO ‘91 (Santa Barbara, August 11–15, 1991), published in Lecture Notes in Computer Science vol. 576, pp. 129–140 (Springer). In that paper the commitment wasn’t the end goal — it was one piece of a verifiable secret-sharing protocol, where a dealer splits a secret into shares such that each participant can check their own share is consistent without talking to anyone else, and any k of n participants can later reconstruct the secret while fewer than k learn nothing about it at all, in the strict Shannon-information sense. The commitment construction inside that protocol turned out to be useful on its own, and today it’s usually studied and deployed independently of the secret-sharing context it was born in — see History for how it sits in the broader zero- knowledge timeline, before and after 1991.

The construction

You need a group in which the discrete logarithm problem is believed to be hard: given two elements $g$ and $h$ of the group, finding the exponent $x$ such that $h = g^x$ should be computationally infeasible. Two versions of this are in common use.

Classic version (multiplicative group mod p, as in the 1991 paper)

• $p$ is a large prime, $q$ a large prime dividing $p - 1$.
• $g$ and $h$ are generators of the subgroup of order $q$ inside $\mathbb{Z}_p^*$.
• Critically, nobody knows $\log_g h$ — the exponent $x$ with $h = g^x$. Both parties can trust this if $g$ and $h$ were generated by a public, nothing-up-my- sleeve procedure (for example, hashing a fixed string into the group) rather than chosen by anyone who might have picked $h = g^x$ for a known $x$.

To commit to a message $m \in \mathbb{Z}_q$:

$$\text{Commit}(m, r) = g^m \, h^r \bmod p, \qquad r \xleftarrow{\$} \mathbb{Z}_q$$

To open, reveal $(m, r)$; the verifier recomputes $g^m h^r \bmod p$ and checks it matches the commitment $C$. The live demo on the homepage runs exactly this formula, over a 2048-bit safe-prime group.

Modern version (elliptic curve)

The same idea, written additively in an elliptic-curve group instead of a multiplicative group mod $p$ — this is the form you’ll see in most current cryptographic protocols and libraries:

$$\text{Commit}(m, r) = m G + r H$$

where $G$ is the curve’s standard base point, and $H$ is a second point with no known discrete log relative to $G$ — again produced via a public hash-to-curve procedure rather than picked out of a hat.

Why hiding is information-theoretic

This is the property that makes Pedersen commitments strictly stronger than a hash commitment, and the argument is short: $r$ is drawn uniformly at random from $\mathbb{Z}_q$, and $h$ generates the entire order-$q$ subgroup. That means $h^r$ is itself uniformly distributed over that whole subgroup — every element is equally likely. Multiplying by any fixed $g^m$ is just a relabeling (a bijection on the subgroup), so $C = g^m h^r$ is exactly uniformly distributed over the subgroup, for every possible value of $m$.

Two different messages $m$ and $m'$ therefore produce commitments with identical probability distributions. No amount of computing power lets an observer distinguish which message produced a given $C$, because $C$ genuinely carries zero information about $m$ — not “effectively zero,” but zero in the same sense a one-time pad carries zero information about its plaintext. That’s what “information-theoretic” (or “unconditional,” or “perfect”) hiding means: the guarantee holds against an attacker with unbounded computation, not just a computationally limited one.

Why binding is only computational

Binding is the flip side, and it can’t also be unconditional — see the trade-off discussed on the commitment scheme page. Here’s exactly what breaking it would require.

Suppose someone finds two different openings of the same commitment: $(m, r)$ and $(m', r')$ with $m \ne m'$, both satisfying $g^m h^r \equiv g^{m'} h^{r'} \pmod p$. Rearranging:

$$g^{m - m'} \equiv h^{r' - r} \pmod p$$

If $r' = r$, this forces $g^{m-m'} \equiv 1$, which (since $g$ has order $q$) means $m \equiv m' \pmod q$ — contradicting $m \ne m'$. So $r' \ne r$, which means $r' - r$ is invertible mod $q$, and we can solve directly for the discrete log of $h$ base $g$:

$$x = \log_g h = (m - m') \cdot (r' - r)^{-1} \bmod q$$

In other words: anyone who can break binding has just computed $\log_g h$. Binding is therefore exactly as hard as the discrete logarithm problem in this group. Since $g$ and $h$ were generated with no known relation between them (see above), this reduces to a problem believed to be hard — but that belief is a computational assumption, not a mathematical certainty. If discrete log in this group ever becomes tractable (a sufficiently large quantum computer, say), binding breaks. Hiding wouldn’t be affected at all.

Try the binding sandbox to find such a collision by hand, on a toy-sized group small enough to brute-force — it makes concrete why this isn’t just “hard” in some vague sense.

The homomorphic property

Multiply two commitments together and you get a valid commitment to the sum of the underlying messages, with the randomness also summed:

$$\text{Commit}(m_1, r_1) \cdot \text{Commit}(m_2, r_2) = g^{m_1} h^{r_1} \cdot g^{m_2} h^{r_2} = g^{m_1 + m_2} h^{r_1 + r_2} = \text{Commit}(m_1 + m_2,\; r_1 + r_2)$$

Nobody needs to open either commitment for this to work — it’s pure group arithmetic. This is the property confidential transactions and range proofs are built on: a system can verify that committed inputs sum to committed outputs — proving no value was created or destroyed — without ever learning what any individual amount was.

---

Sources: T. P. Pedersen, “Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing,” CRYPTO ‘91, LNCS vol. 576, pp. 129–140, Springer, 1991.