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

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?

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.

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$$.
• 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$. Apr 10, 2022 at 21:04
• 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]$? Apr 11, 2022 at 11:23
• @Doron is a $v$ value also publicly declared as part of the proof, just like the $u$ value is? Apr 11, 2022 at 12:14