# Why is the Pedersen commitment perfectly hiding?

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?

## 1 Answer

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.

• 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=...)? – noamgot Jan 3 '18 at 15:38
• just read what you added - great explanation! thanks again – noamgot Jan 3 '18 at 18:54
• @noamgot there might be another pair, because no commitment scheme can be simultaneously both perfectly hiding (aka concealing) and perfectly binding. – Shelby Moore III Jan 28 '19 at 11:28