3
$\begingroup$

I'm reading Bootle/Groth. I'm trying to understand how they are committing to a vector using Pedersen commitment. Here's my understanding of Pedersen commitment in the context of this paper:

  1. We have a group $\mathbb{Z}_p^*$, $g$ as a generator.
  2. The generator produces random group elements $(g_1,\dots,g_n,y)$.
  3. We commit to the vector $\vec{m} = (m_1,\dots, m_n)$ by choosing $r$ randomly from $\mathbb{Z}_p^*$ and then $c = Com(\vec{m};r)$ is $c = y^r \prod_{i=1}^n g_i^{m_i}$.

The paper goes on to describe how $\vec{m}$ is actually a row of coefficients in a polynomial, and the verifier may send an input $x$ to be evaluated (without finding out what the polynomial is!). What I am wondering, though, is:

  1. Does my understanding of this scheme make sense?
  2. If so, what makes this scheme (computationally) hiding and binding? I don't know how to walk through a proof of this.
$\endgroup$
4
$\begingroup$

Yes, you got the scheme essentially right - except that the group cannot be $\mathbb{Z}_p^*$, as the latter does not have prime order. It can however be many other things - like the multiplicative subgroup of squares over $\mathbb{Z}_p^*$, or an elliptic curve. Let us simply consider the scheme as you described it, over some group $\mathbb{G}$ of prime order $p$.

Why is the scheme hiding?

Intuitively, the scheme is perfectly hiding because for any commitment $c$, and for any tuple $(m_1, \cdots, m_n)$, there exists an opening $r$ that "explains" $c$ as $c = y^r\prod_{i=1}^n g_i^{m_i}$, and the distribution of this $r$ (taken over the coins used to generate $c$) is uniform.

More formally, denoting $a\gets_r S$ the action of drawing $a$ uniformly at random from $S$, the commitment scheme is perfectly hiding because for any pair of tuples $(m_1, \cdots, m_n)$ and $(m'_1, \cdots, m'_n)$, the distributions $$D = \left\{c : r\gets_r\mathbb{Z}_p, c \gets y^r\prod_{i=1}^n g_i^{m_i}\right\} \text { and } D' = \left\{c : r\gets_r\mathbb{Z}_p, c \gets y^r\prod_{i=1}^n g_i^{m'_i}\right\}$$ are perfectly equal. This is easy to show: for $i=1$ to $n$, let $\alpha_i$ denote the exponent of $g_i$ in base $y$ (id est, $g_i^{\alpha_i} = y$). Let $\alpha \gets \sum_{i=1}^n \alpha_im_i$ and $\alpha' \gets \sum_{i=1}^n \alpha_im'_i$.

Then $c$ is computed as $y^r\prod_{i=1}^n g_i^{m_i} = y^{r+\alpha}$ in $D$ (for a random $r$), and as $y^r\prod_{i=1}^n g_i^{m'_i} = y^{r+\alpha'}$ in $D$ (for a random $r$). The equality of the distributions is therefore immediate.

Why is the scheme binding?

We can show that the scheme is binding under the discrete logarithm assumption. Let $\mathcal{A}$ be a PPT adversary which, given the parameters of the system (in this case, $(y,g_1, \cdots, g_n)$) can produce (with non-negligible probability $\varepsilon$) a commitment together with valid openings to two different plaintexts, id est: $(c,(m_1, \cdots, m_n),r,(m'_1,\cdots, m'_n),r')$, where $c\in\mathbb{G}$ is a commitment, $(m_1, \cdots, m_n) \neq (m'_1, \cdots, m'_n)$, and $$c = y^r\prod_{i=1}^n g_i^{m_i} = y^{r'}\prod_{i=1}^n g_i^{m'_i}.$$

Let us use this algorithm to break the discrete logarithm assumption with non-negligible probability. Upon receiving a random discrete-log challenge $(g,y)$, we pick $i$ at random between $1$ and $n$, and set $g_i \gets g$. Then we pick $(\alpha_j)_{i\neq i}\gets_r \mathbb{Z}_p^{n-1}$, and set $g_j \gets y^{\alpha_j}$ for any $j\neq i$. Observe that $(y, g_1, \cdots, g_n)$ is perfectly distributed as a valid tuple of parameters for the Pedersen commitment scheme. Therefore, we run $\mathcal{A}(y,g_1,\cdots, g_n)$ and obtain $(c,(m_1, \cdots, m_n),r,(m'_1,\cdots, m'_n),r')$ where it holds with probability $\varepsilon$ that $(m_1, \cdots, m_n) \neq (m'_1, \cdots, m'_n)$ and $c = y^r\prod_{j=1}^n g_j^{m_j} = y^{r'}\prod_{j=1}^n g_j^{m'_j}$. We check whether $m_i \neq m'_i$, and restart the protocol otherwise. Note that as our (uniformly random) choice of $i$ is perfectly hidden from $\mathcal{A}$, and as $(m_1, \cdots, m_n) \neq (m'_1, \cdots, m'_n)$ with probability at least $\varepsilon$, it holds that $m_i \neq m'_i$ with probability at least $\varepsilon/n$.

Let $\alpha \gets \sum_{j\neq i} \alpha_j m_j$ and $\alpha' \gets \sum_{j\neq i} \alpha_j m'_j$. If $m_i \neq m'_i$, we therefore have the following:

$y^r\prod_{j=1}^n g_j^{m_j} = y^{r'}\prod_{j=1}^n g_i^{m'_j}$

hence $y^r g^{m_i}\cdot y^{\alpha} = y^{r'} g^{m'_i} y^{\alpha'}$

hence $y^{r-r'+\alpha-\alpha'} = g^{m_i-m'_i}$, with $m_i - m'_i \neq 0$

hence $y^{(r-r'+\alpha-\alpha')\cdot(m_i-m'_i)^{-1}\bmod p} = g$: we obtain the discrete log of $y$ in base $g$.

Therefore, if $\mathcal{A}$ breaks the binding property of the Pedersen commitment scheme with probability at least $\varepsilon$, we can construct an algorithm which, given access to $\mathcal{A}$, extracts the discrete logarithm of $g$ in base $y$ with probability at least $\varepsilon/n$.

$\endgroup$
  • 1
    $\begingroup$ Good answer, just confused about $\mathbb{Z}^*_p$ "as the latter is not a cyclic group". I understand $\mathbb{Z}^*_p$ can't be used because it doesn't have prime order, but I thought cyclic group meant "has a generator". (This actually may be worth me asking a new question...). $\endgroup$ – eternalmothra Feb 27 '18 at 13:36
  • $\begingroup$ Yes, that was a mistake, I kind of confused myself with $\mathbb{Z}_n^*$, where $n$ is a composite - I dunno exactly what I was thinking about when I wrote that. Anyway, I fixed it. $\endgroup$ – Geoffroy Couteau Feb 27 '18 at 15:02
0
$\begingroup$

Does my understanding of this scheme make sense?

It's close, but it's off by one detail.

The paper says to use a prime order group; you state "We have a group $\mathbb{Z}_p^*$, $g$ as a generator". The issue here is that if $g$ is actually a generator (that is, generates the entire group), well, that's a group of size $p-1$, which is not prime. That turns out to mess up the hiding aspect; e.g. if $y$ happens to be a quadratic residue, then the attacker can deduce the parity of some of the lsbits from some of the $m_1, m_2, ..., m_n$ elements.

Instead, what you can do is make $p$ a safe prime (that is, $(p-1)/2$ is also prime), and have $g$ generate the subgroup of quadratic residues.

If so, what makes this scheme (computationally) hiding and binding?

It's pretty much a simple extension of the proof for the original Pedersen scheme

  • It's perfectly hiding, as for any set of potential committed values $m_1, m_2, ..., m_n$, there's a unique value $r$ that makes the commitment be the value that the verifier sees, hence the verifier gets no information about the values $m_1, m_2, ...., m_n$

  • Assuming that the DLog problem is hard and the committer does not know any nontrivial solution to $g_1^{x_1} g_2^{x_2} ... g_n^{x_n} y^{y_1} = 1$ (where $x_1 = x_2 = ... = x_n = y_1 = 0$ is the trivial solution), then it is computationally binding. In particular, you can show that, if the committer has an oracle that, given $g_i, y$ values, finds two $m_i, m'_i$ vectors and $r, r'$ values that form the same commitment, they can solve the discrete log problem with overwhelming probability of success (to solve the DLog problem for $g, h$, select random values $r_1, r_2, ..., r_n, r_{n+1}, s_1, s_2, ..., s_n, s_{n+1}$, set $g_i = g^{r_i}h^{s_i}$, $y = g^{r_{n+1}}h^{s_{n+1}}$; give those values to the oracle, examine the two commitments; linear algebra will give allow you to solve $g^x = h$ with failure probability bounded by $2/p$

$\endgroup$

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.