9

The general rule for curves is given in; 2003 - Validation of Elliptic Curve Public Keys by Adrian Antipa,Daniel Brown, Alfred Menezes, and René StruikScott Vanstone They defined a point is valid if $P \neq \mathcal{O}$ The $x$ and $y$ coordinates of $P$, $x(P),y(P)$ are valid elements of the field. $P$ satisfies the curve equation - against the twist ...


5

Regarding the [B] and [C] parts of the question per the comments: I'm not sure how exactly did Mike Hamburg find the curve, but from what I know it's usually easier to find the order of the matching Montgomery curve. Recall that Montgomery curves have the form $By^2 = x^3 + Ax^2 + x$. If $B$ is 1, then it fits into the generalized Weierstrass form, and most ...


4

In Tsiounis and Yung's proof of the IND-CPA semantic security of El Gamal, the only assumption made is that the decisional Diffie-Hellman problem is hard. The proof transfers easily to any group where the decisional Diffie-Hellman problem is hard, including we believe (non-pairing-friendly) elliptic curve groups. Similarly all El Gamal instantiations are ...


4

Do your experiments count points at infinity? When $d$ is a quadratic nonresidue over $\mathbb{F}$, the curve $y^2 + x^2 = 1 + d x^2 y^2$ has no points at infinity over $\mathbb{F}$. But if $-1$ is also a quadratic nonresidue, then the curve $y^2 - x^2 = 1 - d x^2 y^2$ has two of them, roughly of the form $(\pm\sqrt{-1/d}, \infty)$.


2

Yes! Good observation! Although note that the original Helios paper by Ben Adida does not mention such implementation details, i.e., on which curve to instantiate the ElGamal encryption scheme. Your observation basically stems from the fact that the decisonal Diffie-Hellman (DDH) assumption does not hold on pairing-friendly curves. On the other hand, one ...


2

Although it is not forward secure against client-side compromise (i.e. disclosure of the user agent's long term private key), it is forward secure against server-side compromise (i.e. disclosure of all information available to the server). Thus, for example, if ownership of the application server is transferred from one company to another and the user's ...


1

If you read all of the RF 8032 you will see that there is a compression (endcodings) of the points. def point_compress(P): zinv = modp_inv(P[2]) x = P[0] * zinv % p y = P[1] * zinv % p return int.to_bytes(y | ((x & 1) << 255), 32, "little") Compression just stores the sign and restores it back with this information def ...


1

The procedure that Mike Kaye suggested works; the other method would be to select a random value, and then use a Hash-to-Curve method to translate that random value to a point; they have been designed so that the order of that generated point is unknown.


1

Pick a random $x$ value. Calculate $y^2 = x^3+ax+b \bmod p$. Then try to form $y$ by taking the square root $\bmod p$. If the square root fails then no $(x,y)$ pair exists on the curve. If the square root works, flip a coin; if tails form $y = p-y \bmod p$. This is how public key compression works. Only the low bit of y is saved. Form $y^2$, take the square ...


Only top voted, non community-wiki answers of a minimum length are eligible