4
$\begingroup$

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

$\endgroup$

closed as off-topic by kelalaka, e-sushi Dec 3 '18 at 8:54

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Here is a link to Pedersen's paper: link.springer.com/chapter/10.1007/3-540-46766-1_9 $\endgroup$ – dkaeae Nov 30 '18 at 13:21
  • 1
    $\begingroup$ @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. $\endgroup$ – Paul Berg Dec 3 '18 at 20:45
  • 2
    $\begingroup$ This question is being discussed on meta. $\endgroup$ – Gilles Dec 12 '18 at 8:22
16
$\begingroup$

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 adversary succeeds if s/he 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$.


what they are used for

Such 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, and the message can't leak. 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 tat 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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David 天宇 Wong Jun 7 at 1:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.