Finally, possibly the greatest challenge, is the issue of efficiency. While for certain applications (defense, financial market, among others) the highest security is desired even with the cost of worse performance, for a great range of everyday applications slowing down the services is not acceptable (people frequently prefer insecure but high-speed services). Existing post-quantum cryptosystems, when taking all aspects into account, lack efficiency (public key-size, signature size, speed of encryption and decryption algorithms, speed of key generation algorithm, and so on). Improving this, or identifying applications that can tolerate one of these aspects being less efficient, is an active field of research.

Superposition attacks: Modifying
security notions. Security is frequently
defined in terms of the probability that
an adversary can succeed in certain hy-
pothetical, interactive games. For ex-
ample, one defines indistinguishabil-
ity as a game that adversaries cannot
win with probability higher than 1/2,
indicating that randomly guessing the
plaintext bit is the best they can do. In
this game, the adversary is given extra
ability to use a learning phase in which
they can request ciphertexts of their
chosen plaintexts. The motivation for
giving these extra abilities is that one
can imagine a scenario that an adver-
sary could persuade an honest party
to encrypt a message of their choice.
To ensure privacy, this action should
not give the adversary any advantage
in trying to decrypt other, unknown to
the attacker, messages. Now we want
to consider adversaries that have the
extra ability to make quantum queries
(and receive quantum answers) in such
a game. Mathematically, if the encryp-
tion (for example) is described by a
function fk, a “classical” query a quan-
tum party can make is described as
|x⟩|y⟩ → |x⟩| fk (x) ⊕ y⟩, where we note
the first register maintains the informa-
tion on x since quantum (unitary) oper-
ations are necessarily reversible. How-
ever, a quantum adversary could have
initiated the query in superposition Σx,y
Ψx,y |x⟩|y⟩ which by quantum linearity
would lead to a superposition cipher-
text Σx,y Ψx,y |x⟩| fk (x ) ⊕ y⟩. The quantum
adversary could attempt to use these
superposition ciphertexts to break a
cryptosystem. It is worth stressing that
having a superposition is not the same
abilities” (see Figure 1). The first class
is where the adversaries are classi-
cal with the extra ability to also solve
problems in bqp. In other words, these
adversaries are like the standard clas-
sical adversaries, with extra access to
an oracle/quantum-computer. This
class is the best known and, in many
accounts of post-quantum security,
the only one discussed. In the second
and third classes we give extra abili-
ties to the adversaries, for example,
we allow them to send input (queries)
in quantum states (superposition of
classical bits) and then use the (quan-
tum) output, along with their quantum
computer oracle, to compromise the
security of protocols. The second class
addresses the modeling and modifica-
tion of security definitions, along with
the immediate consequences. In the
third class we deal with the changes re-
quired in (involved) proof techniques
in this new quantum security model.
For example, the internal state of an
adversary during an interactive proto-
col is described by a general quantum
state and their actions by a general
quantum map.

We should note that all protocols in the post-quantum security category are, in terms of technologies used, fully classical protocols. All the honest steps are realized in classical devices. Still, understanding quantum computation (hardness of problems) and quantum technologies in general (modeling other types of attacks) is crucial to prove the security.

Security against an adversary with an oracle quantum computer. The first, and by far the most thoroughly researched area, is to ensure the security of protocols used is based on the hardness of problems which remain hard for quantum computers. This is clearly a priority since, once quantum computers are built, attacking cryptosystems that use problems that are not hard for quantum computers will be trivial. As explained in Myth 3 and depicted in Figure 2, it is believed that there exist NP problems outside BQP, therefore public key cryptography is still possible in the setting that adversaries have access to an oracle quantum computer.

There are many cryptosystems be-
lieved to be resistant to attacks of this
type. They can be divided to hash-
based, code-based, lattice-based, mul-
tivariate, and secret-key cryptography
(see details in Bernstein7). Here, we will
comment on three issues: confidence,
usability, and efficiency.

The belief that a problem is hard, while in some cases it comes from theoretical implications that involve containments of complexity classes, is frequently based on the inability to find efficient solutions (or improve on existing solutions) despite the effort of many groups during a long period of time. This is the case for the hardness of factoring for classical computers. When we examine the hardness of problems used in cryptosystems against quantum computers, the confidence we have is generally even smaller. For example, with the exception of Merkle’s hash-tree public signature system and McEliece’s hid-den-Goppa-code public-key encryption system, all other post-quantum proposals are relatively new. What is even more important is that research in quantum algorithms and quantum complexity theory is also new and proper cryptanalysis of the systems from the perspective of a quantum adversary is not yet as thorough as for the classical case.

This brings us to the issue of standardization and usability. Such initiatives are active, for example, the National Institute of Standards and Technology (NIST) had a recent call to standardize post-quantum public-key cryptosystems. In order to define the quantum-bit security of a cryptosystem, one must establish which is the fastest algorithm that attempts to break the system. This would also determine what key-length is required for a given security level. For example, the quadratic speed-up due to Grover’s algorithm lead to a need for keys of double size. This, of course, would change if a better algorithm is invented, but good candidates for standardized use should be well enough researched to build confidence that (even moderate) speed-ups are not to be found continuously. In contrast, only recently a new speed-up was found for problems using multivariate quadratic equations. 18 Furthermore, after the standardization of encryption functions, one still needs software implementations that are suitable for integration into a variety of applications.