1
$\begingroup$

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)

$\endgroup$
8
  • $\begingroup$ Hmmmm, when you say $ h = f \times g $, do you mean cross product (that is, $h$ consists of the value $f$ and the value $g$), or do you mean finite field multiplication? I didn't think you meant multiplication, because there's no equivalent operation if you move to an elliptic curve $\endgroup$
    – poncho
    Sep 10, 2022 at 18:59
  • $\begingroup$ @poncho $ h(M) = f(M) * g(M) $, i should have noted that $ F, G \in Z $ $\endgroup$
    – Parsa G
    Sep 10, 2022 at 19:22
  • $\begingroup$ If $*$ is a multiplication operation, how are you intended to do that operation when you use the curve secp256k1/r1? $\endgroup$
    – poncho
    Sep 10, 2022 at 20:57
  • $\begingroup$ the elements $F_{i, b}$ and $G_{i, b}$ are scalar values, so the value of both $ f(M) $ and $ f(M) $ is also an scalar, i'm only using the finite field of the secp256, not the points. $\endgroup$
    – Parsa G
    Sep 10, 2022 at 21:36
  • $\begingroup$ So, you're using the field that sec256k1/r1 is defined on, and are not doing any elliptic curve additions/etc at all? $\endgroup$
    – poncho
    Sep 10, 2022 at 22:04

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you! I updated the question to note that $ H(M) = F(M) * G(M) $, how about that case? $\endgroup$
    – Parsa G
    Sep 10, 2022 at 19:26
  • $\begingroup$ this makes sense! thank you for the help xD, sadly i can't upvote yet :( $\endgroup$
    – Parsa G
    Sep 11, 2022 at 19:05

Your Answer

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

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