Score:1

Create an or-proof for a given list of elements with public input

es flag

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?

Score:1
es flag

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

baro77 avatar
gd flag
Real world example: that's exactly what Monero's RingCT construction does with input amounts
es flag
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$.
knaccc avatar
es flag
@Doron ah, I see. I've updated the answer, it's almost the same as before.
es flag
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]$?
knaccc avatar
es flag
@Doron is a $v$ value also publicly declared as part of the proof, just like the $u$ value is?
es flag
@knaccc, no the v value should be kept as secret, only contrainted to be on the range [1..n]
knaccc avatar
es flag
@Doron what is the objective? $s$ only exists to blind the commitment (to prevent it from being brute-forced to discover the value committed to). How does it help to blind it twice?
es flag
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/135473/discussion-between-doron-and-knaccc).
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.