Cryptography Reference
In-Depth Information
not necessarily solve a specific problem instance even when run repeatedly with different
random choices.
Example 2.1.14
Consider an algorithm
A
for the DLP with respect to the instance generator
of Example
2.1.9
. Suppose
A
simply outputs an integer
a
chosen uniformly at random in
the range 0
<a<r
. Since
r>
2
2
κ
the probability that
A
is correct is 1
/
(
r
1
/
2
2
κ
.
−
1)
≤
cx
n
for
x
For any polynomial
p
(
x
) there are
X,c
∈ R
>
0
and
n
∈ N
such that
|
p
(
x
)
|≤
≥
X
.
X
such that
cK
n
2
2
K
. Hence, the success probability of
A
Similarly, there is some
K
≥
≤
is negligible.
Certain decision problems (e.g., decision Diffie-Hellman) require an algorithm to behave
differently when given inputs drawn from different distributions on the same underlying
set. In this case, the success probability is not the right concept and one instead uses the
advantage
. We refer to Definition
20.2.4
for an example.
Chapter 7 of Shoup [
497
] gives further discussion of randomised algorithms and success
probabilities.
2.1.3 Reductions
An
oracle
for a computational problem takes one unit of running time, independent of the
size of the instance, and returns an output. An oracle that always outputs a correct answer
is called a
perfect oracle
. One can consider oracles that only output a correct answer
with a certain noticeable probability (or advantage). For simplicity we usually assume that
oracles are perfect and leave the details in the general case as an exercise for the reader. We
sometimes use the word
reliable
for an oracle whose success probability is overwhelming
(i.e., success probability 1
where
is negligible) and
unreliable
for an oracle whose
success probability is small (but still noticeable).
Note that the behaviour of an oracle is only defined if its input is a valid instance of
the computational problem it solves. Similarly, the oracle performs with the stated success
probability only if it is given problem instances drawn with the correct distribution from
the set of all problem instances.
−
Definition 2.1.15
A
reduction
from problem A to problem B is a randomised algorithm
to solve problem A (running in expected polynomial-time and having noticeable success
probability) by making queries to an oracle (which succeeds with noticeable probability)
to solve problem B.
If there is a reduction from problem A to problem B then we write
4
A
≤
R
B
.
Theorem 2.1.16
Let A and B be computational problems such that A
≤
R
B. If there
is a polynomial-time randomised algorithm to solve B then there is a polynomial-time
randomised algorithm to solve A.
4
The subscript
R
denotes the word “reduction” and should also remind the reader that our reductions are randomised algorithms.
