# Why is pqRSA in the NIST PQC submissions?

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?

• The hard work was already done—the paper written, the code tested—so hey, why not submit it? – Squeamish Ossifrage May 28 '18 at 2:12
• So just for fun (and perhaps some free analysis and publicity)? – forest May 28 '18 at 2:14
• 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. – Ella Rose May 28 '18 at 2:50
• 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. – Future Security May 28 '18 at 23:04
• 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.) – Future Security May 28 '18 at 23:22

[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:

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