New faster indifferentiable hash functions to elliptic curves, including BLS12-381

[Dimitri-Koshelev]

Hello, H2C team.

My name is Dimitri Koshelev. I am a post-doc in Paris in the field of elliptic cryptography.

Based on quite complicated interesting mathematics, I constructed new faster hash functions to elliptic curves (indifferentiable from a random oracle). Some of my works have already been checked and published. For example, in this one I extend the simplified SWU encoding to all elliptic curves of j-invariant 1728. Recently, I also wrote new texts dedicated to faster hashing to some elliptic curves of j-invariant 0, including BLS12-381. Let me give here the links: hashing to the group G1 and hashing to the group G2. These texts are under review in some scientific journals at the moment. However, I verified all my formulas in the computer algebra system Magma.

I would be very grateful to you, if you could read at least abstracts of my articles and give your opinion. Is this useful for your draft ?

Thanks in advance. Best regards, Dimitri.

[chris-wood]

Thanks for filing this issue, @dishport! This seems like a great contribution to the field. I think we can pursue adding suites that use your new hashing algorithms without blocking this document.

@kwantam. what do you think? (Tagging @daira for some eyes, too.)

[kwantam]

Is the idea that there would be a separate document that specifies the new mapping algorithms?

[Dimitri-Koshelev]

You are welcome, @chris-wood!

For the sake of completeness, let me add. Recently, I also wrote several texts (https://eprint.iacr.org/2021/1034 and https://eprint.iacr.org/2021/1082) improving my previous results even more.

Best regards.

[chris-wood]

@kwantam yeah, that's what I'm thinking.

[armfazh]

@dishport could you please clarify whether your method improves over the ones currently described in the draft, e.g. reduces the number of operations, or it covers more curves with a unified implementation. Those details will be great to better assess the method.

[Dimitri-Koshelev]

@armfazh, yes, the new methods improve the ones currently described in the draft if j-invariant of an elliptic curve equals 0 or 1728. All the new methods require fewer exponentiations in the basic (prime) field Fp. More precisely, I constructed

1. a hash function H to any elliptic curve of j-invariant 1728 (i.e., y^2 = x^3 + ax) with the cost of 1 square root in Fp (resp. 2 square roots to make H indifferentiable). The same is true for elliptic curves of j-invariant 0 (i.e., y^2 = x^3 + b) having a small divisor of the Frobenius trace (e.g., the curves BN512 and BN638 from some international standards of pairing-based cryptography). By the way, the smallest degree of an Fp-isogeny to BN512 (resp. BN638) is equal to 1291 (resp. 1523);

2. an indifferentiable hash function to elliptic curves of j-invariant 0 whose the coefficient b is a quadratic residue in Fp (e.g., BLS12-381 E1 whose b = 4) with the cost of 1 cubic root in Fp (instead of 2 square roots). Moreover, I checked that the sliding window method (at least for BLS12-381) gives a quite small addition chain to compute a cubic root. Its length is even slightly smaller than the length of the addition chain for a square root in Fp.

[mratsim]

2. Its length is even slightly smaller than the length of the addition chain for a square root in Fp;

Nitpick for @dot-asm, I have an addition-chain of length 449 operations for sqrt instead of 457 operations in BLST.

[kwantam]

Nitpick for @dot-asm, I have an addition-chain of length 449 operations for sqrt instead of 457 operations in BLST.

Nice! Did you find this manually, or did you use a tool (and if so: is it public?)?

[mratsim]

I used @mmcloughlin addchain package https://github.com/mmcloughlin/addchain

[daira]

This seems like a great contribution to the field. I think we can pursue adding suites that use your new hashing algorithms without blocking this document.

I agree.

[Dimitri-Koshelev]

https://link.springer.com/article/10.1007/s10623-022-01012-8 Hi. My article about hashing to the subgroup G1 is published since yesterday in Designs, Codes and Cryptography.