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

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.

| improve this answer | |
  • $\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.