Hashing to elliptic curves $y^2 = x^3 + b$ provided that $b$ is a quadratic residue

Hi guys,

I wrote a new article

Hashing to elliptic curves y^2 = x^3 + b provided that b is a quadratic residue.pdf (244.9 KB)

In my opinion, this is the most useful result for applied cryptography I have ever obtained. Please read its abstract:

Let \mathbb{F}_{\!q} be a finite field and E_b\!: y_0^2 = x_0^3 + b be an ordinary elliptic \mathbb{F}_{\!q}-curve of j-invariant 0 such that \sqrt{b} \in \mathbb{F}_{\!q}. In particular, this condition is fulfilled for the curve BLS12-381 and for one of sextic twists of the curve BW6-761 (in both cases b=4). These curves are very popular in pairing-based cryptography. The article provides an efficient constant-time hashing h\!: \mathbb{F}_{\!q} \to E_b(\mathbb{F}_{\!q}) of an absolutely new type for which at worst \#\mathrm{Im}(h) \approx q/6. The main idea of our hashing consists in extracting in \mathbb{F}_{\!q} a cubic root instead of a square root as in the well known (universal) SWU hashing and in its simplified analogue. Besides, the new hashing can be implemented without quadratic and cubic residuosity tests (as well as without inversions) in \mathbb{F}_{\!q}. Thus in addition to the protection against timing attacks, h is much more efficient than the SWU hashing, which generally requires to perform two quadratic residuosity tests in \mathbb{F}_{\!q}. For instance, in the case of BW6-761 this allows to avoid at least approximately 2 \!\cdot\! 761 \approx 1500 field multiplications.

In your opinion, is this a useful result ? Please let me know in order to collaborate if any of companies or startups wants to use my hashing in its products. In this case I can implement it in one of programming languages.

Best regards.

1 Like

Interesting!

Quick question: does this apply to the altbn-128 curve as well, or no?

Unfortunately no, because for the altbn-128 curve the coefficient b = 3. It is a quadratic non-residue in the finite field. I will try to generalize my approach to this curve, but the task is very non-trivial, in my opinion.

Oh, that’s great! I’m pleased to see you changed your opinion from earlier this year:

A few questions:

  1. How much faster is the hashing compared to Wahby-Boneh?
  2. Have you tried implementing the function?

Can you expand on this? Does this imply that your hash function does not behave like a random oracle (unlike Wahby-Boneh)?

How much faster is the hashing compared to Wahby-Boneh?

My hashing is not much faster, because the Wahby-Boneh hashing uses an \mathbb{F}_{\!q}-isogeny \varphi of degree 11. This is a quite small degree. If Horner’s method is applied for the image computation of \varphi, then it is sufficient approximately 50 field multiplications. However, in my opinion, the new hashing is more elegant)

My hashing is much faster if an elliptic curve does not have \mathbb{F}_{\!q}-isogenies of small degree.

Have you tried implementing the function?

Not yet. I can try this if you are potentially interested in putting my hashing into practice. What programming languages do you use ?

Can you expand on this? Does this imply that your hash function does not behave like a random oracle (unlike Wahby-Boneh)?

Sorry, I have no experience with random oracles, so I’m not sure I understand your question. I just estimated the image cardinality of the new hashing as a usual set map.

If I am not mistaken, the cardinality of the Wahby-Boneh hashing equals {\approx} 3q/(8 \!\cdot\! 11). Indeed, the image cardinality of the simplified SWU hashing is equal to {\approx} 3q/8 according to Propositon 4 of Article. However, the isogeny \varphi maps 11 points to one. Thus since 88/3 \approx 29.3, the image of my hashing has the cardinality at least 5 times more.

Understood. The Boneh-Wahby hash function is being standardised by IETF for use across various blockchain projects. At this point in time a significant speedup is probably required to displace Boneh-Wahby.

That’s great. BTW, have you considered publishing on ePrint? ePrint tends to get much visibility within the cryptography and blockchain space than ResearchGate.

On page 3 of the Boneh-Wahby paper there is a section titled “Hash functions to curves as random oracles”. By “behaving like a random oracle” I mean that the hash function is indifferentiable from a random oracle.

BTW, have you considered publishing on ePrint?

Yes, I also submitted the text to ePrint. It should be published in several days.

What do you consider a small degree?

Since \sqrt[3]{b} \not\in \mathbb{F}_{\!q} (i.e., there are no \mathbb{F}_{\!q}-points of order 2) for all curves used in practice, we can suppose that the degree d of an \mathbb{F}_{\!q}-isogeny \varphi\!: E \to E_b is odd, where j(E) \neq 0. In this case, according to Vélu’s formulae we obtain

\varphi = \left( \dfrac{\varphi_0(x)}{\varphi_1(x)}, y\dfrac{\varphi_2(x)}{\varphi_3(x)} \right),

where \varphi_i are \mathbb{F}_{\!q}-polynomials such that

\deg(\varphi_0) = d, \qquad \deg(\varphi_1) = d-1, \qquad \deg(\varphi_2) = \deg(\varphi_3) = 3(d-1)/2

if I am not mistaken. Thus in general Horner’s method requires \approx 5d field multiplications in order to compute the image of \varphi. You decide for yourself whether it’s a lot or not.

1 Like