Cryptography Reference
In-Depth Information
breaking
Y
. Non-black-box theorems of this sort are also possible (for example,
see Ref. [26]), but are rarely required for these kinds of results, and indeed are
not required for the theorems we quote. This is lucky, since it guarantees us that
the theorems still hold with respect to a quantum universe.
Table 2.
Minimal known fundamental computational assumptions sucient for the
existence of key establishment protocols in each class
Protocol class
Computational assumptions
OOB
none
PGE
one-way functions
wc-AKE
one-way functions
c-UKE
/
sc-AKE
trapdoor predicates
q-UKE
/
q-AKE
sym
none
q-AKE
pub
one-way functions
The theorems establish the minimal fundamental computational assumptions
known to be sucient for the existence of protocols by class, summarized in
Table 2. Public-key encryption implies one-way functions [8]. Thus, the classes
c-
UKE
and
sc-AKE
require the strongest assumption in the table—the existence
of trapdoor predicates—which reflects the fact that it is not known how to
construct any protocol in these classes without relying on (or implying) public-
key encryption.
12
To facilitate our discussion, we summarize this point as the
following conjecture:
Conjecture 16 (Classical secret key agreement implies public-key en-
cryption).
Every protocol in
c-UKE
implies a trapdoor predicate (with respect
to a possibly-non-black-box reduction).
Safest Fair Comparison.
Most articles on quantum cryptography that ap-
peared in the 1990s and early 2000s stressed the fact that
q-AKE
sym
(respectively,
q-UKE
) is the only known class of in-band
ake
(respectively,
uke
)protocols
that requires no computational assumptions. But implicitly discarding all
computational assumptions in this way makes it impossible to have a serious
discussion about the relative merits of classical and quantum protocols for key
establishment (since any classical key-establishment protocol requires some com-
putational assumption). So, suppose we give classical cryptography a fighting
chance: suppose we allow only
the weakest computational assumption necessary
for in-band classical key establishment
—one-way functions.
12
One might declare Table 2 misleading, since, for example, Theorem 14 is usually
regarded merely as a plausibility result: the construction of a signature scheme from
an arbitrary one-way function is relatively very inecient. To address this issue,
we note that reasonably practical constructions are known for pseudorandom gen-
erators, symmetric-key encryption schemes, and signature schemes from one-way
permutations
[7,8]. Thus, even restricting to reasonably practical schemes, the class
sc-AKE
still requires the assumption of a primitive possessing a trapdoor property,
as far as we know.
