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:


We have a group $\mathbb{Z}_p^*$, $g$ as a generator.
The generator produces random group elements $(g_1,\dots,g_n,y)$.
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:


Does my understanding of this scheme make sense?
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$.