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

[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
>>
>>

-- 
email: rstruik.ext at gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867