# 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 $(\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$.

• 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$