Re: [CFRG] Comment on draft-irtf-cfrg-hash-to-curve-10

[Daira Hopwood <[e-mail]>]

On 22/04/2021 17:44, Riad S. Wahby wrote:
> Hello Daira,
> 
> Thanks for the comments. They're very helpful! A few responses below.
> 
> By the way, in your original email (which I didn't respond to at the
> time---very sorry!), you ask why we preclude Z = -1 for SSWU. The
> reason is that this specific case appears to be covered by a patent.
> (This is true more generally of the Z selection code, which is
> slightly more complicated than would be necessary absent the patent.)
> We don't explain this in the document because IETF doesn't want
> discussion of IPR in the documents, as I understand it.
> 
> Daira Hopwood <[e-mail]> wrote:
>> This is not just an editorial comment. The implementations in the
>> appendix are indeed technically constant-time, but the map_to_curve
>> for SSWU, for example, uses a square root, a quadratic residue test
>> (which is essentially the same cost as a square root), and an inversion.
>> A good implementation should only require one square root and no
>> inversions, when producing an output point in projective, e.g.
>> Jacobian, form.
> 
> I think you're talking about the straight-line code in Appx. F, right?
> 
> You're obviously right that it's possible to do much better when
> working in projective coordinates. So maybe another way to state
> the objection is, there's no point including Appx. F (or maybe even
> what's in the body text) when everyone should just use code roughly
> like what's in Appx. G. Is that right?

As I already pointed out, the code in Appendix G only covers q = 3 (mod 
4), 5 (mod 8), and 9 (mod 16).

So no, I am not saying that people should use the code in Appendix G.
That code is wildly overcomplicated. I am saying that there is actually
no need to specialize map_to_curve for different fields.

I guess I will have to spell out the changes I'm suggesting:

* Add a section describing sqrt_ratio, with the following specification:

   Let h be some fixed nonsquare in Fq. Define sqrt_ratio for
   u ∊ Fq and v ∊ Fq* as:

     sqrt_ratio(u, v) = (true, sqrt(u/v)),    if u/v is square in Fq
                      = (false, sqrt(h*u/v)), otherwise.

   Include some explanatory text saying how to implement this naively,
   and how to implement it efficiently. (It's the same function described
   at https://ristretto.group/formulas/invsqrt.html , generalized to
   an arbitrary field, with v ≠ 0. A constant-time implementation has
   roughly the same cost as a full-width fixed-scalar multiplication.
   Square root algorithms like Tonelli-Shanks and [Sarkar2020] can be
   straightforwardly modified to sqrt(h*u/v) if u/v is not square with
   almost no additional cost, as I'm sure you know.

* Replace the algorithm in section 6.6.2 with the following, which is
   compatible with the existing specification:

   Let a and b be the parameters of the curve E/Fq : y^2 = x^3 + ax + b.
   Precompute θ = Z/h in Fq.

   Define map_to_curve(u) for u ∊ Fq as follows:

     Zuu = Z·u^2
     ta = Zuu^2 + Zuu
     x1n = b·(ta + 1)
     xd = a·CMOV(Z, -ta, ta == 0)
     U = (x1n^2 + a·xd^2)·x1n + b·xd^3
     x2_num = Zuu·x1_num
     (is_gx1_square, y1) = sqrt_ratio(U, xd^3)
     y2 = θ·Zuu·u·y1
     xn = CMOV(x2n, x1n, is_gx1_square)
     y' = CMOV(y2, y1, is_gx1_square)
     y = CMOV(-y, y, u mod 2 == y mod 2)
     return the point on E with affine coordinates (xn/xd, y).

   (Don't take my word that it is compatible; check it! See
   https://github.com/zcash/pasta/blob/master/hashtocurve.sage#L204-L293
   if needed.)

* Delete Appendix G.2 and references to it, and renumber.

* Replace Appendix F.2 with a straight-line implementation of the
   map_to_curve algorithm above (i.e. one that makes temporaries
   explicit).


Notice that:

- This algorithm doesn't explicitly require Jacobian coordinates. It's
   defined only in terms of field arithmetic, apart from the last step
   constructing the output point. I would expect implementors to use
   Jacobian coordinates, but other choices (including affine, at the
   cost of an inversion) are possible. A note about how to construct the
   point in Jacobian coordinates might be useful.

- If an implementor doesn't care about performance then a naive
   implementation of sqrt_ratio using constant-time Tonelli-Shanks is
   possible, with the same performance as the original algorithms.


I will also throw in my two-penneth on the issue of the hash returning
the zero point. Yes, it's an issue for some protocols, and in particular
it was an issue for our DiversifyHash function in Zcash. It is not good
practice to just ignore exceptional cases even when they occur with
negligible probability; for a start, it makes a protocol more difficult
to audit.

We got around this just by replacing the zero point with a different
precomputed point, which is an output of the hash on a input that
otherwise cannot occur:

   https://zips.z.cash/protocol/nu5.pdf#concretediversifyhash

(Note: this is *not* equivalent to just picking some arbitrary point.
It must be a point that we verifiably could not choose to collide with
some other output of the hash.) The replacement can easily be done in
constant time.

> Two concerns here. First, I would strongly prefer to keep the body
> text in terms of affine coordinates, to avoid mixing implementation
> detail with high-level description. Moreover, if we did talk about
> projective coordinates throughout, we'd likely end up talking about
> different projective systems for different curve shapes, which would
> be confusing for many readers.

This is not an issue, as I explained above.

> Second, I'm not totally convinced that everyone who will use this
> document will want to use projective coordinates.

Also not an issue. They pay no complexity or other cost.

> (Perhaps, though, we should mention projective coordinates explicitly
> in forward-refs from Section 6 and Appx. F to Appx. G.)
> 
> Meanwhile, someone who wants a simple, straight-line function that's
> totally generic and doesn't have to be super fast is probably quite
> happy with what's presented in Appx. F. Isn't this a user we want
> to support, too?

We would be supporting them. The algorithm above is no more complicated
than what is currently in Appendix F.2 (and significantly less
complicated, while being no less efficient, than Appendix G).

> I guess we might worry about the middle case---a person who's trying
> to implement something that's fast, but doesn't know they need
> projective coordinates to do that and doesn't notice the very clear
> "look at Appendix G!" signposting.

If they have a 2-adic field, they can't use Appendix G. As I said,
2-adic fields are commonplace in applications using FFTs. They're not
"weird" or "ugly" (why would one even use such terms about a field?)

Besides, there is *no downside* to making the algorithm work efficiently
for 2-adic fields. None at all.

>> Furthermore, the algorithm for q = 9 (mod 16) is 70 steps, when
>> it can actually be written for *any* field in less than 20 steps.
> 
> Unless I'm missing something, this is only true if we take divsqrt()
> as a one-liner, no? In contrast, the 70-step algorithm essentially
> has divsqrt() inlined.

divsqrt (or sqrt_ratio) is a much simpler thing to test and optimize
if it's independent of map_to_curve. This is a real explanatory
improvement, not just "sweeping complexity under the rug".

> (And assuming we go this way, I'd certainly take you up on your
> offer of an implementation of divsqrt that works for general fields,
> if you're still willing to provide it!)

I can do that, but it's just implementing [Sarkar2020] and the hint
in [BDLSY2012] section 5 for the general case.


[WB2019]     https://eprint.iacr.org/2019/403
[Sarkar2020] https://eprint.iacr.org/2020/1407
[BDLSY2012]  https://ed25519.cr.yp.to/ed25519-20110705.pdf

-- 
Daira Hopwood