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.