2

Here is the situation - RSA/ECC is not quantum resistant, because a quantum computer feasibly calculate the private key based on the knowledge of the public key (because the quantum computers tackle much easier the hardness of prime factorization, I read).

Now, my hypothetical scenario: What if Alice creates her private key and hands over her public key to Bob in person. At the same time, Bob creates his private key and hands over his public key to Alice in person. Any future data exchange (or key agreement) will then happen always without sharing the public keys. Will this arrangement defy the the quantum computers?

Ivo
  • 61
  • 2
  • 4
    I know this doesn't answer your question, but in your scenario where both the public key and private key are kept secret (from all other parties), I don't see any benefit over just using symmetric encryption (where a single key is kept secret from all other parties). In practice asymmetric encryption is used as part of [hybrid encryption](https://en.wikipedia.org/wiki/Hybrid_cryptosystem) where you just use asymmetric encryption (e.g., RSA) to encrypt a random symmetric key (e.g., AES) that is then used to encrypt/decrypt the long message. – dr jimbob Sep 13 '16 at 04:51
  • 2
    If an eavesdropper observed an *extremely large* number of sent RSA ciphertexts you could limit potential values of the modulus N (in that every c will necessarily be less than the true N). As quantum algorithms (Shor algorithm) can factor a composite number N in O( (lg N)^3 ) time and then break RSA, if you could actually limit N to a small range a quantum attacker could attempt to factor many potential N. I don't think this attack would be feasible for any reasonable number of observed messages for real RSA key sizes, but in principle RSA ciphertexts leak information about N. – dr jimbob Sep 13 '16 at 05:11
  • good points @drjimbob this solution with asymmetric crypto is important in assuring accountability. Symmetric secrets also have the problem that once you had e.g. server ID database, you actually compromise the secrets and identities of all the users – Ivo Sep 13 '16 at 05:28
  • 1
    This is only interesting when asked about _specific_ PKE schemes, rather than PKE in general: ​ ​ ​ If the public key is part of the ciphertexts, then treating them as secret doesn't help. ​ Conversely, if encryption finishes by padding to public length and then applying a symmetric scheme using as key [[a uniformly distributed part of the public key] that was not used in the earlier part of encryption], then treating the public keys as secret makes that at least as secure as the symmetric scheme. ​ ​ ​ ​ ​ ​ ​ ​ –  Sep 13 '16 at 08:07
  • @drjimbob: If the RSA public key is also kept secret, as OP meant, the ciphertext, as a byte sequence, could be partitioned into portions of any smaller sizes or even padded to larger sizes. I don't see how N could be known to the adversary. – Mok-Kong Shen Sep 13 '16 at 13:24
  • @Mok-KongShen -- Imagine a toy 10-bit RSA key; p=29, q=31, N=899. Every ciphertext sent (assuming Kerckhoffs's principle where we understand everything about protocol except the secrets), will necessarily be less than N, and an eavesdropper sees every sent ciphertext. Seeing 30 ciphertexts which will be distributed in the range `[0, N)`, you deduce that N is greater than the largest seen ciphertext. Doing multiple trials (of 30 ciphertext each), I get within 10 odd numbers of the true N about 70% of the time. – dr jimbob Sep 13 '16 at 20:45
  • @drjimbob: Ok. On the one hand, your could even reduce your 10 bits to, say, 5 bits, and on the other hand increase it to, say, 1000 bits. Do you see my point? – Mok-Kong Shen Sep 14 '16 at 10:02

1 Answers1

1

What you are asking about is typically called pre-shared key (PSK) scheme, where a previously shared secret between the parties is used to secure communication. Conceptually, it is secure from quantum attacks. However, PSK is typically implemented with symmetric keys, where you skip key exchange and shared key derivation and go directly from handshake to encrypted channel. This is done with symmetric keys because such algorithms are more computationally efficient. There is no technical reason why PSK could not operate with asymmetric keys, but there is also no reason to use asymmetric keys when you already established a shared secret. In addition, this is not how any of the existing protocols utilize public keys - where public key is transmitted in the clear. For example, as part of TLS protocol server will transmit its certificate that contains public key in the clear during handshake. At that point, public key can be trivially extracted by a passive eavesdropper.

Symmetric cryptography is resistant to quantum computing while asymmetric cryptography is not. The part of asymmetric cryptography that fails to quantum is key derivation, specifically establishing shared secret - it is theoretically possible for an attacker to derive symmetric keys based on information exchanged during handshake and negotiation. All quantum attacks on asymmetric schemes assume knowledge of public key. Assuming custom protocol that never transmits public keys in the clear is used, you would be safe from quantum attacks. Unfortunately, such protocol would not be at all useful in any way.

For now, the best you could do to improve your resistance to quantum is to utilize very, very long public keys. This is based on the assumption that quantum computer with larger number of quantum gates is harder to construct and operate.

Kirill Sinitski
  • 989
  • 6
  • 12
  • Your last paragraph is interesting. Could you give some (naturally) rough idea of how very very long the public keys likely should be (in a certain near future)? – Mok-Kong Shen Sep 14 '16 at 10:13
  • I am not by any means an expert in this, so please don't take what I say as an authoritative source. When using Grover's search a number of q-bits necessary to attack RSA key it linearly related to key length. I believe there are engineering challenges operating quantum computer with more than few q-bits. If today we had megabytes-long RSA keys and a proven and working quantum gate, such long RSA key would likely be safe for foreseeable future. Since relationship is linear, this is not a trapdoor function. – Kirill Sinitski Sep 14 '16 at 13:24
  • 1
    @KirillSinitski - Your advice is bad. If there's a breakthrough in QC that makes having ~1000 coherent qubits usable for computation, it may not take long to extend to ~10000/100000 coherent qubits. Decrypting with a b-bit private RSA key (on a classical computer) scales as O(b^3). Breaking a b-bit RSA modulus on a QC (with O(b) qubits) also scales as O(b^3). Say your computer takes 4 millisecond to encrypt with 4096 bit RSA key (benchmarking on my computer with `openssl speed rsa` gives 7 ms) ; it would take about a billion years to do a single decryption with a 1 MB modulus. – dr jimbob Sep 16 '16 at 16:11
  • It's better to just switch to algorithms that don't rely on things that can easily be broken with Shor's algorithm (no factoring or no (elliptic curve) discrete logs). Something like McEliece or NTRU, or symmetric crypto with double-sized keys (to factor for Grover's algorithm halving the effective key length) See: https://en.wikipedia.org/wiki/Post-quantum_cryptography – dr jimbob Sep 16 '16 at 16:15
  • @dr jimbob I'd like to object that my advice is least bad alternative. There is no proven quantum resistant public key algorithm that I am aware of. There is no existing QC implementation that could chain more than a couple qubits. Obviously, with new developments this advice will have to be revised. Yes, computation time with extra-long RSA keys is an issue, but it can be solved with dedicated crypto accelerators. Both of these are proven technologies today that would address QC as we understand them today. – Kirill Sinitski Sep 19 '16 at 14:33
  • 1
    @KirillSinitski Yes, nothing's proven quantum resistant, but there's also no public key algorithm/trapdoor function that's proven to be resistant to classical computers in fast polynomial time. It's generally very hard to prove that some new algorithm no one has conceived of (utilizing properties not thought of) can't solve a problem. Quantum computers aren't magic machines that can do everything faster; they can just do certain operations very well like the quantum Fourier transform that can be exploited to find periods in discrete groups used to factor numbers or solve discrete logs. – dr jimbob Sep 19 '16 at 17:14
  • 1
    Also your alternative is not feasible -- massively parallel supercomputers with custom ASICs are not close to being fast enough to generate or use megabyte (8388608 bit) sized RSA keys. Humans have only found about 50 primes in our history that are 4194304 bits or larger (and all have very special form like Mersenne primes). (Using one of these 50 large known primes in a key would be extraordinarily weak as you could factor by dividing the modulus against the 50 known large primes). There's no reason to think post-quantum algorithms should be susceptible to quantum computation. – dr jimbob Sep 19 '16 at 18:22