# Proof of using a literal from known set, inside a computed formula

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$$

• 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.
• 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? – Squeamish Ossifrage Apr 11 '18 at 13:57
• 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'$. – Squeamish Ossifrage Apr 11 '18 at 14:42
• 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. – 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.

• 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. – Vadym Fedyukovych Jun 11 '18 at 7:43