Is product of two linear combinations over a finite field information hiding?

Question

Suppose we have a 32-bit message $ M=(m_1,..m_{32}) \in \{0, 1\}^{32} $ and we have secrets $ F_{i, b} $ and $ G_{i, b} $ (2x32+2x32=128 secrets in total).

$$ \forall 1 \leq i \leq 32, b \in \{0, 1\} : F_{i, b}, G_{i, b} \in Z_q $$

And now we define two functions $ f $ and $ g $ respectively:

$$ f(m_1, .., m_{32})= \sum_{i=1}^{32}{F_{i, m_i}} $$ $$ g(m_1, .., m_{32})= \sum_{i=1}^{32}{G_{i, m_i}} $$

We say $ h(M) = f(M) * g(M) $, and we publish the evaluations of $ h $ for every possible message, how many distinct tuples of $ (M, h(M)) $ is needed for an adversary to be able to recover the secrets $ F_{i, b}, G_{i, b} $? Or can we assume that the function $ h $ is information hiding regarding $ F, G $?

I would appreciate any references or hint about which part of the literature I should look into!

(P.S: we're doing all of this in a finite field, the implementation should use curve secp256k1/r1 in practice)

Answer 1

would it be sufficient if the attacker could compute $h(M)$ for values of $M$ that he did not query?

yes, that's also not desirable

Ok, here's one (not likely to be optimal approach) to do that, which succeeds with good probability for an attacker chosen message given 529 random $M, H(M)$ pairs.

We can rewrite $h(M)$ as follows:

$$h(m) = \sum_{i : m_i \ne 0} c_i + \sum_{i, j : i < j \land m_i, m_j \ne 0} d_{i,j} + e$$

with the assignments:

$$F_{i,\Delta} = F_{i,1} - F_{i,0}$$ $$G_{i,\Delta} = G_{i,1} - G_{i,0}$$ $$c_i = F_{i,\Delta}G_{i,\Delta} + F_{i,\Delta} \sum_k G_{k,0} + G_{i,\Delta} \sum_k F_{k,0}$$ $$d_{i,j} = F_{i,\Delta}G_{j,\Delta} + F_{j,\Delta}G_{i,\Delta}$$ $$e = \sum_k F_{k,0} \cdot \sum_k G_{k,0}$$

The attacker knows, for any message $M$, which values of $c_i, d_{i,j}, e$ which need to be added together to create the sum. There are a total of 529 such values (32 $c_i$ values, 496 $d_{i,j}$ values and 1 $e$ value); if he has 529 random $M$ values (with the appropriate sum), he has a good chance of being able, for another message $M'$, being able to use linear algebra to find the appropriate sum from the equations he knows.

Now, this is likely not the best possible approach; after all, there are only 128 secrets, and so in theory, it should be computable with that many (and actually less; there are symmetries where a number of sets of secret values give the same output). However, this gives one upper limit on how many $h(M)$ values you can publish.