[Cryptography] "Post-quantum RSA"

[Phillip Hallam-Baker]

On Tue, May 23, 2017 at 2:50 PM, Julien Bringer <julien.bringer at gmail.com>
wrote:

>
>
> Le 23 mai 2017 3:05 PM, "Jerry Leichter" <leichter at lrw.com> a écrit :
>
> "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."
>
> 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.
>
> Still, an interesting exploration of limits.
>
> Oh - the authors include Daniel Bernstein and Nadia Heninger. :-)
>
>                                                         -- Jerry
>
>
> 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.
>
> I like the message it conveys: do not focus only on using power of quantum
> computers for breaking schemes!
>

​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.

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20170524/1be7e3a7/attachment.html>