[Cryptography] "Post-quantum RSA" (Julien Bringer)

[L Jean Camp]

It seems the argument is for RSA as opposed to ECC RSA. It does not address
lattice crypto at all.

In terms of recommendations, it seems more like a transition proposal
towards lattice crypto while we know that there are superior factoring
attacks, not a pre/post crypto proposal per se.

In that, it seems like a good transitional technology with all the caveats
applied to transitional solutions.


Message: 1
Date: Tue, 23 May 2017 20:50:33 +0200
From: Julien Bringer <julien.bringer at gmail.com>
To: Jerry Leichter <leichter at lrw.com>
Cc: Cryptography <cryptography at metzdowd.com>
Subject: Re: [Cryptography] "Post-quantum RSA"
Message-ID:
        <CAALJo_BkDd4u9xLhGpO5EKeWU=pfs2oticUg=tQfx8RViWdiYw at mail.gmail.com>
Content-Type: text/plain; charset="utf-8"

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-0001.html>

Prof. L. Jean Camp
http://www.ljean.com

Make a Difference
http://www.ieeeusa.org/policy/govfel/congfel.asp
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20170524/905030da/attachment.html>