[Cryptography] Mathematics of variable substitutions?

[Bill Cox]

I was hoping someone could point me in the direction of relevant
mathematics where we examine what equations can be converted to other
equations using variable substitutions, in ways that are efficiently
computable modulo a prime.  For example, we can easily convert an Edwards
curve into a circle with the substitution z^2 = x^2(1 + y^2).  However,
this substitution does not cause the Edwards addition law to become the
circle group addition law.  It becomes something cool, but the equations
are no more efficient than computing the regular Edwards addition law.

Has it been proven that no birational substitution can convert the Edwards
addition law into the circle group addition law?  The circle group addition
law is:

    x3 = x1x2 - y1y2
    y3 = x1y2 + x2y1

The Edwards addition law (with the origin properly set to (1, 0) rather
than (0, 1)) is:

    x3 = (x1x2 - y1y2)/(1 - d*x1y1x2y2)
    y3 = (x1y2 + x2y1)/(1 + d*x1y1x2y2)

These seem similar, so it is natural to ask if there is any efficiently
computable variable substitution that maps one to the other.  Clearly there
is such a substitution, since we know we can continuously morph the points
on the Edwards curve that are in the group to the points of the circle
group at least when the points do not wrap around the curve more than once,
which turns out not to be a significant limitation.

It looks like it is enough to do is map the doubling equation onto the
circle doubling equation, which is a simpler problem.  The Edwards point
doubling equation for points in the upper right quadrant can be expressed
in terms of the X coordinate like this:

    x2 = -(x^4 + 2x^2 - 1)/(x^4 - 2x^2 - 1)

Similarly, the circle group doubling equation is:

    x2 = 2x^2 -1

To be able to use the circle doubling equation to compute the Edwards
doubling equation, we have to find a function F(x) such that:

    2*F(x)^2 - 1 = F(-(x^4 + 2x^2 - 1)/(x^4 - 2x^2 - 1))

To work on this, I seem to need modular-arithmetic friendly identities such
as:

    F(a*b) = F(a)*F(b) when F(x) = x^q for any rational q
    F(a*b) = F(a) + F(b) when F(x) = log(x) (I assume I can solve DLP
efficiently, since I'm attacking ECC which uses small keys)
    F(a + b) = F(a)*F(b) when F(x) = g^x

This feels a bit like solving integrals, but I don't know the rules.  Where
can I read about this?

Thanks,
Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160430/e330ee88/attachment.html>