Cryptography Reference
In-Depth Information
δ
=
δ
T
Then these span a subspace
{
∈
R
}
of rank 3 with high probability. One
can compute
X
∈
R
by satisfying
(
C
(
i
1
)
T
X
C
(
i
)
are symmetric matrices (
i
=1
,
2
,
3)
,
2
which is determined up to scalars. From the above fact,
X
is found to be pro-
portional to
u
. It is not dicult to compute
u
, a part of the secret key, from
X
.
Coppersmith's second attack.
The second Coppersmith's attack is based on
the following algorithm.
Proposition 1 ([2]).
Let
N
be an odd positive integer and
f
(
x, y
)
a bivariate
quadratic polynomial over
Z
Z
.
Δ
(
f
)
denotes the discriminant of
f
defined as
in [2]. If
gcd(
Δ
(
f
)
,N
)=1
, then there exists an algorithm which gives a solu-
tion to
f
(
x, y
)=0
with probability
1
/N
, and requires
O
(log(
−
1
log
N
)log
4
N
)
arithmetic operations on integers of size
O
(log
N
)
bits.
−
If
x, y
∈
R
are written as
x
=
x
0
·
1+
x
1
·
i
+
x
2
·
j
+
x
3
·
ij,
y
=
y
0
·
1+
y
1
·
i
+
y
2
·
j
+
y
3
·
ij,
then the equation over
R
,whichis
x
T
x
+
y
T
hy
=4
M
(7)
is rewritten by 4 quadratic equations with respect to 8 variables
x
0
,x
1
,...,y
3
.
By simplifying equation (7) and using the property of quaternion algebra, the
problem of solving the system of quadratic equations can be reduced to that of a
set of bivariate quadratic equations. Therefore, it is possible to forge a signature
basedontheaboveproposition.
4
Redefinition of HS Scheme
In HS scheme, more general non-commutative rings can be utilized than the
quaternion algebra used in Sato-Araki scheme. In this section, we describe HS
scheme associated to non-commutative rings over a field
K
or
Z
/N
Z
.Inthecase
of
Z
/N
Z
, the scheme becomes the original HS scheme.
4.1
Non-commutative Rings
Let
L
be either a field
K
or
Z
/N
Z
. In this paper, we say that an
L
-algebra
R
is
a non-commutative ring only if
(1)
R
is a free module over
L
with finite rank, and
(2)
R
is non-commutative.
