Cryptography Reference
In-Depth Information
L
n
L
m
,whichisasystemof
m
quadratic polynomials of
n
variables over
L
.
In what follows, let us suppose that
→
F
is expressed as
F
=(
f
r
+1
,..., f
n
)
T
.
L
m
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
Signature Generation.
Let
M
∈
L
n
. Here,
B
=
G
−
1
(
A
) is computed by the following procedure.
Step 1.
Choose a random element
b
1
∈
∈
R
.
Step 2.
For
k
=1
,...,n
, do the following operation recursively.
Here,
g
k
is a non-commutative polynomial with respect to
x
1
,...,x
k
.
By substituting
x
1
=
b
1
, ..., x
k−
1
=
b
k−
1
into
g
k
, we obtain a non-
commutative polynomial,
g
k
,ofonevariable
x
k
and with at most 1
degree. We compute the solution
b
k
∈
R
of
g
k
(
x
k
)=
a
k
(10)
R
m
. (If there is no solution, return to Step 1.)
Step 3.
Set
B
=(
b
1
,...,b
n
).
Verification.
where
A
=(
a
i
)
∈
If
F
(
C
)=
M
, then the signature is accepted, otherwise it is re-
jected.
This scheme is denoted by HS(
R
;
n
).
Remark 1.
In general, it is dicult to solve a non-commutative equation (10)
directly. However, once a
L
-basis of
R
isfixed,wehaveanewsystemof(com-
mutative) linear equations with respect to this basis. This system is easy to
be solved in general. If
R
has an ecient arithmetic operation, the equation
(10) can be solved more eciently. For example, in the case of a quaternion
algebra
Q
L
(
a
), its realization (8) enable us to compute its arithmetic operation
eciently.
5
Security Analysis of HS Scheme
Thus far, we have analyzed [10] the attacks against HS scheme, in the case of
L
=
Z
, for both Coppersmith, Stern and Vaudenary (CSV) [5] and Coppersmith
[4] attacks. In this section, we analyze security countermeasures against these
attacks on the HS scheme when
L
=
K
. Note that some technique to solve
equations of multivariate polynomials is available in the security analysis in the
case of
L
=
K
, on the other hand, it is dicult to be applied in the case of
L
=
/N
Z
. This is the difference between security analysis in the case of
L
=
K
and that in the case of
L
=
Z
/N
Z
Z
/N
Z
.
5.1
Security against CSV Attack
For the public key
F
=(
f
2
,f
3
,...,f
n
), we use notation
F
2
,F
3
...,F
n
as in
§
2.1.
The key step in the CSV attack is to find a linear combination
Λ
=
i
c
i
F
i
of
F
2
,...,F
n
which dose not have full rank. In Birational Permutation scheme,
such
Λ
can be found by solving an equation of polynomial of one variable.
