Cryptography Reference
In-Depth Information
A reduction between problems A and B therefore explains that “if you can solve B then
you can solve A”. This means that solving A has been “reduced” to solving problem B and
we can infer that problem B is “at least as hard as” problem A or that problem A is “no
harder than” problem B.
Since oracle queries take one unit of running time and reductions are polynomial-time
algorithms, a reduction makes only polynomially many oracle queries.
Definition 2.1.17
If there is a reduction from A to B and a reduction from B to A then we
say that problems A and B are
equivalent
and write
A
≡
R
B
.
Some authors use the phrases
polynomial-time reduction
and
polynomial-time equiv-
alent
in place of reduction and equivalence. However, these terms have a technical meaning
in complexity theory that is different from reduction (see Section 34.3 of [
136
]). Defini-
tion
2.1.15
is closer to the notion of Turing reduction, except that we allow randomised
algorithms, whereas a Turing reduction is a deterministic algorithm. We abuse terminology
and define the terms
subexponential-time reduction
and
exponential-time reduction
by
relaxing the condition in Definition
2.1.15
that the algorithm be polynomial-time (these
terms are used in Section
21.4.3
).
2.1.4 Random self-reducibility
There are two different ways that an algorithm or oracle can be unreliable. First, it may be
randomised and only output the correct answer with some probability; such a situation is
relatively easy to deal with by repeatedly running the algorithm/oracle on the same input.
The second situation, which is more difficult to handle, is when there is a subset of problem
instances for which the algorithm or oracle extremely rarely or never outputs the correct
solution; for this situation random self-reducibility is essential. We give a definition only
for the special case of computational problems in groups.
Definition 2.1.18
Let
P
be a computational problem for which every instance of the
problem is an
n
1
-tuple of elements of some cyclic group
G
of order
r
and such that the
solution is an
n
2
-tuple of elements of
G
together with an
n
3
-tuple of elements of
Z
/r
Z
(where
n
2
or
n
3
may be zero).
The computational problem
P
is
random self-reducible
if there is a polynomial-time
algorithm that transforms an instance of the problem (with elements in a group
G
)intoa
uniformly random instance of the problem (with elements in the
same
group
G
) such that
the solution to the original problem can be obtained in polynomial-time from the solution
to the new instance.
We stress that a random self-reduction of a computational problem in a group
G
gives
instances of the same computational problem in the same group. In general, there is no
way to use information about instances of a computational problem in a group
G
to solve
