# Proving I can solve an equation without disclosing the solution (zero-knowledge proof)

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.

• 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 – Daniel Feb 15 at 3:35
• 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)? – SEJPM Feb 16 at 10:31
• 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. – chausies Feb 19 at 17:41

• 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. – SEJPM Feb 13 at 14:39