Score:1

Crypto

Why can't we just increase the bit length to counteract shor's algorithm?

HarryFoster1812

2/27/24, 5:17 PM

I know that it sounds like a very stupid question but if Shor's algorithm has a complexity of roughly $n^3$ why cant we just increase the bit size until the time for the algorithm to run is unfeasible on a quantum computer or would it just take too much memory and too much computation for RSA/ECC to be worth it?

147

3 + 2

elliptic-curves

post-quantum-cryptography

quantum-cryptography

shors-algorithm

ddddavidee

2/27/24, 5:26 PM

There is a paper by Bernstein et al. that does exactly this. If I remember correctly the RSA key has to be increased up to one terabyte to be secure. Link to the paper https://eprint.iacr.org/2017/351

ddddavidee

2/27/24, 5:50 PM

A question related to the pqRSA https://crypto.stackexchange.com/questions/59591/why-is-pqrsa-in-the-nist-pqc-submissions?rq=1

Score:6

Crypto

poncho

2/27/24, 5:56 PM

if shor's algorithm has a complexity of roughly n^3 why cant we just increase the bit size until the time for the algorithm to run is unfeasible on a quantum computer

The problem is that the amount of work needed by the honest parties is also roughly $n^3$, hence we don't have that much advantage over an attacker.

To be fair, we do have a few advantages:

For RSA, there are optimizations available for the honest parties that aren't there for the attacker, for example, the CRT optimization on the private operation, and short exponents on the public one [1]
The attacker has to run his operation on a Quantum Computer, which will likely be a large constant times as expensive as a classical one.

On the other hand, both these advantages don't add up to enough (especially given that we also assume the adversary has considerably more computational resources at his disposal than we do).

[1]: I believe that, when targeting a discrete log problem, Shor's can take advantage of knowledge that the exponent is small, and so that discrete log optimization doesn't help us.

+ 0

Score:3

Crypto

Mark

2/27/24, 7:06 PM

The main reason is because any such technique has at best a polynomial gap between

the effort honest parties must spend to compute the cryptosystem, and
the effort adversaries must spend to break the cryptosystem.

Cryptography from a polynomial honest-to-malicious hardness gap has been known for a while. In fact, one of the earliest public-key cryptosystems (before RSA by a few years iirc) went by the name of Merkle's Puzzles, and had precisely this property, namely they took $O(n)$ time to compute for honest parties, and $\Omega(n^2)$ for adversaries. See Public-Key Cryptography in the Fine-Grained Setting for example. Moreover, in the random oracle model, this is size of gap is known to be optimal, at least in the classical setting.

This is to say that if you are going to "settle" for a small gap between honest parties and adversaries, it is perhaps better to do other things than simply RSA "scaled up" appropriately, though perhaps it is best to simply use a lattice-based scheme instead.

+ 0

Score:-5

Crypto

Swashbuckler

2/27/24, 5:45 PM

That's what CNSA 1.0 did: minimum RSA key length is 3072, minimum AES key length is 256, and minimum SHA length is 384. CNSA 2.0 goes beyond that with some new algorithms.

+ 3

poncho

2/27/24, 5:46 PM

This doesn't answer the question...

Swashbuckler

2/27/24, 7:49 PM

@poncho but it does senor, but it does.

poncho

2/27/24, 7:53 PM

How does it answer the question? The question was "why can't we use larger RSA/ECC modulii to address concerns about quantum computers?" CNSA 1.0 doesn't address quantum computers at all - CNSA 2.0 does by saying "don't use RSA/ECC, instead use those algorithms over there"

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Why can't we just increase the bit length to counteract shor's algorithm?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.