Score:1

Proving addition of secret values in a small field

cn flag

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?

Gareth Ma avatar
ng flag
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?
Sacha Servan-Schreiber avatar
sb flag
@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$).
Gareth Ma avatar
ng flag
@SachaServan-Schreiber Huh, I thought the definition of hash function includes {collision, preimage, second-preimage} resistant. Maybe I meant *cryptographic* hash functions
Sacha Servan-Schreiber avatar
sb flag
Yeah, as far as I know, a cryptographic hash would mean all those properties are satisfied
Kolja avatar
cn flag
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)?
Score:3
ng flag

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

Kolja avatar
cn flag
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!
Gareth Ma avatar
ng flag
@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.
Score:1
us flag

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.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.