[Cryptography] Mathematics of variable substitutions?

[Watson Ladd]

On Sat, Apr 30, 2016 at 4:17 AM, Bill Cox <waywardgeek at gmail.com> wrote:
> 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:

See any book on algebraic geometry which proves the genus is a
birational invariant.

>
>     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
>
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.