<div dir="ltr"><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, May 23, 2017 at 2:50 PM, Julien Bringer <span dir="ltr"><<a href="mailto:julien.bringer@gmail.com" target="_blank">julien.bringer@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><span class=""><br><div class="gmail_extra" dir="auto"><br><div class="gmail_quote">Le 23 mai 2017 3:05 PM, "Jerry Leichter" <<a href="mailto:leichter@lrw.com" target="_blank">leichter@lrw.com</a>> a écrit :<br type="attribution"><blockquote class="m_-5216990637142323671quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">"Abstract: This paper proposes RSA parameters for which (1) key generation, encryption, decryption, signing, and verification are feasible on today's computers while (2) all known attacks are infeasible, even assuming highly scalable quantum computers. As part of the performance analysis, this paper introduces a new algorithm to generate a batch of primes. As part of the attack analysis, this paper introduces a new quantum factorization algorithm that is often much faster than Shor's algorithm and much faster than pre-quantum factorization algorithms. Initial pqRSA implementation results are provided."<br>
<br>
The proposed parameters lives in a curious area somewhere between theory and practice.  It isn't "theory" because it can't exclude the possibility of incrementally faster quantum algorithms for factoring that would destroy the tradeoffs.  (Then again, the same could be said of traditional pre-quantum RSA!).  On the other hand, it's not really practical because the recommended key sizes are around a terabyte - and they estimate an encryption/decryption time of about 5 days.<br>
<br>
Still, an interesting exploration of limits.<br>
<br>
Oh - the authors include Daniel Bernstein and Nadia Heninger. :-)<br>
<br>
                                                        -- Jerry<br><br></blockquote></div><br></div></span><div class="gmail_extra" dir="auto">Thanks for the pointer. Dan presented an overview at Eurocrypt rump session earlier this month. I was not sure they will come up with a paper. </div><div class="gmail_extra" dir="auto"><br></div><div class="gmail_extra" dir="auto">I like the message it conveys: do not focus only on using power of quantum computers for breaking schemes! </div></div></blockquote><div><br></div><div><div class="gmail_default" style="font-size:small">​RSA seems like a poor choice since the value of adding bits to the key seriously diminishes. 2048 bit RSA is only a little better than 1024, to get to 2^256 work factor ​you need 16Kb keys. </div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">The work factor curve gets really flat for RSA. Which is why ECC looks a better bet without quantum. Once you get into 'improved' quantum algorithms that are not Shor, I would expect the same tricks apply because the weakness of RSA at higher bits is determined by the structure of the underlying problem.</div></div><div><br></div><div> </div></div></div></div>