Cryptography Reference
In-Depth Information
In HS scheme, the attack by finding a matrix which dose not have full rank,
like a Λ , can be extended. Moreover, in a more general setting of scheme in
MPKC, the CSV attack can be extended, which is called the HighRank attack.
We will analyze the security against the HighRank attack in
§
7.
5.2
Security against Coppersmith's First Attack
Sato-Araki scheme can be translated using HS scheme as HS( Q Z /N Z (
1); 2)
with
A 1 = Identity map of
Z
/N
Z
,
) 2
) 2 given by A 2 ( z 1 ,z 2 )=( z 1 + uz 2 ,z 1
A 2 :(
Z
/N
Z
Z
/N
Z
uz 2 )
(
where u is a part of the secret key described as in
3. Because A 1 and A 2 are fixed
and expressed by simple transformations, a simple relation (6) holds. Therefore
the Coppersmith's first attack is applicable for Sato-Araki scheme. However in
HS scheme, we adopt random ane transformations as A 1 and A 2 .Thismakes
dicult to find a simple relation like a (6) in HS scheme.
§
5.3
Security against Coppersmith's Second Attack
In Sato-Araki scheme, the problem to forge a signature is reduced to that to
solve the non-commutative equation (7). Moreover this equation is rewritten
by 4 quadratic equations with respect to (commutative) 8 variables as in
3.1.
Fortunately, the system of these quadratic equations is decomposed into some
systems of bivariate quadratic equations, and therefore we can solve the non-
commutative equation (7) using Proposition 1. However, in HS scheme, the
numbers of non-commutative variables and equations increase. Concretely, we
need to solve r ( n
§
1) quadratic equations with respect to (commutative) rn
variables for HS( R ; n )where r is the dimension of R over K . Therefore the se-
curity against Coppersmith's second attack in HS scheme is reduced to the MQ
problem.
6
Reduction of HS Scheme to Rainbow
Uchiyama and Ogura [22] pointed out that the original HS scheme, which is
defined over
-analogue of Rainbow in
which the original Rainbow [7] is a multilayer variant of the Unbalanced Oil and
Vinegar signature scheme. This implies that attacks against Rainbow also apply
to HS scheme.
Z
/N
Z
, can be rewritten using a
Z
/N
Z
6.1
Original Rainbow and Its Analogue
To deal with both the original Rainbow and its analogue over a finite field, we
prepare Rainbow defined over L which is either K or
Z
/N
Z
.
 
Search WWH ::




Custom Search