# Proving addition of secret values in a small field

Suppose that a prover holds two secret values $$x,y\in\mathbb{F}$$ and both the prover and verifier have $$z\in\mathbb{F}$$. The prover wishes to prove that $$z=x+y$$ without revealing $$x,y$$ to the verifier.
We can further assume that the verifier has access to some oracle which confirms whether commitments $$X,Y$$ to $$x,y$$ are honestly generated.

One way of doing it is the following: The prover sends $$X = g^x$$, $$Y = g^y$$, and the verifier checks if $$g^{z}=XY$$ (and confirms that $$X,Y$$ are honest).

I guess what is needed is a key-homomorphic hash function $$H$$, with which $$X=H_x(0), Y=H_y(0)$$ and $$H_{x+y}(0)=H_x(0)\oplus H_y(0)$$, but maybe something weaker could do the job (?).

Is there a way to solve this problem for small fields? For small we can assume that the size of the field is ~256 bits (so in particular DL is easy!). What about in general for large fields if we don't rely on DL?

• Homomorphic means it’s not a hash function (all the preimage and collision requirements fail because of linear algebra). Maybe you want a key homomorphic PRF? Jul 25 at 18:28
• @GarethMa, that's not entirely correct. A hash function is just a map from a large domain to a smaller range. A collision-resistant hash function is what you are describing. I think in this case the problem is that $g^x$ does not hide $x$ (e.g., imagine $x=1$, then a simple test is checking if $g^x = g$). Jul 25 at 19:27
• @SachaServan-Schreiber Huh, I thought the definition of hash function includes {collision, preimage, second-preimage} resistant. Maybe I meant cryptographic hash functions Jul 25 at 19:29
• Yeah, as far as I know, a cryptographic hash would mean all those properties are satisfied Jul 25 at 19:33
• Key-homomorphic is indeed a better choice, but I am unaware of any such functions over small fields. As for hiding, I guess something like $X=g^xh^r$, $Y=g^yh^{-r}$ would (almost) do the job (over a large field)? Jul 26 at 7:07

Write the finite field as $$\mathbb{F} = \mathbb{F}_q$$, where $$q = p^k$$ is a prime power. Since $$\mathbb{F}_q \cong \mathbb{F}_p^k$$, we can interpret $$x, y, z$$ as vectors over $$\mathbb{F}_p$$ where addition is performed component-wise. Hence, it suffices to prove $$x + y = z$$ over $$\mathbb{F}_p$$ which is quite well studied (I believe). Simplest is something like Paillier or Pedersen. If you want to overkill, See CD97, or thesis (lattice) or other resources.
Edit: Another approach is to note that $$x + y = z \iff \left(\bar{x} + \bar{y} = \bar{z}\right) \lor \left(\bar{x} + \bar{y} = \bar{z} + p\right)$$, where $$\bar{\cdot}$$ is the integer representation of $$\cdot$$ within $$[0, p)$$. From this answer, we can focus on proving relations over integers. There are results to do this, especially since you know a bound $$\bar{x}, \bar{y}, \bar{z} < p$$.