4
$\begingroup$

I learned today about the Pedersen commitment scheme.

A quick reminder (I know there are some variants of this scheme, so I will present the one I learned about):

  • Public parameters - 2 primes $p,q$ such that $p=2q+1$, and 2 elements $g_1, g_2 \in \mathbb{Z}_p^*$ of order $q$ (i.e $g_1,g_2$ are generators of a q-ordered sub-group of $\mathbb{Z}_p^*$).
  • Secret parameter - $s \in \mathbb{Z}_q$
  • The scheme - $P$ chooses $r \in \mathbb{Z}_q$ at random and sends the commitment $C = g_1^s g_2^r \pmod p$. Then $P$ reveals $s',r'$ and $V$ accepts iff $C = g_1^{s'} g_2^{r'} \pmod p$.

I read that the scheme is perfectly hiding (i.e - even an unbounded adversary cannot reveal $s$ given only the commitment $C$). Why is that true?

When I was asked if even an unbounded adversary can learn anything, I thought that such adversary can iteratively try possible values of $r,s$ until he finds such values that satisfy $C = g_1^s g_2^r$ (I was apparently wrong of course). Why isn't that correct?

$\endgroup$
11
$\begingroup$

When I was asked if even an unbounded adversary can learn anything, I thought that such adversary can iteratively try possible values of $r,s$ until he finds such values that satisfy $C = g_1^s g_2^r$ (I was apparently wrong of course). Why isn't that correct?

Because there are lots of different $r, s$ pairs that satisify the solution. In particular, for every possible $s$ value, there's exactly one corresponding $r$ value that satisfies $C = g_1^s g_2^r$. Hence, an exhaustive search will not eliminate any possible $s$ values (or make any one more likely); hence, the adversary gets no information about $s$ from the value of $C$.

How this works may be easier to understand if we map this to an easier-to-understand group; if we select an arbitrary subgroup generator $g$, and have $g^a = g_1$, $g^b = g_2$, and $g^c = C$ (as $C$ must also be in the subgroup), the relation is $g^c = g^{as} g^{br}$ or $c = as + br \bmod q$. We can rearrange this to $b^{-1}(c - as) = r$ (assuming $b \ne 0$; this cannot happen as $g_2$ was specified to be a generator), and so we can see that for a specific $s$ value, this gives us the unique $r$ value that satisfies the relation.

More precisely, the paragraph above (and in particular the equation $b^{-1}(c - as) = r$) shows us that for every value $s$ there is a unique value $r$ such that $C=g_1^s g_2^r$.

BTW: this is the same reason that One Time Pad is perfectly hiding.

$\endgroup$
  • $\begingroup$ thanks! how can we tell that there's only one matching r for each s? and more generally, how can we show that there might be another pair (s',r') which satisifies the equation (C=...)? $\endgroup$ – noamgot Jan 3 '18 at 15:38
  • $\begingroup$ just read what you added - great explanation! thanks again $\endgroup$ – noamgot Jan 3 '18 at 18:54
  • $\begingroup$ @noamgot there might be another pair, because no commitment scheme can be simultaneously both perfectly hiding (aka concealing) and perfectly binding. $\endgroup$ – Shelby Moore III Jan 28 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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