Breaking ciphertext using a quantum computer when the public key is not available

Question

As we know about Shor's algorithm on quantum computers it is possible to crack RSA / ECC easily if we have enough qubits.

Is it possible to crack RSA / ECC on a quantum computer if we only have ciphertext and don't have the public key used to encrypt itself?

Does it matter if we have many ciphertexts and corresponding plaintext for some of them that are generated using the same public key?

I've indeed removed your third question and simplified the text in your question for the benefit of future readers. If you see that a question is off topic (and not answered in the accepted answer) then please remove it and possibly ask separately. Generally we assume that multiple ciphertext are available to an attacker, so the second question is not really needed either (but that's only true in hindsight, so I've left it in). — Maarten Bodewes, Commented May 9, 2020 at 10:52

Maarten Bodewes · Accepted Answer · 2020-05-09 10:55:40Z

You asked:

Is it possible to crack RSA / ECC on a quantum computer if we only have ciphertext and don't have the public key used to encrypt itself?

Typically not, with a few exceptions; here are the exceptions:

RSA signatures with deterministic padding (eg. PKCS #1.5) and a small to moderate $e$ (e.g. $e = 65537) - with two signatures (and corresponding message), we can recover the public key with a conventional computer (and then use our quantum computer to break it).
ECDSA signatures - with one signature (and corresponding message), we can recover the public key (with a few "false hits") with a conventional computer; we can then use our quantum computer to break it.

Things that likely look immune:

RSA encryption (which always uses random padding), or randomized RSA signatures (e.g. PSS); the relationships between the plaintexts would appear to be too subtle for the attacker to use them.
EdDSA signatures - because of how the public key is stirred in, the key recovery method we used with ECDSA doesn't work (and without the public key, the attacker can't compute $H(R, A, M)$, which you need to know to have a copy of generating a forgery)
ECIES - the ciphertext consists of $rG$ (for some random $r$) and a symmetric ciphertext that is keyed based of $rP$; the attacker could recover the value $r$ with his handy quantum computer, however without knowing $P$, there's not much else he can do (and having multiple ciphertexts wouldn't appear to help).

i edited the question to include having plaintext for some of ciphertexts , i'd appreciate if you edit your answer to include answer for that case too (i'll delete this comment when answer is edited by you) — emaditaj, Commented May 9, 2020 at 20:21
i mean for ecies if we have plaintext, so we can get the key used in symmetric algo , so now we know P (you said "without knowing P, there's not much else "), and with having p break the sytem , am i right or the P is something else , and we can't get it if you have key used for symmetric algo — emaditaj, Commented May 10, 2020 at 21:47
@emaditaj: "for ecies if we have plaintext, so we can get the key used in symmetric algo"; actually, for the symmetric algorithms we actually use in ECIES, you cannot recover the key with just a single plaintext/ciphertext, even with a quantum computer (I'd argue that'd be the case even if it were a 128 bit key, but that is marginal). In any case, with ECIES, that symmetric key is generated via a KDF, which is itself one-way... — poncho, Commented May 11, 2020 at 3:13

1 Answer 1