1
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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? $\endgroup$
    – Gareth Ma
    Jul 25 at 18:28
  • 1
    $\begingroup$ @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$). $\endgroup$
    – Sacha Servan-Schreiber
    Jul 25 at 19:27
  • $\begingroup$ @SachaServan-Schreiber Huh, I thought the definition of hash function includes {collision, preimage, second-preimage} resistant. Maybe I meant cryptographic hash functions $\endgroup$
    – Gareth Ma
    Jul 25 at 19:29
  • 1
    $\begingroup$ Yeah, as far as I know, a cryptographic hash would mean all those properties are satisfied $\endgroup$
    – Sacha Servan-Schreiber
    Jul 25 at 19:33
  • $\begingroup$ 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)? $\endgroup$
    – Kolja
    Jul 26 at 7:07

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Pedersen works in theory, but in practice the DL assumption is not hard (I mentioned the field is small!). It seems I will need to go for the overkill, and the cited articles look very useful, thank you for sharing! $\endgroup$
    – Kolja
    Jul 26 at 11:45
  • 1
    $\begingroup$ @Kolja I am not that experienced so take my comment with a grain of salt. However, I highly suspect that there's some way easier scheme if you just want the simple relation here. I will edit the post with an alternative approach. $\endgroup$
    – Gareth Ma
    Jul 26 at 12:40
1
$\begingroup$

key-homomorphic hash function can be used as you suggested. Key-homomorphic hash functions [PRF can be find here] 1 enable certain homomorphic properties that allow computations on the commitments to be performed without revealing the underlying secrets (in your case, x and y).

For small fields, you can use a key-homomorphic hash function H to generate the commitments X and Y, such that X = H(x, r1) and Y = H(y, r2), where r1 and r2 are random blinding factors. Then, you can use the homomorphic property of the hash function to compute H(x + y, r1 + r2) = H(x, r1) ⊕ H(y, r2), where ⊕ represents the field addition operation. This is possible because you mentioned that in small fields (around 256 bits), discrete logarithm (DL) is easy, and this enables efficient computation of the commitment values and their addition.

However, in larger fields, if we cannot rely on the discrete logarithm assumption being easy, finding a key-homomorphic hash function might be challenging. As the field size increases, it becomes difficult to find efficient key-homomorphic hash functions that can perform homomorphic operations on commitments.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.