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@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves
_______________________________________________
Curves mailing list
Curves@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves
