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?

Improve this question
7
  • 5
    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 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, 2016 at 4: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, 2016 at 5: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, 2016 at 5: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. ​ ​ ​ ​ ​ ​ ​ ​
    – user49075
    Sep 13, 2016 at 8: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, 2016 at 13:24

1 Answer 1

Reset to default
3

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.

Improve this answer
7
  • 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, 2016 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, 2016 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, 2016 at 16:11
  • 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, 2016 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, 2016 at 18:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .