Why is the Pedersen commitment perfectly hiding?

Question

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?

Answer 1

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.