In classical cryptography, security proofs are often based on the (assumed) computational hardness of some mathematical problem. Using the principles of quantum mechanics might provide means to design cryptographic protocols that can classically not be implemented (information-theoretically) securely. But is there also a notion of computational security in quantum cryptography (assuming a polynomial-time quantum adversary)? Why does or doesn't make this notion of security sense?


1 Answer 1


But is there also a notion of computational security in quantum cryptography (assuming a polynomial-time quantum adversary)?

No, not really, or at least, none that has been explored. The goal of Quantum Cryptography is to be secure, even if the adversary has a Quantum Computer and that they are computationally unbounded; that is, the goal is to rely (as much as possible) on security-by-the-laws-of-physics alone [1].

One could include the assumption that they are computationally bounded; however if you did that, you would have a number of competing options available, including large key symmetric cryptography and postquantum (public key) cryptography. These existing solutions already solve the problem, and are considerably cheaper and more versatile. Hence, there appears to be little need to lower the security bar on Quantum Cryptography.

Kelalaka brought up the paper "Computational Security of Quantum Encryption"; however a close review shows that the security targets it makes do not rely on the security assumptions of Quantum Mechanics. Instead, it examines the extension of classical cryptography into the realm of Qubits (and how that differs in nontrivial ways from the cryptography on bits). This may be semantics, however I do not believe that falls into the realm of "Quantum Cryptography".

[1]: Of course, that's not the only assumption; they always need to assume that there are no exploitable side channels, that the equipment is operating as designed (and not in a way that looks correct, but is exploitable) and also for many QKD systems, the shared keys are used to AES encrypt the actual traffic (and hence those systems need to assume AES is strong as well).

  • $\begingroup$ What about this work Computational Security of Quantum Encryption? $\endgroup$
    – kelalaka
    Commented Jul 7, 2020 at 14:52
  • $\begingroup$ I don't think that this answer is correct. For example, With the proven bound of Grover's algorithm, now one can talk about the quantum computational security like in the perfect vs computationally secure. Even it can be run parallel threre are limits for those. $\endgroup$
    – kelalaka
    Commented Jul 7, 2020 at 15:49
  • 1
    $\begingroup$ @kelalaka: I disagree that things like Grover's algorithm (against, say, a symmetric cipher) is relevant to the question; it specifically asked about "quantum cryptography", not classical cryptography that is secure if the adversary has a quantum computer. $\endgroup$
    – poncho
    Commented Jul 7, 2020 at 17:11
  • 1
    $\begingroup$ I'm pretty sure there is a very large number of works on quantum cryptography that rely on computational assumption. For example, there exists quantum oblivious transfer protocols if and only if there exists quantum commitments, but the latter must be a computational assumption (they cannot exist unconditionally in the quantum world). While there are plausible quantum-secure classical constructions of oblivious transfer, their security is not known to reduce to the existence of commitment schemes, which is a seemingly much weaker assumption. Hence, it makes sense to consider a quantum OT, $\endgroup$ Commented Jul 9, 2020 at 5:54
  • 1
    $\begingroup$ because we can base it on weaker assumptions, even though we cannot build it unconditionally even I'm the quantum setting. There are many results of this kind out there. I'm not even mentioning the works on quantum circuit evaluation in crypto (e.g. secure computation, or garbling, or obfuscation, of quantum circuits) which require computational assumption, while obviously involving participants which must be able to perform quantum computation. $\endgroup$ Commented Jul 9, 2020 at 5:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.