Cryptography Reference
In-Depth Information
There is good reason to do this. Trapdoor predicates seem to be inherently
less secure than one-way functions in general. Firstly, trapdoor predicates easily
imply one-way functions [8], whereas the converse is believed not to be true.
As some evidence for this, we note that it has been shown in Ref. [27] that,
with respect to black box reductions (and with respect to a classical universe),
one-way functions are not sucient (even) to imply secret key agreement (see
Remark 4; but we have not checked that this theorem holds with respect to
a quantum universe—in general, such classical black-box no-go theorems need
not). Secondly, using the equivalences stated in Theorem 11 and Theorem 12, it
seems far more likely that an ecient algorithm would be found for breaking a
public-key cryptosystem (i.e. computing a trapdoor predicate) than breaking a
symmetric-key cryptosystem (i.e. inverting a one-way function without the trap-
door property), because the public-key cryptosystem possesses more structure in
order to embed a trapdoor into the encryption “function”. Quantum computers
are firmly believed not to be able to invert all one-way functions eciently; we
state this as a conjecture:
Conjecture 17 (One-way functions exist).
Quantum-resistant one-way
functions (computable in polynomial-time on a classical computer) exist.
We do not mean to suggest that quantum-resistant trapdoor predicates do not
exist (we don't know). We do suggest, though, that the added structure of trap-
door predicates makes it much more likely that algorithms for the underlying
problems will improve at a more unpredictable rate: plain one-way functions are
less risky.
Even allowing one-way functions, we see that
qke
has advantages over clas-
sical systems, beyond unconditional security.
Advantages of QKE assuming (only) one-way functions.
Most of the
advantages below have appeared elsewhere in the literature in one form or an-
other, but our presentation is motivated differently. The following four advan-
tages are not intended to be totally independent; indeed, each is just a quali-
tatively different consequence of the fact that the secret key is independent of
both the initial keys and classical communication in
qke
(and that we have taken
sc-AKE
-protocols out of the picture).
•
Advantage 1: Improved security against reveal of initial keys
In classical cryptography, the physical nature of a cryptosystem and protocol
leads to the consideration of different types of attacks, some more serious or
more technologically dicult to mount than others. Similarly, adversaries are
often categorized by their power, for example,
passive
adversaries are considered
only to be able to read certain data that is sent along a channel, whereas
active
adversaries are assumed to have complete control over the channel. It is also
relevant to consider precisely
when
Eve may become active; a
delayed
adversary
is one that remains passive until the key establishment protocol completes, but
is active immediately afterwards.
