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

[Björn Haase]

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