Subject: [CFRG] Questions regarding draft-irtf-cfrg-hash-to-curve-10

From: Björn Haase <[email-masked]>
Date: Wed, 2 Dec 2020 11:58:47 +0000

Hello Riad, Hello Christopher,

As requested, I have filed an issue in the GIT draft regarding an update of our CPace security analysis.

I am currently reviewing one other aspect regarding the hash_to_curve construction, where the result of two mappings is added.

hash_to_curve(msg)
Input: msg, an arbitrary-length byte string.
Output: P, a point in G.

Steps:
1. u = hash_to_field(msg, 2)
2. Q0 = map_to_curve(u[0])
3. Q1 = map_to_curve(u[1])
4. R = Q0 + Q1 # Point addition
5. P = clear_cofactor(R)
6. return P

The important aspect would be, that the result P comes from a uniform distribution.

I am aware of a result from Coron, Icart, brier and Madore “Efficient Indifferentiable Hashing into Ordinary Elliptic Curves.” where they saw the need for using rather something of the type of
P = Q0 + x * Q1.

In “Indifferentiable Deterministic Hashing to Elliptic and Hyperelliptic Curves” there is a discussion that, even if uniformity could not be guaranteed, at least some weaker property of “well-distributed encodings” holds, which they show for SWU.

https://eprint.iacr.org/2010/539.pdf

I am having now the questions: Are you aware of a result that extends this to Elligator2? If I understood the paper correctly, the case of SSWU should be covered as part of the general properties of SWU. The guarantees seem to be linked to the property of the map that it is “well distributed” (where I did not yet understand the full implication of the character sums definition …).

Yours,

Björn.

Mit freundlichen Grüßen I Best Regards 

Dr. Björn Haase 

Senior Expert Electronics | TGREH Electronics Hardware

Endress+Hauser Liquid Analysis

Endress+Hauser Conducta GmbH+Co.KG | Dieselstrasse 24 | 70839 Gerlingen | Germany
Phone: +49 7156 209 377 | Fax: +49 7156 209 221
[email-masked] |  www.ehla.endress.com 

Endress+Hauser Conducta GmbH+Co.KG
Amtsgericht Stuttgart HRA 201908
Sitz der Gesellschaft: Gerlingen
Persönlich haftende Gesellschafterin:
Endress+Hauser Conducta Verwaltungsgesellschaft mbH
Sitz der Gesellschaft: Gerlingen
Amtsgericht Stuttgart HRA 201929
Geschäftsführer: Dr. Manfred Jagiella

Gemäss Datenschutzgrundverordnung sind wir verpflichtet, Sie zu informieren, wenn wir personenbezogene Daten von Ihnen erheben.
Dieser Informationspflicht kommen wir mit folgendem Datenschutzhinweis (https://www.endress.com/de/cookies-endress+hauser-website) nach.

Disclaimer: 

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you receive this in error, please contact the sender and delete the material from any computer. This e-mail does not constitute a contract offer, a contract amendment, or an acceptance of a contract offer unless explicitly and conspicuously designated or stated as such.

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 2 Dec 2020 13:36:53 +0000

Hi Björn,

At some point (2013?) I wrote up an article on uniform hashing specifically for Elligator 2, but it got rejected for being too similar to previous work, and I never bothered to post it on ePrint.  I’ll do that now.  You can find proofs for two constructions in the paper cited below, one of which is hash-twice-and-add.

https://www.shiftleft.org/papers/indifferentiable/

It may also be possible to show that Elligator 2 is well-distributed, but this paper shows directly that hash-twice-and-add works.

Cheers,
— Mike

PS: Mods, feel free to reject my previous attempt at this message, which is held because it has a PDF attached to it.

> On Dec 2, 2020, at 11:58 AM, Björn Haase <[email-masked]> wrote:
> 
> https://eprint.iacr.org/2010/539.pdf <https://eprint.iacr.org/2010/539.pdf>
>  
> [email-masked] <mailto:[email-masked]> |  www.ehla.endress.com <http://www.ehla.endress.com/> 
> 
> Dieser Informationspflicht kommen wir mit folgendem Datenschutzhinweis <https://www.de.endress.com/de/cookies-endress+hauser-website> nach.
> 
>  
> Disclaimer: 
> 
> The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged
> material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities
> other than the intended recipient is prohibited. If you receive this in error, please contact the sender and delete the material from any computer.
> This e-mail does not constitute a contract offer, a contract amendment, or an acceptance of a contract offer unless explicitly and conspicuously designated or stated as such.
> 
>  
> _______________________________________________
> CFRG mailing list
> [email-masked] <mailto:[email-masked]>
> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>

---

From: Björn Haase <[email-masked]>
Date: Wed, 2 Dec 2020 22:00:52 +0100

Hi Mike,

thank you! That was exactly what I was looking for.  Once the paper gets on the eprints, I think that it should be added to the list of references in the Hash2Curve draft.

I'll be adding a corresponding feature request at the github repository.

Yours,

Björn.

Gesendet: Mittwoch, 02. Dezember 2020 um 14:36 Uhr

Von: "Mike Hamburg" <[email-masked]>

An: "Björn Haase" <[email-masked]>

Cc: "[email-masked]" <[email-masked]>

Betreff: Re: [CFRG] Questions regarding draft-irtf-cfrg-hash-to-curve-10

Hi Björn,

Cheers,

— Mike

hash_to_curve(msg)

Output: P, a point in G.

Steps:

5. P = clear_cofactor(R)

6. return P

P = Q0 + x * Q1.

Yours,

Björn.

Dr. Björn Haase

Endress+Hauser Conducta

Verwaltungsgesellschaft mbH

Dieser Informationspflicht kommen wir mit folgendem Datenschutzhinweis nach.

Disclaimer:

CFRG mailing list

[email-masked]

https://www.irtf.org/mailman/listinfo/cfrg

_______________________________________________ CFRG mailing list [email-masked] https://www.irtf.org/mailman/listinfo/cfrg

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 2 Dec 2020 21:14:30 +0000

Great. The reference was accepted to ePrint remarkably quickly (eg hanks editors!), as

https://eprint.iacr.org/2020/1513

Cheers,
— Mike

> On Dec 2, 2020, at 9:01 PM, Björn Haase <[email-masked]> wrote:
> 
> Hi Mike,
>

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 2 Dec 2020 22:32:11 +0000

Sorry for the spam.  That should of course read “thanks editors!”.  — Mike

> On Dec 2, 2020, at 9:14 PM, Mike Hamburg <[email-masked]> wrote:
> 
> https://eprint.iacr.org/2020/1513 <https://eprint.iacr.org/2020/1513>
> 
> Cheers,
> — Mike
> 
>> https://www.shiftleft.org/papers/indifferentiable/ <https://www.shiftleft.org/papers/indifferentiable/>
>>  
>> On Dec 2, 2020, at 11:58 AM, Björn Haase <[email-masked] <mailto:[email-masked]>> wrote:
>>  
>> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>_______________________________________________ CFRG mailing list [email-masked] https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>_______________________________________________
> CFRG mailing list
> [email-masked]

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 2 Dec 2020 13:21:42 +0000

Hello Björn,

At some point (2013?) I wrote up an article on uniform hashing specifically for Elligator, but it got rejected for being too similar to previous work, and I never bothered to post it on ePrint.  I’ll do that now.  Please find attached an analysis of two constructions, one of which is hash-twice-and-add.

Regards,
— Mike