Cryptography Reference
In-Depth Information
Computational assumptions.
We would like to closely examine the funda-
mental computational assumptions that underlie the various kinds of key estab-
lishment protocols. To do this, we start by recalling the following well-known
theorems.
9
Theorem 10 ([7]).
Pseudorandom generators exist if and only if one-way func-
tions exist.
Theorem 11 ([8]).
Symmetric-key encryption schemes exist if and only if one-
way functions exist.
Theorem 12 ([20]).
Public-key encryption schemes exist if and only if trapdoor
predicates exist.
Theorem 13 ([21]).
Information-theoretically-secure symmetric-key message
authentication codes exist.
Theorem 14 ([22,23]).
Public-key signature schemes exist if and only if one-
way functions exist.
Theorem 15 ([24]).
Information-theoretically-secure
q-UKE
-protocols exist.
Because we are assuming a quantum universe, one-way functions and trapdoor
predicates
10
in this article (if they exist) are secure against an adversary with a
quantum computer, but are still assumed to be eciently computable on a clas-
sical computer; also, trapdoors are still considered to be classical objects.
11
We
also note that Theorems 10, 11, 12, and 14 hold with respect to
black-box re-
ductions
: if the theorem states that
X
implies
Y
,then
Y
can be constructed
from
X
, only using
X
as a black box, i.e., the reduction does not rely on the
specifics of how
X
works; furthermore, the security reduction is also a black-box
one, i.e., an algorithm for breaking
X
can be constructed from a black box for
9
The following theorems and other similar statements should be interpreted as follows.
A statement of the form “Cryptographic objects of type
Y
exist if cryptographic
objects of type
, then there
exists an object of type
Y
such that breaking the object of type
Y
implies breaking
the object of type
X
exist” means “If there exists an object of type
X
”.
10
Informally, the predicate
B
(
x
)
∈{
0
,
1
}
is a(n)
(unapproximable) trapdoor predicate
if anyone can find an
x
such that
B
(
x
)=0ora
y
such that
B
(
y
) = 1 eciently on
a classical computer, but only one who knows the trapdoor can, given
z
, compute
B
(
z
) eciently on a quantum computer (this notion was introduced in Ref. [20]).
Note that one can use a trapdoor predicate for public-key encryption: the bit
b
is
encrypted as any
x
such that
B
(
x
)=
b
.
11
One could consider “one-way/trapdoor quantum functions”, where the input and
output of the functions are classical or quantum, and the functions only need to
be computable eciently on a quantum computer. We stick to classical one-way
functions and trapdoor predicates that are quantum resistant, candidates of which
are, e.g., the trapdoor predicates underlying some lattice-based cryptosystems (see
Ref. [25] for more examples).
X
.” Such a statement may also be phrased, “
X
implies
Y
