[Cryptography] "Post-quantum RSA"

[Julien Bringer]

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!

Julien
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20170523/868fe94d/attachment.html>