# Commiting to a linear relation over a finite field

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.

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