1
$\begingroup$

Given a (potentially multivariable) equation $f(x)=0$, Peggy wants to prove to Victor that she knows a solution $x^\star$ to it without actually disclosing anything information about the value of $x^\star$.

Is there a slick way to pull off this zero-knowledge proof?

If possible, I want a solution

  1. in the continuous context where $x\in\mathbb{R}^n$ (and, if necessary, $f$ is well-behaved and infinitely differentiable.)
  2. in the discrete context, where $x\in GF(p)$ (i.e. modulo a large prime $p$).

For a continuous example: $f(x) = [ x_1 \cdot x_2 - 2 , x_1^3 - x_2 + 1] = [0, 0]$. A solution is $x^\star = (1, 2)$.

For a discrete example: $f(x) \equiv 2^{x_1} + 3^{x_2} - x_1 \equiv 0 \pmod{5}$. A solution is $x^\star=(1,2)$.

In both cases, we want to show we have that solution without disclosing the value.

Edit: You can absolutely assume that $f$ can be efficiently evaluated, making the problem in NP.

Edit 2: I in particular want a slick solution that doesn't involve just considering the boolean computation circuit. Something more akin to the zero-knowledge proof that one knows of a Hamiltonian path by considering providing it on an isomorphic graph.

$\endgroup$
3
  • $\begingroup$ One of the main compilations when developing ZK proofs (and in general Cryptography) over the reals is the need of sampling uniformly random values, which is essential to perform “masking” in many ZK constructions $\endgroup$ – Daniel Feb 15 at 3:35
  • $\begingroup$ If you aren't looking for a (generic) circuit-based solution, can you somehow restrict the set of operations being used in the equations (e.g. only addition, multiplication, subtraction, exponentiation)? $\endgroup$ – SEJPM Feb 16 at 10:31
  • $\begingroup$ Any generic mathematical functions (like one might encounter in $f$) are fine. I imagine a good solution might look something like "Draw out the graph of computations done by $f$. Selectively reveal a value computed partway through the real computational graph, or a fake one." Some scheme like that. $\endgroup$ – chausies Feb 19 at 17:41
3
$\begingroup$

For the discrete case, you can just use any zk-SNARK that generalizes over arithmetic circuits.

There is no direct way to do a zero-knowledge proof over the reals. However, you can map linear operations over real numbers to operations in the field you are working in by first proving an upper bound on your inputs. Since the circuit is public the verifier can independently check if the upper bound leads to overflow.

$\endgroup$
2
  • $\begingroup$ Alternatively one could use zk-SNARKS over boolean circuits and use boolean floating point arithmetic circuits and then prove that the output is smaller than some fixed, acceptable constant, e.g. $2^{-10}$, depending on the semantics of the proof in the grander context. $\endgroup$ – SEJPM Feb 13 at 14:39
  • $\begingroup$ Sorry, I should have been more clear. I in particular wanted a "slick" solution that didn't involve heavy-handedly working over the computational circuit. I wanted a solution more like what's used for proving you know a hamiltonian cycle by providing it on a random isomorphic graph, or proving you know a three coloring by providing showing a part of it with a random permutation of the colors. $\endgroup$ – chausies Feb 15 at 18:47

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.