1
$\begingroup$

Would it be insecure to hash a message $m$ to an elliptic curve point by multiplying it to some generator $G$ for the purpose of a private set intersection ?

$$ M = hash(m) * G $$

I keep seeing references that hashing with $M = hash(m) * G$ might be dangerous :

the discrete logarithm of $h(m)$ with respect to $G$ is known , which makes most protocols insecure.

However in the case of a private set intersection we can use a secret key $s$, so if I am correct the discrete logarithm of $h(m) *s$ would not be known :

$$ M_s = h(m) * s * G $$

Private Set Intersection

In the case of a private set intersection Alice and Bob each have a secret key ($s_A$ and $s_B$) and lists of data. To see what data they have in common they encrypt their data twice (once with each secret key) and search for the matches. In this example Alice has the message $m_1$ and Bob the message $m_2$.

  1. Alice computes $M_{1,A} = M_1 * s_A = h(m_1) * s_A * G $
  2. Alice sends $M_{1,A}$ to Bob
  3. Bob computes $M_{1,AB} = M_{1,A} * s_B$ and $M_{2,B} = M_2 * s_B$
  4. Bob sends $M_{1, AB}$ and $M_{2, B}$ to Alice
  5. Alice computes $M_{2, BA} = M_{2, B} * s_A$
  6. If $M_{2, BA} = M_{1, AB}$ then $M_1 = M_2$

In summary we test if $$ h(m1) * s_A * s_B * G = h(m2) * s_A * s_B * G $$

$\endgroup$
1
$\begingroup$

However in the case of a private set intersection we can use a secret key $s$, so if I am correct the discrete logarithm of $h(m) *s$ would not be known :

That is correct; it is not known; however that is not sufficient; the relationship between $h(m_1) * s$ and $h(m_2) * s$ would be known (if you know $m_1, m_2$), and that breaks security (at least, within this protocol).

In this protocol, Bob computes (in step 3) $h(m_{1}) * s_A * s_B * G$ and $h(m_{2}) * s_B * G$, and sends them (in step 4) to Alice (and then Bob has no further interaction with Alice).

If Alice has a guess $m'_2$ of Bob's value, what she can do is compute $(h(m'_2) * h(m_1)^{-1}) * (h(m_{1}) * s_A * s_B * G)$ and $s_A * (h(m_{2}) * s_B * G)$; if these are the same, then her guess $m'_2$ is the same as Bob's $m_2$. Alice can perform this computation with any number of $m'_2$ values, without any further interaction with Bob; allowing her to recover a guessable Bob's secret value after a single exchange.

This works because Alice is able to derive what her exchanged value would have been, had she started with a different secret to begin with.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Wow, I did not see that. This is a great answer. I don't understand your final note about Alice being able to derive what her exchanged value would have been though. But I do understand the concept, Alice computes the inverse of $h(m_1)$ to reuse Bob's answer and perform an offline brute force attack. $\endgroup$ – braincoke Jul 2 at 12:10
  • $\begingroup$ Do you have any knowledge of a method to hash a point into an elliptic curve that would be simple enough and secure for this use case ? $\endgroup$ – braincoke Jul 2 at 12:12
  • $\begingroup$ @braincoke: you might look through datatracker.ietf.org/doc/draft-irtf-cfrg-hash-to-curve $\endgroup$ – poncho Jul 2 at 13:00

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.