[curves] Is there an established name for the hardness assumption capturing twist security of a curve?

Sat Jun 13 13:37:28 PDT 2020

Hi Björn,

You don’t even really need a square root by the way, just a Jacobi symbol evaluation.  Jacobi symbol is slightly easier for most fields, but much easier for eg p224.  Also, if for some reason you’re using EGCD instead of FLT to divide (it’s faster but needs blinding for side channels), you can get the Jacobi symbol along the way using quadratic reciprocity, but you can’t take a square root that way.

For both Montgomery and SW curves there’s an extra simple algorithm to do this.  Depending on the ladder algorithm you’re using, it basically amounts to computing 1/Z while also checking the Jacobi symbol of Z; you usually do not have to solve for y or even y^2.

Lemma for Montgomery curves: if a point on a Montgomery curve is even (i.e. twice another point) then it necessarily has a square x-coordinate.  If it is even and on the twist, then x is either 0 or nonsquare; the 0 case is an error (at least for RFC 7748, dunno about CPace).  This can be seen eg from the doubling formula:

Let Cy^2 = x(x^2 + Ax + 1), where for the curve C=1 is square, but for the twist it isn’t square.

Then x_dbl = (x^2 - 1)^2 / (4x (x^2 + Ax + 1)) = (x^2 - 1)^2 / (4 C y^2)

The output of the Montgomery ladder is always even if you’re clearing the cofactor.  So what you want to compute is X/Z, but also check that X/Z is square and nonzero.  This can be computed as X^2 / XZ.  Compute tmp = (XZ)^((p-3)/2).  Then the Jacobi symbol J = tmp * XZ; if J == 1 then the point is on curve and tmp = 1/XZ.  If j == -1 then the point is not on the curve.

If you’re using the usual Montgomery ladder (as copied into eg RFC 7748), it’s even easier.  You can see that X is always computed as the square of something, so it’s only Z that might not be square.  So you don’t need to use XZ as above, you can just do it with Z.  Compute tmp = Z^((p-3)/2), J = tmp * Z, output = X*tmp = X/Z if J==1 and error otherwise.

This fact is part of the motivation for Decaf / Ristretto.

For odd-order short Weierstrass, all points are even and the lemma doesn’t hold anyway.  However, depending on the scalarmul algorithm, you likely have a very similar trick.  For example, if you’re using a Jacobian co-Z Montgomery ladder for x-only arithmetic, then the coordinates will be something like (X1 : X2 : Z^2) and (Y1 : Y2 : Z^3), where Z is unknown.  Indeed for x-only, Z can’t be known: it depends on y but Z^2 doesn’t.  The ladder setup uses this fact: you can compute the Jacobian X and Y without knowing y itself, but only y^2 and Z^2.  At the end, you solve for W := Z^2 and divide to get the output X-coordinate.  There are different ways to solve for Z^2 depending on the exact form of the ladder.

The key point is that your Jacobian Y-coordinates are part of the ladder state, so they're in the field by definition.  W = Z^2 is in the field since you solve for it using add/sub/mul, and X and x are in the field whether you’re on the curve or the twist.  But  the underlying y is in the field iff Z^3 is in the field, which is true if and only if W = “Z^2” you solved for is really square.  You could take the full square root W and recover the two possible y-coordinates, but if you only want x then you can just invert and check the Jacobi symbol using the exact same math as above.

The fastest publicly known SW ladder is my work at https://eprint.iacr.org/2020/437.pdf <https://eprint.iacr.org/2020/437.pdf>, but (and this is not legal advice) there is a patent warning so you may want to consider the slightly slower https://ches.2017.rump.cr.yp.to/a1933e522beb16591d9dc8e373ad7079.pdf <ttps://ches.2017.rump.cr.yp.to/a1933e522beb16591d9dc8e373ad7079.pdf> instead.

As for the origin of the inverse square root trick, I believe that a special case of it for p==5 mod 8 is in the Ed25519 paper, and the general case is in my paper at https://eprint.iacr.org/2012/309.pdf <https://eprint.iacr.org/2012/309.pdf>.  But someone else might have found it earlier or independently.

Regards,
— Mike

> On Jun 12, 2020, at 11:28 AM, Björn Haase <bjoern.m.haase at web.de> wrote:
> 
> Hello Rene,
> 
> yes that's true. If the check is done after a scalar multiplication,
> this comes at almost no complexity adder, however still some additional
> code. (Actually, IIRC it's not detailed in the elligator paper but in
> the Ed25519 paper). In fact, I did already use it for speeding up
> Elligator2.
> 
> Thank's for the pointer.
> 
> Björn
> 
> 
> Am 12.06.2020 um 16:51 schrieb Rene Struik:
>> Hi Bjorn:
>> 
>> If one computes R:=k*Q, where the input point has coordinates
>> Q:=(x,y), one usually has to perform a conversion from projective
>> coordinates to affine coordinates, via inversion in GF(q). Checking
>> whether a compressed point Q is on a curve requires a square root
>> computation in the same field. Combining both operations (inversion +
>> square root computation) can be done at essentially the cost of the
>> square root computation. So, relative incremental cost is indeed
>> approximately zero, as suggested.
>> 
>> sqrt{a}, 1/b can be computed via 1/sqrt{a*b^2} = 1/b*sqrt{a) -->
>> 1/sqrt{a}, sqrt{a}, 1/b (I believe this was first mentioned by Icart
>> and also used in the Elligator paper)
>> 
>> I hope this helps.
>> 
>> Rene
>> 
>> On 6/12/2020 10:05 AM, Björn Haase wrote:
>>> Hi Rene,
>>> 
>>> >at negligible incremental cost (a few field multiplies) even if one
>>> implements ECDH using
>>> >Montgomery ladders and is only given the x-coordinate of a point
>>> 
>>> If you transfer the full point coordinates the cost indeed might be
>>> small. If you spare the communication bandwidth and transfer the
>>> x-coordinate only, you need code and computation for a full field
>>> exponentiation (square root). IMO, this is worth to be spared, at least
>>> on small targets.
>>> 
>>> Yours,
>>> 
>>> Björn.
>>> 
>>> Am 12.06.2020 um 14:55 schrieb Rene Struik:
>>>> Hi Bjorn:
>>>> 
>>>> Why not simply check whether the point is on the curve? Within the
>>>> context of DH schemes, this is trivial to do and comes at negligible
>>>> incremental cost (a few field multiplies) even if one implements ECDH
>>>> using Montgomery ladders and is only given the x-coordinate of a point.
>>>> 
>>>> Best regards, Rene
>>>> 
>>>> 
>>>> On 6/12/2020 3:32 AM, Björn Haase wrote:
>>>>> Hi to all,
>>>>> 
>>>>> I am currently re-working the security proof for CPace
>>>>> https://datatracker.ietf.org/doc/draft-haase-cpace/ such that tight
>>>>> computational bounds for the adversary could be given.
>>>>> 
>>>>> In this context, I am still looking for the name and defininition
>>>>> of the
>>>>> problem that captures the feature of "twist security", i.e. for the
>>>>> tight reduction for the case where an active adversary passes a
>>>>> point on
>>>>> the twist to a honest party.
>>>>> 
>>>>> I did not find an established security notion so far that captures
>>>>> this
>>>>> property so that I could re-use it in the re-worked proof.
>>>>> I'd coin it "exponential transfer" and formulate it in the way:
>>>>> Given two groups (modulo negation) J and J' with co-factors c and
>>>>> c' in
>>>>> which the discrete logarithm problem is assumed to be hard in the
>>>>> prime
>>>>> order subgroup and with c' = n * c and d=max(c,c'), the *exponential
>>>>> transfer problem * is defined as:
>>>>> Given two points B,X = B^(d * x) in J: Provide two points B' and X' in
>>>>> J' with X' = B'^(d * x).
>>>>> I'd like to avoid having to newly define it myself. I would very much
>>>>> appreciate if anybody could give me a pointer.
>>>>> Yours,
>>>>> Björn
>>>>> _______________________________________________
>>>>> Curves mailing list
>>>>> Curves at moderncrypto.org
>>>>> https://moderncrypto.org/mailman/listinfo/curves
>>>> 
>>>> 
>> 
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20200613/ebe15da0/attachment.html>