Cryptography Reference
In-Depth Information
expectation is taken over all problem instances of size
n
as well as all choices of the
randomness. For more details see Section 4.2 of Talbot and Welsh [
539
].
2.1.2 Success probability of a randomised algorithm
Throughout the topic we give very simple definitions (like Definition
2.1.1
) for compu-
tational problems. However, it is more subtle to define what it means for a randomised
algorithm
A
to solve a computational problem. A
perfect algorithm
is one where the
output is always correct (i.e., it always succeeds). We also consider algorithms that give the
correct answer only for some subset of the problem instances, or for all instances but only
with a certain probability.
The issue of whether an algorithm is successful is handled somewhat differently by
the two communities whose work is surveyed in this topic. In the computational number
theory community, algorithms are expected to solve all problem instances with probability
of success close to 1. In the cryptography community, it is usual to consider algorithms that
only solve some noticeable (see Definition
2.1.10
) proportion of problem instances, and
even then only with some noticeable probability. The motivation for the latter community is
that an algorithm to break a cryptosystem is considered devastating even if only a relatively
small proportion of ciphertexts are vulnerable to the attack. Two examples of attacks that
only apply to a small proportion of ciphertexts are the attack by Boneh, Joux and Nguyen
on textbook Elgamal (see Exercise
20.4.9
) and the Desmedt-Odlyzko signature forgery
method (see Section
24.4.3
).
We give general definitions for the success probability of an algorithm in this section,
but rarely use the formalism in our later discussion. Instead, for most of the topic, we focus
on the case of algorithms that always succeed (or, at least, that succeed with probability
extremely close to 1). This choice allows shorter and simpler proofs of many facts. In any
case, for most computational problems the success probability can be increased by running
the algorithm repeatedly, see Section
2.1.4
.
The success of an algorithm to solve a computational problem is defined with respect to
an
instance generator
, which is a randomised algorithm that takes as input
κ
(often
κ
is called the
security parameter
), runs in polynomial-time in the output size and outputs an
instance of the computational problem (or fails to generate an instance with some negligible
probability). The output is usually assumed to be
(
κ
) bits,
3
∈ N
so “polynomial-time” in the
previous sentence means
O
(
κ
m
) bit operations for some
m
∈ N
. We give an example of an
instance generator for the DLP in Example
2.1.9
.
Let
A
be a randomised algorithm that takes an input
κ
S
κ
for the set of
possible outputs of
A
(
κ
). The
output distribution
of
A
on input
κ
is the distribution on
∈ N
. Write
S
κ
such that Pr(
x
)for
x
∈
S
κ
is the probability, over the random choices made by
A
, that the
output of
A
(
κ
)is
x
.
3
Hence, for problems related to RSA or factoring,
κ
is now assumed to be the bit-length of the modulus.
