13
$\begingroup$

In the NIST post-quantum cryptography workshop, the round one submissions included pqRSA. If memory serves, this is an implementation of RSA using the product of a very large number of 4096-bit primes to protect against Shor's algorithm. It requires something like a terabyte of private key material. Why was this submitted to NIST given that its impracticality obviously disqualifies it?

Improve this question
$\endgroup$
5
  • 8
    $\begingroup$ The hard work was already done—the paper written, the code tested—so hey, why not submit it? $\endgroup$
    – Squeamish Ossifrage
    May 28, 2018 at 2:12
  • 1
    $\begingroup$ So just for fun (and perhaps some free analysis and publicity)? $\endgroup$
    – forest ♦
    May 28, 2018 at 2:14
  • 4
    $\begingroup$ I'm pretty sure it's a joke. I would post that as an answer, but I don't think there's any way to cite references to back up the claim. $\endgroup$
    – Ella Rose
    May 28, 2018 at 2:50
  • 3
    $\begingroup$ There is a second paper with the same title. cr.yp.to/papers/pqrsa-20170419.pdf One of my favorite quotes is "Our batch prime-generation algorithm suggests that, to help reduce energy consumption and protect the environment, all users of RSA—including users of traditional pre-quantum RSA—should delegate their key-generation computations to NIST or another trusted third party." I think there is some satire of NIST (it's rules, processes, and the NIST/NSA/RSA Dual-EC-DRGB scandal), the inefficiencies of PQ schemes, and the types of arguments and solutions non-experts make. $\endgroup$
    – Future Security
    May 28, 2018 at 23:04
  • 1
    $\begingroup$ My real favorite is "The question here is not whether quantum computers will be built, or will be affordable for attackers. This paper assumes that astonishingly scalable quantum computers will be built, making a qubit operation as inexpensive as a bit operation." People just assume quantum computers will scale linearly with effort. Or even exponentially with effort, like Moore's law. PQ hype tends to totally ignore the energy requirements, run time, or engineering challenges. Which will be first, the crypto-apocalypse or cold fusion at home? (The triple encryption suggestion is fun too.) $\endgroup$
    – Future Security
    May 28, 2018 at 23:22

2 Answers 2

Reset to default
17
$\begingroup$

[source of information: my interpretation of multiple hallway chats I've had with DJB and Tanja Lange at conferences]

The actual NIST PQC submission was for two reasons:

  1. A joke. Evidence1: DJB yelling from the back of the room "How much RAM does the NIST benchmarking machine have??" Dustin Moody replying "Dan, we're not benchmarking pqRSA!". Evidence2: DJB mercilessly mocking his paper's reviewers on stage: "Of course it's not practical! This guy clearly has a British stiff upper lip".
  2. A template for other submissions. DJB's plan at least was to submit it several months early to iron out the kinks in the submission process, and to make the latex source public for other submitters to re-use the format and the legal boilerplate (I don't know whether he did or not).

The scientific work behind the submission made some very valuable contributions to the field of cryptographic science:

  1. Answer the question:
    • Question: "Do the honest parties (keygen, encrypt, decrypt) have an asymptotic advantage over a Shor's adversary? If so, how big does the key need to be to get a comfortable amount of quantum security?"
    • Answer: Yes; 1 TB keys to force a quantum circuit with >= $2^{128}$ gates. This reduces to 1 GB keys if you take into account latency between quantum gates and make a "not before expiry of the universe" type argument.
  2. Modification to the encrypt and decrypt operation to make them more efficient on multi-prime keys.
  3. Batch-prime generation: to optimize keygen of several thousand (million?) 1024-bit primes, they came up with a way to more efficiently generate primes in batches.
  4. Can we save ECC the same way? As part of the same research, effort was put into making a pqECC with a similarly massive key, but they could not find equivalent mathematical tricks that would give the honest parties an asymptotic advantage over a quantum adversary.

Even though the submission will not make it past Round1, it made valuable contributions both to the competition itself, and to cryptographic science as a whole. As @SqueamishOssifrage said in comments:

The hard work was already done—the paper written, the code tested—so hey, why not submit it?

Improve this answer
$\endgroup$
13
$\begingroup$

The pqRSA proposal technically complies with the NIST rules for the competition, and, as all governmental organizations, NIST tends to be stickler for rules.

Now of course it's a sort of joke (whether it is a good one, or whether it was taken a bit too far, is a matter of taste). From a pure cryptographic point of view, it might be useful as an illustration of the difficulty of talking about the computational efficiency of a machine that does not exist.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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