Cryptography Reference
In-Depth Information
Signature Generation
Let
M
)
n−
1
be a message. We compute
A
=
A
−
1
(
M
),
B
=
G
−
1
(
A
)and
C
=
A
−
2
(
B
) in the same order. The signature of the message is
C
∈
(
Z
/N
Z
)
n
.
∈
(
Z
/N
Z
Here,
G
−
1
(
A
) represents an element of the preimage of
A
.
Verificat ion
If
F
(
C
)=
M
then the signature is accepted, otherwise it is rejected.
2.1
Attack against Birational Permutation Scheme
It is believed that solving general equations over
is more dicult than
doing so over a finite field. The security of Birational Permutation scheme was
based on the diculty of solving the problem over
Z
/N
Z
. However, Coppersmith,
Stern and Vaudenary gave an ecient algorithm [5] to compute
A
2
,apartof
the secret key, without solving equations over
Z
/N
Z
.
For simplicity, assume that
A
2
are linear transformations. We write
A, B
for
the matrix expression of the linear parts of
A
1
,A
2
, respectively, and
g
k
,f
k
(
k
=
2
,
3
,...,n
) are denoted by
Z
/N
Z
g
k
(
x
)=
x
T
G
k
x
,
k
=
x
T
F
k
x
(
x
=(
x
1
,...,x
n
)
T
)
,
(2)
for some
F
k
,G
k
∈
M
(
n,
Z
/N
Z
). (
T
means the transpose operator.) Since
a
kl
x
T
B
T
G
j
B
x
=
x
T
B
T
n
B
x
n
f
k
(
x
)=
a
kl
G
l
l
=2
l
=2
where
A
=(
a
kl
), we have
F
k
=
B
T
n
B.
a
kl
G
l
(3)
l
=2
n
, the determinant of
l
=2
a
k
1
l
G
l
−
λ
l
=2
a
k
2
l
G
j
For a variable
λ
and 1
≤
k
1
,k
2
≤
λa
k
2
n
)
2
. From (3), the determinant of
F
k
1
−
is factored by (
a
k
1
n
−
λF
k
2
is also
λa
k
2
n
)
2
. Therefore
a
k
1
n
/a
k
2
n
, which is denoted by
λ
0
,iscom-
puted by the public key. By calculating the kernel and the image of
F
k
1
−
factored by (
a
k
1
n
−
λ
0
F
k
2
,
)
n
is decomposed as
(
Z
/N
Z
(
Z
/N
Z
)
n
=
B
−
1
((
)
n−
1
B
−
1
(
n−
1
Z
/N
Z
×{
0
}
)
⊕
{
0
}
×
(
Z
/N
Z
))
(4)
Continuing this operation, we finally arrive at a decomposition,
)
n
=
B
−
1
((
n−
1
)
B
−
1
(
n−
1
(
Z
/N
Z
Z
/N
Z
)
×{
0
}
⊕···⊕
{
0
}
×
(
Z
/N
Z
))
by subspaces with rank 1. By rewriting the public key on a basis of the above
decomposition, we obtain a system of equations with the same form as the central
map, and in this way, we can forge a signature.
