Fouque and Tibouchi method: relwork / attribution issue

[kwantam]

Hi folks,

Thanks for the hard and excellent work on this!

There are a couple small issues with the discussion of hashing to pairing-friendly curves.

1. I notice in the current draft that the section discussing the work of Fouque and Tibouchi at Latincrypt 2012 does not correctly attribute the work. The FT12 paper is clear that the map the authors describe is an instantiation of the Shallue--van de Woestijne method, with constants selected in a way that is convenient for Barreto-Naehrig curves. So a cite of S--vdW (ANTS 2006) would probably be appropriate here.

2. It's probably important to point out in this section that the map is undefined when u = 0 and when u = sqrt(-1-B). The first case can happen for any curve. The second case can only happen when (-1-B) is square. For BN curves this will never be true, but for BLS curves is can and likely will be. (As a specific example, -1-B is square for BLS12-381, so the map as described is undefined at +/-sqrt(-5).)

In fact, the second comment might be true more generally. A brief search of the document doesn't turn up any instances discussing what to do if/when the map is undefined. This is probably important, since in practice many of these maps will have some undefined inputs, and it would be unfortunate if different implementations diverged in their behavior.

Since the document appears to be encouraging constant-time implementations, it's not clear that there's a good blanket recommendation that would apply to every map. So it might be useful to think about how to handle undefined behavior on a map-by-map basis, in a way that is amenable to constant-time implementations. I'm happy to help out with this.

[kwantam]

I moved the undefined cases question to its own issue #103