0
$\begingroup$

Suppose I have some finite field $k$. I am wondering if there exists a way to commit to a linear relation $a_1x_1 + a_2x_2 + \cdots + a_mx_m = b$ over $k$ , such that I can later reveal that a certain $m-$tuple $(c_1,\cdots ,c_m)$ satisfies $a_1c_1+\cdots a_mc_m = b$, but without revealing the coeficients $a_1 , \cdots , a_m$?

If it helps you can assume that the finite field is of prime order, but if you know a way to do this in an arbitrary finite field that would be even better.

$\endgroup$
2
$\begingroup$

If we can assume that $k$ is a large prime order (say, 256 bits or larger), one way is with Pederson commitments.

Assuming $g, h$ are two unrelated bases of order $k$ in $Z_p$ (for some large (2048 bit or more) prime $p = kn+1$), then the commitment are the values $g^{a_1}h^{r_1}, g^{a_2}h^{r_2}, ..., g^{a_m}h^{r_m}, g^{-b}h^{r'} = d_1, d_2, ..., d_m, d_b$, where $r_1, r_2, ..., r_m, r'$ are random values between 0 and $k-1$.

Then, to prove that a specific $c_1, c_2, ..., c_m$ satisfies the linear relation, you generate a zero knowledge proof that you know the value $x$ such that $h^x = d_b \cdot d_1^{c_1}d_2^{c_2} ... d_m^{c_m}$

This is equivalent to starting that $h^x = g^{a_1c_1 + a_2c_2 + ... + a_mc_m - b}h^{c_1r_1 + c_2r_2 + ... + c_mr_m + r'}$; if $a_1c_1 + a_2c_2 + ... + a_mc_m - b \equiv 0 \pmod k$, the prover can do this (assuming he remembers the values $r_1, r_2, ..., r_m, r'$ that he used); if $a_1c_1 + a_2c_2 + ... + a_mc_m - b \not\equiv 0 \pmod k$, then this reduces $h^x = g^yh^z$ for a nonzero $y$ and some $z$; as we assume no one knows the discrete log of $g$ to base $h$, the prover cannot know $x$.

I don't immediately see how to make this work in smaller groups (working in a larger subgroup that has $k$ as a proper factor doesn't work), but at least it's a solution that works in some cases...

| improve this answer | |
$\endgroup$

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.