Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
If I construct a vector pedersen commitment $c = a_1G_1 + a_2G_2 + ... + a_nG_n$ with an arbitrary scalar vector $(a_1, a_2, ..., a_n)$ and group elements $(G_1, G_2, ..., G_n)$, is it possible to create a range proof that proves that each element in this commitment is non-negative?
I understand that it is possible to create a range proof using Bulletproofs for cases like $c=aG+bH$, but is it possible to create a range proof for vectors like the one above as well?
Your vector commitment does not have a blinding factor, which means it does not hide whether two different commitments are to the same list of $a_i$ components. Depending on the nature of the $a_i$ components, it may also be possible to brute-force the commitment to determine the components it represents.
We can easily fix this by adding a blinding factor $b$:
$C = a_0G_0 + a_1G_1 + ... + a_{n-1}G_{n-1} + bH$
We wish to demonstrate that each component $a_i$ is a positive integer less than $2^s$.
To do this, we create and declare $(n\cdot s)$ commitments each with their own uniformly random blinding factor $b_{i,j}$, where $0\leq i <n$ and $0\leq j <s$. Each commitment $C_{i,j}$ is calculated as $C_{i,j} = (z_{i,j}\cdot 2^j)G_i + b_{i,j}H$, where $z_{i,j}$ is $0$ or $1$ and represents the $j$th bit of the component $a_i$.
A verifier can calculate $C'=\sum C_{i,j}$. We can demonstrate that $C$ represents the same list of $a_i$ components as $C'$ by providing a signature for the public key $(C-C')$ on the base point $H$. The private key for the point $(C-C')$ will be the value $b-\sum b_{i,j}$.
We've now demonstrated two things: $C$ is a commitment to the same list of components as $C'$, and that each component $a_i$ is created as a list of no more than $s$ bits (and thus must be a positive integer).
All that is left is to demonstrate is that each of the declared commitments $C_{i,j}$ really is a commitment either to $0$ or to $2^jG_i$.
This can be achieved with any kind of ring signature that proves the private key for either $C_{i,j}$ or $(C_{i,j} - 2^jG_i)$ on the base point $H$ is known. You can use bulletproofs or the simpler to understand Borromean ring signatures to achieve this.
