Cryptography Reference
In-Depth Information
Definition 13.4.1
An
encoding
of a group
G
of order
r
is an injective function
σ
:
G
→
}
t
log(
r
)
.
A
generic algorithm
for a computational problem in a group
G
of order
r
is a prob-
abilistic algorithm that takes as input
r
and (
σ
(
g
1
)
,...,σ
(
g
k
)) such that
g
1
,...,g
k
∈
{
0
,
1
G
and returns a sequence (
a
1
,...,a
l
,σ
(
h
1
)
,...,σ
(
h
m
)) for some
a
1
,...,a
l
∈ Z
/r
Z
and
h
1
,...,h
m
∈
G
(depending on the computational problem in question). The generic algo-
rithm is given access to a perfect oracle
O
such that
O
(
σ
(
g
1
)
,σ
(
g
2
)) returns
σ
(
g
1
g
−
1
).
2
Note that one can obtain the encoding
σ
(1) of the identity element by
O
(
σ
(
g
1
)
,σ
(
g
1
)).
One can then compute the encoding of
g
−
1
from the encoding of
g
as
O
(
σ
(1)
,σ
(
g
)).
Defining
O
(
σ
(
g
1
)
,σ
(
g
2
))
=
O
(
σ
(
g
1
)
,O
(
σ
(1)
,σ
(
g
2
))) gives an oracle for multiplication
in
G
.
Example 13.4.2
A generic algorithm for the DLP in
g
where
g
has order
r
takes
g
a
. A generic algorithm for CDH (see
Definition
20.2.1
) takes input (
σ
(
g
)
,σ
(
g
a
)
,σ
(
g
b
)) and outputs
σ
(
g
ab
).
input (
r,σ
(
g
)
,σ
(
h
)) and outputs
a
such that
h
=
In Definition
13.4.1
we insisted that a generic algorithm take as input the order of
the group, but this is not essential. Indeed, it is necessary to relax this condition if one
wants to consider generic algorithms for, say, (
)
∗
when
N
is an integer of unknown
factorisation. To do this, one considers an encoding function to
Z
/N
Z
l
and it follows that the
order
r
of the group is at most 2
l
. If the order is not given then one can consider a generic
algorithm whose goal is to compute the order of a group. Theorem 2.3 and Corollary 2.4 of
Sutherland [
536
] prove an
(
r
1
/
3
) lower bound on the complexity of a generic algorithm
to compute the order
r
of a group, given a bound
M
such that
√
M<r<M
.
{
0
,
1
}
13.4.2 Maurer's model for generic algorithms
Maurer's formulation of generic algorithms [
364
] does not use any external representa-
tion of group elements (in particular, there are no randomly chosen encodings). Maurer
considers a black box containing registers, specified by indices
i
, that store group
elements. The model considers a set of operations and a set of relations. An oracle query
O
(
op,i
1
,...,i
t
+
1
) causes register
i
t
+
1
to be assigned the value of the
t
-ary operation
op
on the values in registers
i
1
,...,i
t
. Similarly, an oracle query
O
(
R,i
1
,...,i
t
) returns the
value of the
t
-ary relation
R
on the values in registers
i
1
,...,i
t
.
A
generic algorithm
in Maurer's model is an algorithm that takes as input the order of
the group (as with Shoup's model, the order of the group can be omitted), makes oracle
queries and outputs the value of some function of the registers (e.g., the value of one of the
registers; Maurer calls such an algorithm an “extraction algorithm”).
∈ N
Example 13.4.3
To define a generic algorithm for the DLP in Maurer's model one imagines
a black box that contains in the first register the value 1 (corresponding to
g
) and in the
second register the value
a
(corresponding to
h
g
a
). Note that the black box is viewed
=
