Cryptography Reference
In-Depth Information
2.3.4 Probabilistic Algorithms
The concrete algorithms we have considered so far are
deterministic
, in the sense
that their behavior is completely determined by their input, so that if the algorithm
is executed multiple times with the same input, it always produces the same output.
But, as we shall see, in cryptology one often uses
probabilistic
(
or randomized
)
algo-
rithms
. These algorithms have access to a source of randomness that yields random
bits
4
with uniform probability distribution (i.e., where 0 and 1 each have probabil-
ity
2
). Consequently, a probabilistic algorithm may produce a different output each
time it is executed with the same input. Examples of algorithms of this type used in
cryptography are:
•
Algorithms to randomly generate a key of a given size.
•
Randomized encryption algorithms which produce different ciphertexts when
repeatedly used with the same plaintext and the same key (as we shall see, the
use of probabilistic encryption algorithms is crucial to obtain good security).
•
Probabilistic algorithms used to test primality, such as the
Miller
-
Rabin test
,to
be discussed later.
•
Algorithms to randomly choose a prime number of a given size.
We have already mentioned the relation between polynomial-time and efficient
(or, at least, tractable) computation and now we want to point out that probabilistic
polynomial-time algorithms (which are generally faster than deterministic ones) are
actually the ones usually taken to define efficiency. There are several interesting
classes of probabilistic algorithms, among which we mention:
•
Monte Carlo algorithms
. These run in polynomial time but may not always give
the correct result. In the case of a decision problem a Monte Carlo algorithm is
yes
-
biased
if a 'yes' answer is correct with some probability
2 but a 'no' answer
is always correct. Similarly,
no
-
biased
Monte Carlo algorithms are defined by
interchanging the roles of 'yes' and 'no'. The two-sided versions of Monte Carlo
algorithms, which may err on either the 'yes' or the 'no' side, are also called
Atlantic City
algorithms.
>
1
/
•
Las Vegas algorithms
. These algorithms run in
expected
polynomial time, meaning
that their running time is a random variable whose expected value is polynomial
(see Sect.
2.1
) but, in contrast, their output is always correct. However, Las Vegas
algorithms may not even provide an output for some inputs.
It is sometimes said that Monte Carlo algorithms are always fast but only probably
correct while Las Vegas algorithms, on the contrary, are always correct but only
probably fast. As we shall see later, examples of both classes of algorithms are
known for the decision problem of determining whether a given integer is prime
(in fact, there is also a deterministic polynomial-time algorithm for this problem, but
it is significantly less efficient than the probabilistic ones).
4
It is often metaphorically said that the algorithm tosses “random coins”.
