1
$\begingroup$

Is there any ZK protocol that can be used to prove dependence of two entities. More specifically, if there are x(dependent) and y(independent), is there protocol to prove that x is dependent or function of y, without revealing the function it self.

Edit: As replies below suggested, I thought to provide concrete form of dependent function. So for example x= 2+y another example can be x=ky, where k is yet another independent variable. In short, x can be even more complicated function of y.

$\endgroup$
  • 2
    $\begingroup$ How do you formally define "being dependent"? For any $x$, I define $f$ to be the constant function that always output $x$. Then we indeed have $x = f(y)$... So you must specify what type of dependency you consider. $\endgroup$ – Geoffroy Couteau Mar 8 '17 at 21:06
  • $\begingroup$ I have edited the question $\endgroup$ – muhammad haris Mar 8 '17 at 23:41
  • $\begingroup$ Still, you want to hide the function, so might want to say what exactly you want to prove. For example, you can prove that $x$ was computing by applying a degree-2 polynomial on $y$, while keeping the polynomial secret (or any other kind of well defined class of function that you can think of). But proving that $x = f(y)$ for some function f while hiding $f$ would make the protocol trivial: you could always prove that by choosing a "degenerate" function as in my previous comment. So you must define what class of "non-degenerated" functions" you want to consider. $\endgroup$ – Geoffroy Couteau Mar 8 '17 at 23:58
  • $\begingroup$ You must also specify what the verifier has that identifies x and y. ​ ​ $\endgroup$ – user991 Mar 9 '17 at 1:56
  • $\begingroup$ And you need to state what $x$ and $y$ actually are. Things like zero knowledge proofs are usually based on some finite group. Regarding your 2nd example: In that case $x$ and $y$ could be independent, but it really depends both on what kind of numbers you have and what kind of distributions. $\endgroup$ – tylo Mar 9 '17 at 10:14
2
$\begingroup$

Any NP statement can be proven in zero knowledge (not necessarily practically efficiently, but yes in polynomial time). So, if you can define what you want as an NP relation then it can be done. However, in order to do that, you must define what you mean by "dependent" and so on.

Such statements can also be highly efficient. For example, it is possible to efficiently prove that a tuple of elements if of the "Diffie Hellman type". Informally, one can prove that for some $(g,h,u,v)$ there exists a value $r$ such that $u=g^r$ and $v=h^r$ (where $g$ is the group generator and all operations are in the group). Observe that this is exactly a proof that $u$ and $v$ are ''dependent'' variables.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks yea Diffie Hellman is good place to start, can you please re read my edit ? $\endgroup$ – muhammad haris Mar 8 '17 at 23:41

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.