# Using Pedersen commitment for a vector

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.

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 $$n-1$$ values for $$\alpha_j$$, $$(\alpha_j)_{j\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$$.

• 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...). – eternalmothra Feb 27 '18 at 13:36
• 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. – Geoffroy Couteau Feb 27 '18 at 15:02

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$