Cryptography Reference
In-Depth Information
Example 2.1.9
Let a security parameter
κ
be given. First, generate a random prime
number
r
such that 2
2
κ
<r<
2
2
κ
+
1
(by choosing uniformly at random (2
κ
∈ N
1)-bit integers
and testing each for primality). Next, try consecutive small integers
k
until
p
+
=
kr
+
1is
u
(
p
−
1)
/r
and repeat if
g
prime. Then, choose a random integer 1
<u<p
and set
g
=
=
1.
= F
p
of order
r
. Finally, choose
It follows that
g
is a generator of a cyclic subgroup of
G
g
a
. Output (
p,r,g,h
), which can
uniformly at random an integer 0
<a<r
and set
h
=
be achieved using 3
bits.
One sees that there are finitely many problem instances for a given value of the security
parameter
κ
, but infinitely many instances in total. The output distribution has (
r,g,h
)
uniform in the appropriate sets, but
p
is not uniform.
log
2
(
p
)
+
log
2
(
r
)
When considering an algorithm
A
to solve a computational problem we assume that
A
has been customised for a particular instance generator. Hence, a problem might be easy
with respect to some instance generators and hard for others. Thus it makes no sense to
claim that “DLP is a hard problem”; instead, one should conjecture that DLP is hard for
certain instance generators.
We now define what is meant by the word negligible.
Definition 2.1.10
A function
:
N → R
>
0
is
negligible
if for every polynomial
p
(
x
)
∈
R
[
x
] there is some
K
∈ N
such that for all
κ>K
with
p
(
κ
)
=
0wehave
(
κ
)
<
1
/
|
p
(
κ
)
|
.
A function
:
N → R
>
0
is
noticeable
if there exists a polynomial
p
(
x
)
∈ R
[
x
] and an
integer
K
such that
(
κ
)
>
1
/
|
p
(
κ
)
|
for all
κ>K
with
p
(
κ
)
=
0.
={
∈ R
≤
≤
}
N →
−
Let [0
,
1]
x
:0
x
1
. A function
p
:
[0
,
1] is
overwhelming
if 1
p
(
κ
) is negligible.
Note that noticeable is not the logical negation of negligible. There are functions that
are neither negligible nor noticeable.
1
/
2
κ
is negligible.
Example 2.1.11
The function
(
κ
)
=
Exercise 2.1.12
Let
f
1
(
κ
) and
f
2
(
κ
) be negligible functions. Prove that
f
1
+
f
2
is a
negligible function and that
p
(
κ
)
f
1
(
κ
) is a negligible function for any polynomial
p
(
x
)
∈
R
[
x
] such that
p
(
x
)
>
0 for all sufficiently large
x
.
Definition 2.1.13
Let
A
be a randomised algorithm to solve instances of a computational
problem generated by a specific instance generator. The
success probability
of the algo-
rithm
A
is the function
f
:
,
f
(
κ
) is the probability that
A
outputs the correct answer, where the probability is taken over the randomness used by
A
and according to the output distribution of the instance generator on input
κ
. An algorithm
A
with respect to an instance generator
succeeds
if its success probability is a noticeable
function.
N →
[0
,
1] such that, for
κ
∈ N
Note that the success probability is taken over both the random choices made by
A
and the distribution of problem instances. In particular, an algorithm that succeeds does
