Elliptic curve isogeny

A few days a go (the 9th of November) a new patch about elliptic curves on GnuPG had been published. With two month delay since Mikael sent the code to me... As I read in the esr's book this is long longer time than acceptable.I'm sorry.

Now it's time to retrieve the projects. It is necessary to recuperate the gumstix development and also this year I will do my master degree research project. Against about elliptic curves. But what I said is really generic. I have some ideas, that I wanna write in this blog to be used as a brain storming to specify what is able to do and discard something else. Today is the turn elliptic curve isogeny.

Without speak on mathematics, and as far as I know, if you have a cryptoanalyst against finite fields and your paranoia says you that your privacy could be compromised, the only option that you have is increase your keylength... Use a bigger RSA or ElGamal key. Over elliptic curves you have one option before this: you can change the elliptic curve (and propose the elliptic discrete logarithm problem over a complete new one field). Nothing that the cryptoanalist computes for the old field can be used here.

But the cost to generate a new curve every key generation is hard. There are too much proprties and characteristics to test and be sure that this curve have good cryptographyc properties. One way to generate a new curve with a guarantee that it has cryptographyc characteristics is to perform some isogeny transformations to one curve that you know that it has this properties.

There exist algorithms to obtain a graph where the nodes represents elliptic curves and the edges represents an isogeny transformation. I don't need to go so far to know about isogenies, in the same university research group with I am studying they are specialists on this. For a long time a go I am listening conversations talking about this transformations an its advantages. The data structures that this isogeny transformation creates receive the name volcanus, and a join of volcanus receive the name of cordillera.

But! If the attacker knows the steps that you did in the volcanus to obtain your new isogeny curve, and it has good knowledge on isogenies transformation, it is possible to 'migrate' all the computation work that before I said that should be not useful, to the new field and continue the attack. This means that the isogeny could only generates more work to the attacker but it maybe doesn't improve the security.

An option, is to perform the transformation in secret. Generate a way in the volcanus during the key generation, from then you use the new elliptic curve and forget the relation with the one from it came... If the attacker is not able to stablish the path from one to the other, the system is secure.

Long time a go I was talking about this with Mikael, and he shows me that there are many people in the world that propose to use a public key isogeny cryptosystem, where the secret key is precisely this path in the volcanus.

Then the question is: Are we complicating so much the problem? In the low level we need to be careful with the AES symmetric cryptoanalysis. In the centre we have to beware if some algorithm better that pollard's-rho has been discovered. An then a third front we will have this transformation that could be grateful to reset a hole smartcard cryptosystem.

Yes, it is a grate thing to have the possibility to reset a institution smart card system without increase the keylength but with a restablishment of the security against an attacker.