Zero-knowledge proof for committing a choice?

Question

Let's say there are 100 choices (which are publicly known), each represented as a different string, and today you have to choose one of them. You need not reveal what that choice is right now, though. One thing you could do is take your choice, append a bunch of entropy at the end, and publish your signature of the resulting string. Later, to prove that you made a valid choice, you can publish the string, proving that you had decided on that choice by the time you published the signature.

However, this still requires you to ultimately reveal your choice in order for others to verify that you did indeed select one of the 100 choices and didn't try to pass off some garbage string. Is there a zero-knowledge protocol, such that you can let others verify that you indeed chose one of the 100 choices without leaking any information? That is, we want the advantage of an adversary trying to guess your choice to be still only 1/100. If not possible, anything under 1 (which would result from directly revealing your choice) would nonetheless be an improvement.

Answer 1

Below is one possibility, but for a large set of values not a really efficient one as the work and the size is linear in the number of values. I additionally added a variant where the work and proof size is constant.

Standard OR Proof

Say we are working in a cyclic multiplicative group $G$ of prime order $p$ with generators $g$ and $h$ (such that the discrete logarithm between $g$ and $h$ is unknown to the users) and I assume that the values on the list (values $v_i$'s) are elements of $Z_p^*$ (e.g., by hashing the choices if they have a larger representation than values in $Z_p^*$ using a secure hash function).

You could publish an authentic list $(v_1,\ldots,v_{100})$ so everyone can check that these choices are indeed the possible choices or just give it to your users if you want to be the only one verifying the choices of the users.

Then, if a user chooses one out of the 100 possibilities, say $v_i$, the user computes an unconditionally hiding commitment to one of your choices (such that even knowning the 100 choices one cannot figure out which value is hidden in the commitment) as $H=g^{v_i}h^r$ for random $r\in Z_p^*$ (here by using a Pedersen commitment). In addition to $H$ the user publishes a non-interactive honest-verifier zero-knowledge proof of knowledge $\pi$ that the value in his commitment $H$ is equal to one of the values in the list. More precisely, with $\pi$ one proves the statement $$PoK\{(\beta):H=g^{v_1}h^\beta \vee H=g^{v_2}h^\beta \vee \ldots \vee H=g^{v_{100}}h^\beta\}$$ where this is a standard OR composition of discrete logarithm proofs and made non-interactive using the Fiat-Shamir heuristic.

So the user publishes the pair $(H,\pi)$ which convinces any verifier that the prover knows a secret value $r$ (the value $\beta$ in the proof, which is not revaled) such that his commitment $H$ is a commitment to one of the values $(v_1,\ldots,v_{100})$ without revealing which one.

If the user later on wants to open the commitment (reveal the choice) he publishes $(v_i,r)$ and everyone can check whether $H=g^{v_i}h^r$.

Efficient Set Membership Proof

In the above proof, the cost for the prover is $O(n)$ where $n$ is the cardinality of the set of values. You could also use the approach in this paper, which requires the publisher of the list to compute a (Boneh-Boyen) signature to each of the values of the list, i.e., costs of $O(n)$, but the cost for the proof is only $O(1)$, i.e., the prover computes a commitment and proves that he knows a value that has been signed, which can be efficiently done when using Boneh-Boyen signatures. The proof can also be made non-interactive using the Fiat-Shamir heuristic.