1
$\begingroup$

Let $g\in G$ and $h\in H$ be two group generators. Given a list L of m group elements, where $L=(L_1,...,L_m)$, a prover wants to convince a public verifier (namely, a verifier who only has public input) that one element $L_i$ in the list $L$ (without revealing i) can be produced from a public element $ u =u_i$ (where i should not be revealed) and some secret $s_i$, e.g., prove that there is some $i$ such that for which $L_i = g^{u_i}h^{s_i}$ for public $u_i$ and secret $s_i$. Is it possible to create such proof with Pedersen commitment or with Groth-Sahai commitment?

$\endgroup$

1 Answer 1

1
$\begingroup$

Note that $s_i$ and $u_i$ must be scalars (positive integers less than the group order $\ell$ of the generator) and not field elements.

In additive notation:

You have a set of Pedersen commitments of the form $L_i = s_iG+u_iH$ where $s_i$ is the random blinding factor and $u_i$ is the value being committed to.

To prove that a Pedersen commitment $L_i$ commits the value $u$, just provide a signature for $L_i - uH$ on the generator $G$. This proves the values (on generator $H$) exactly cancel each other out, because if they did not cancel each other out the signature would not be possible (because $G$ and $H$ are chosen such that $h$ is unknowable such that $H=hG$). The private key, known only to you, will be $s_i$.

To prove that one of a list of Pedersen commitments is a commitment to a certain $u$ value, just provide a ring signature instead. This will prove that in at least one of the cases, you've committed to that value. The list of public keys in the ring signature would be $\{L_i - uH\}$, and only where $u\overset{?}{=} u_i$ will there be a knowable corresponding private key $s_i$.

$\endgroup$
8
  • 1
    $\begingroup$ Real world example: that's exactly what Monero's RingCT construction does with input amounts $\endgroup$
    – baro77
    Apr 10, 2022 at 13:07
  • $\begingroup$ I think that I didn't explain myself properly. The prover outputs a proof $\pi$ and the public $u_i$ (not a commitment to $u_i$) so that any verifier that is given the list $L$, $u_i$, and $\pi$ would accept iff there exist a an element in the list (which, e.g., is a pedersen commitment) that was generated from $u_i$. $\endgroup$
    – Doron
    Apr 10, 2022 at 21:04
  • $\begingroup$ @Doron ah, I see. I've updated the answer, it's almost the same as before. $\endgroup$
    – knaccc
    Apr 10, 2022 at 21:26
  • $\begingroup$ Thanks @knaccc! That's indeed seems to be working! By the way, is it possible to even add another constraint that there is another secret $v_i$ s.t. $v_i\in [1..n]$ (i.e., each commitment is of the form $L_i = g^{u_i} h^{s_i}f^{v_i}$ such that $v_i\in [1..n]$? $\endgroup$
    – Doron
    Apr 11, 2022 at 11:23
  • $\begingroup$ @Doron is a $v$ value also publicly declared as part of the proof, just like the $u$ value is? $\endgroup$
    – knaccc
    Apr 11, 2022 at 12:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.