I found the paper on Efficient Protocols for Set Membership and Range Proofs in which efficient protocols for the following problem are discussed:

Given a commitment $C_v$ to a value $v$ we want show with a zero knowledge proof that $v$ is in a set $\Phi$. Only $C_v$, and $\Phi$ is publicly known in this scenario

However, I wondered if there are also efficient protocols for the following problem:

Given a commitment $C_v$ to a value $v$ and a signature $\sigma_\Phi$ on a set $\Phi$. Is it possible to efficiently show with a zero knowledge proof that $v$ is in the set $\Phi$ if only $C_v$ and $\sigma_\Phi$ are publicly known?

I read the very similar question Constructing set membership proof for private set. However, the difference there is that the element in question is publicly known and also no efficiency is considered.

Edit: Thank you Mikero, you were right. I did not consider the possibility that a signature might include a copy of the plain message :)

My intention is to do the following:

Suppose there are three parties: A prover $\mathcal{P}$, a verifyer $\mathcal{V}$ and a third-party $\mathcal{T}$.

We have a set $\Phi$ with signature $\sigma_\Phi$ from $\mathcal{T}$. $\mathcal{P}$ wants to efficiently prove to $\mathcal{V}$ that the commitment $C_v$ belongs to a value $v$ in the set $\Phi$, without $\mathcal{V}$ learning either $\Phi$ or $v$.

Basically $\mathcal{P}$ wants to prove that a value $v$ belongs to a set $\Phi$ from $\mathcal{T}$ without revealing the value or the set.

  • 1
    $\begingroup$ A signature is not required to hide the message that it signs. So you can consider a signature scheme where $\sigma_\Phi$ includes a literal copy of $\Phi$. But I'm sure that's not what you had in mind. You might need to add more constraints to your question. $\endgroup$ – Mikero Jul 11 '19 at 3:34
  • $\begingroup$ @Mikero Thank you for you comment, I edited my question. $\endgroup$ – bit Jul 11 '19 at 8:39
  • 1
    $\begingroup$ How big is your set? Should the size of the set remain hidden as well? Is it ok to replace the signature on the set by a commitment to the set, given by the trusted party? $\endgroup$ – Geoffroy Couteau Jul 13 '19 at 10:42
  • $\begingroup$ @GeoffroyCouteau The set is finite and has an upper bound m. The size of the set does not need to remain hidden (also it probably could be hidden by padding the set using some kind of dummy elements). I would like to avoid to make additional use of a trusted party. The statement to proof regarding the source of the set should not be stronger, than that it was signed with a key from the third party. However, if the key really was created by that third party may be checked using a trusted party. I hope this makes sense? :) $\endgroup$ – bit Jul 17 '19 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.