Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am not a mathematician, but I was wondering if the proposed proof of the abc conjecture (PDF) by Shinichi Mochizuki of Kyoto University would contain insights and mathematical tools that would lead to a weakening of elliptic curve cryptography.

share|improve this question
1  
Not exactly your specific question, but a similar question (RSA crypto) was recently asked on the Cryptography sister site. Maybe you'll have some luck there? crypto.stackexchange.com/questions/3780/… –  jtolds Sep 12 '12 at 17:12
1  
As far as I understand currently, Mochizuki's proof does not provide explicit/effective bounds, so no such implications are (immediately) expected. –  Andres Caicedo Sep 12 '12 at 17:20
    
@jtolds thank you for the crypto site link - much appreciated. –  Gary Rowe Sep 13 '12 at 9:32
1  
You may find this interesting: rjlipton.wordpress.com/2012/09/12/… –  Andres Caicedo Sep 14 '12 at 2:36
1  
A short update: I was actually wrong, and Mochizuki's approach can be made effective in fairly explicit ways. Whether it is correct is another issue, and I wouldn't be able to tell. Anyway, the following answer in MathOverflow discusses the effective bounds: mathoverflow.net/questions/106560/… –  Andres Caicedo Sep 27 '12 at 20:21
show 1 more comment

1 Answer 1

I'm not a crypto specialist, or even a number-theorist, so you should take this answer with a grain of salt: I don't see how a proof of ABC could possibly effect elliptic curve cryptography in practice.

First, the applications of elliptic curves to cryptography which I am aware of use curves over finite fields; ABC is a conjecture about curves over number fields.

Secondly, my main point: It is hard to imagine the proof of any long believed conjecture effecting cryptography in practice, because cryptographers routinely analyze their methods under the assumption that major number theoretic conjectures are true. If we proved ABC, or Birch--Swinnerton-Dyer, or the Generalized Riemann Hypothesis, we might become more confident that cryptographic protocols have the strengths they are claimed to have, but it wouldn't change our beliefs about the strengths of the protocols because they have already been analyzed under the belief that those conjectures hold.

In fact, I suspect that if one of these conjectures were false, it probably also wouldn't alter cryptographic practice much. I am less confident of this claim, but I think the experimental evidence for these conjectures is strong enough that any counterexample would probably be out of the range of curves used in cryptographic practice. I could definitely be wrong here. (To further clarify what I am thinking here, I don't mean that we have literally checked every curve in the relevant range. I mean it is my vague intuition that we have checked enough curves that it seems likely that, even if there were some counterexample, they would be very rare and thus easily avoided by choosing a random curve.)

Of course, it is possible that Mochizuki's claimed proof might introduce methods which lead to dramatically improved algorithms for computing (for example) elliptic curve discrete logarithms. Since very few people have understood his methods yet (and I am not one of them), it seems too soon to comment on this.

Apologies if this is all obvious to you!

share|improve this answer
    
+1 thanks for the analysis. I'll hold the question open for a while longer since it is the points raised in the your last paragraph that most concern me. –  Gary Rowe Feb 4 '13 at 16:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.