Suppose I have publicly revealed the value of $\phi(u) = A+Bu$, where A, B, u are private values from a large group, that I want to keep in secret.

Furthermore, I want to add proof that the value $u$ is from a publicly known set of values, without revealing its real value.

  1. How can I do that?
  2. Same question with proof about $A$

I thought about:

  • A zero-knowledge scheme, but it seems to be inadequate to that purpose because the value $u$ is publicly known.
  • Private set intersection - But since $u$ is from a publicly known set I might reveal its value.
  • 1
    $\begingroup$ You said there's a group, but you've used addition and multiplication, so there's obviously more than just a group here. Is there actually a ring structure? A field? $\endgroup$ – Squeamish Ossifrage Apr 11 '18 at 13:57
  • 1
    $\begingroup$ If you have a field, then for any value $p = \phi(u)$ and any $u′$, one can presumably pick $A' = 0$ and let $B' = p\cdot (u')^{-1}$, and then you get $p = A' + B' u'$, so no matter what $A$, $B$, and $u$ were to begin with, given $p$ you can fabricate an $A'$, $B'$, and $u'$ also matching the structure $p = \phi'(u') = A' + B' u'$. $\endgroup$ – Squeamish Ossifrage Apr 11 '18 at 14:42
  • $\begingroup$ Probably this does not work, unless you specify more of the formula. All those private values don't even exist from the point of view of the verifier - and there is nothing to check. You basically publish a random element, and we can only guess there might be values $A,B$ for every $u,\phi$. Which means the construction has no relvance. $\endgroup$ – tylo Aug 10 '18 at 8:44

In Crypto 94, Cramer, Damgård and Schoenmakers proposed Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols with abstract below:

Suppose we are given a proof of knowledge $P$ in which a prover demonstrates that he knows a solution to a given problem instance. Suppose also that we have a secret sharing scheme $S$ on $n$ participants. Then under certain assumptions on $P$ and $S,$ we show how to transform $P$ into a witness indistinguishable protocol, in which the prover demonstrates knowledge of the solution to some subset of $n$ problem instances out of a collection of subsets defined by $S.$

For example, using a threshold scheme, the prover can show that he knows at least $d$ out of $n$ solutions without revealing which $d$ instances are involved. If the instances are independently generated, we get a witness hiding protocol, even if $P$ did not have this property.

Our results can be used to efficiently implement general forms of group oriented identification and signatures. Our transformation produces a protocol with the same number of rounds as $P$ and communication complexity $n$ times that of $P.$ Our results use no unproven complexity assumptions.

The authors also state:

Our techniques are to some extent related to those of De Santis et al. The models are quite different, however: They consider non-interactive proofs of membership, while we consider interactive proofs of knowledge.

The paper is available here


1- Maybe you could use the CDS protocol (sorry, link content is in Spanish, I could not find any Wikipedia English page but the maths are valid though). While $u$ is from a public set, it should still remain secret. The CDS is usually used for voting system, where $u$ belongs to the set $\{0,1\}$ (yes or no). It is indeed a "Zk-proof" approach but it is quite "light" as long as $u$ does not belong to a "big" set.

  • $\begingroup$ Cramer-Damgard-Schoenmakers did introduce an OR proof, that works exactly by proving the "true" statement and simulating all others, connected together with a sum of challenges of each sub-protocol instance. $\endgroup$ – Vadym Fedyukovych Jun 11 '18 at 7:43

Your Answer

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

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