# What is a Pedersen commitment?

I couldn't find any answer providing a high-level overview on what Pedersen commitments are or what they are used for.

• Here is a link to Pedersen's paper: link.springer.com/chapter/10.1007/3-540-46766-1_9 Nov 30, 2018 at 13:21
• @kelalaka the beauty in getting an answer on SE is embedded in the amazing ability of users to comprise a lot of information in compact yet still nicely-formatted texts. I could've found what a Petersen commitment is on Wikipedia, but I asked it here (1) because of the aforementioned idea and (2) for others to quickly find the answer after squandering time on a search engine. Dec 3, 2018 at 20:45
• Dec 12, 2018 at 8:22
• I voted to repoen this question because the meta discussion seems to conclude that it is on-topic. Also, experience shows that its answer is popular.
– fgrieu
Nov 25, 2019 at 21:05
• I have reopened the question (as mod) as the Wikipedia article (always a good place to start research) seems to have little info about the scheme. Note however that this question doesn't show any research, which is an explicit reason for closing questions, as stated in our help center. This is not a good example of questions that are on topic. Nov 26, 2019 at 20:02

what Pedersen commitments are

In a commitment scheme such as Pedersen:

1. the committer (or sender) decides (or is given) a secret message $$m$$ taken in some public message space with at least two elements;
2. decides a random secret $$r$$;
3. produces from that $$m$$ and $$r$$ a commitment $$c=\mathcal C(m,r)$$ by applying some public method (the commitment algorithm $$\mathcal C$$) defined by the scheme;
4. makes $$c$$ public;
5. later reveals $$m$$ and $$r$$.
6. The verifier (or receiver) is given $$c$$, $$m$$, $$r$$ and can check if indeed $$\mathcal C(m,r)=c$$. That will always hold if 1/2/3/4/5 are carried out as stated.

Informally, that must not hold in any other case met, including if the committer changes $$m$$ between steps 1 and 5 or chooses $$r$$ maliciously. Further, $$c$$ must give no clue about $$m$$ before step 5.

More formally: an adversaries succeeds if they can exhibit any of the following

• $$m$$, $$m'$$, $$r$$ and $$r'$$ with $$m\ne m'$$ and $$\mathcal C(m,r)=\mathcal C(m',r')$$
• $$m$$ and $$m'$$ with $$m\ne m'$$ and such that, for a random secret choice of $$r$$ and given a randomly chosen value among $$c=\mathcal C(m,r)$$ and $$c'=\mathcal C(m',r)$$, the adversary can decide with probability sizably better than 50% it the given value is $$c$$ or $$c'$$.

Pedersen commitment uses a public group $$(G,\cdot)$$ of large order $$q$$ in which the discrete logarithm is hard, and two random public generators $$g$$ and $$h$$. Random secret $$r$$ is chosen in $$\Bbb Z_q$$, the message $$m$$ is from any subset of that. The commitment is $$\mathcal C(m,r)=g^m\cdot h^r$$.

The reference description is section 3 of Torben Pryds Pedersen's Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, in proceedings of Crypto 1991.

what they are used for

Commitments are the cryptographic equivalent of secretly writing $$m$$ in a sealed, tamper-evident, individually numbered (or/and countersigned) envelope kept by who wrote the message. The envelope's content can't be changed (binding property), and the message can't leak (hiding property). Among improvements brought by cryptography, we do not need to check that the envelope was actually sealed, and things can be done remotely; numbers are aplenty and recyclable. On the other hand, we need computers, and the method will convince only those that trust both math and the computer they use.

An example application is fairly deciding who serves first in a tennis match between Bob and Carol, in a way convincing both of them and Valery (acting as referee). It is agreed that if Bob can guess Carol's choice, Bob serves first; otherwise, Carol does.

Using such envelope, that could be done as:

• Carol secretly decides $$m$$ in $$\{0, 1\}$$, writes it on a paper, puts it the envelope, seals it, shows that to Bob and Valery, but keeps the envelope.
• Bob announces a guess $$m_b$$ in $$\{0, 1\}$$; he and Valery do not know the outcome yet, but Carol does.
• Carol states her choice of $$m$$ and gives the envelope to Valery.
• Valery checks if $$m\ne m_b$$ and (needed only in the affirmative) opens the envelope to check if it does contain a paper with $$m$$ written on it; in which case Carol serves first. Otherwise, Bob does.

Using a commitment, Carol acting as committer and Valery acting as verifier:

• Carol secretly decides $$m$$ in $$\{0, 1\}$$ and performs 2/3/4, announcing $$c$$.
• Bob announces a guess $$m_b$$ in $$\{0, 1\}$$; he and Valery do not know the outcome yet, but Carol does.
• Carol states her choice of $$m$$ and $$r$$.
• Valery checks if $$m\ne m_b$$ and (needed only in the affirmative) $$\mathcal C(m,r)=c$$; in which case Carol serves first. Otherwise, Bob does.

Bob can't cheat, because $$c$$ (which he knows when choosing $$m_b$$) gives him no clue about $$m$$.

Carol can't cheat by choosing $$r$$ so that $$\mathcal C(0,r)=\mathcal C(1,r)$$ and giving the resulting value as $$c$$, which would allow her to announce $$m$$ per $$m_b$$. Having failed that, she can't reverse her choice of $$m$$, because the check $$\mathcal C(m,r)=c$$ will then catch that.

As pointed by Poncho, $$H(m,r)$$ where $$H$$ is a (preimage-resistant) hash is a commitment of $$m$$. Compared to this, Pedersen commitments:

• Allow things such as proving additive equalities (modulo the group order) among committed values, without revealing them; and more.
• Maintain their hiding property even w.r.t. computationally unbounded adversaries.
• BTW, it sounds like for high-entropy messages, you can just do commitment = H(m), but for short/low-entropy messages then pedersen commitments make sense. Jun 7, 2019 at 1:01
• @David天宇Wong: if all you need is a base commitment scheme, then commitment = H(m. r) makes sense. On the other hand, sometimes we need to do more than that; we might need to make provable statements about previously generated commitments, such as 'these two commitments are the same value'. That's easy to do with Pedersen commitments; rather harder with hash-based ones. May 12, 2020 at 12:36
• Your explanation is very nice.
– Land
Apr 13, 2022 at 2:03
• How to open this commitment in a zero-knowledge way?
– Land
Nov 7, 2022 at 3:54
• @Land: I suggest you open a new question for that; you'll get a wider audience. Plus I can't confidently answer that.
– fgrieu
Nov 7, 2022 at 4:19