Hash into elliptic curves for private set intersection

Question

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 :

• How to Hash into Elliptic Curves, Thomas Icart

• Deterministic Hashing to Elliptic and Hyperelliptic Curves, Mehdi Tibouchi

• Efficient Indifferentiable Hashing into Ordinary Elliptic Curves, Thomas Icart

• hash - Fast hashing into elliptic curve - Cryptography Stack Exchange

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

Answer 1

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.