[curves] Another try at point compression

[Michael Hamburg]

> On Dec 26, 2014, at 5:41 AM, Robert Ransom <rransom.8774 at gmail.com> wrote:
> 
> On 12/17/14, Robert Ransom <rransom.8774 at gmail.com> wrote:
> 
>> In my opinion, the main disadvantage of your previous sgn(v)/sqrt(u)
>> format was that it absolutely required one exponentiation to pack each
>> point.
> 
> I was wrong about this.  As the last step of Montgomery-ladder scalar
> multiplication by an odd scalar, sqrt(u) can be recovered up to sign
> using the Montgomery-form differential addition formulas (just as for
> the isogeny-based Edwards x/y point format that you developed in
> January) and one batchable inversion, and the sign can be recovered
> using one Legendre symbol per point.

Yes.  Though if you want to combine this with fast twist rejection, you might have to go with parity instead of Legendre symbol, and in that case you do need to solve for y using a square root.

> And at the end of *any* Edwards-form operation, one can choose P and Q
> for some fixed P-Q of sufficiently large order (P-Q should probably be
> the standard basepoint) such that P+Q is the desired output, convert P
> and Q to projective Montgomery form (on the same curve; no isogeny
> needed), and do the same incomplete differential addition, inversion,
> and Legendre symbol as for a Montgomery-ladder output.
> 
> 
> Robert Ransom

I’m pretty sure this doesn’t work and can’t work.

The reason it doesn’t work is that if P+Q=R is the desired output, and P-Q=B is the base point, then P = (R+B)/2 and Q = (R-B)/2.  If you try to shuffle it in some other way, you will find yourself needing sqrt(u) for the point (P-Q), which won’t be known in advance if P-Q isn’t the base point or similar.

The reason it can’t work is that this would yield a rational function with coefficients in F that evaluates to sqrt(u), but R isn’t even then sqrt(u) isn’t in F.

Cheers,
— Mike