Cryptography Reference
In-Depth Information
is described by
a
(
l
)
b
(
l
)
i
x
i
+
c
(
l
)
,
g
l
(
x
)=
ij
x
i
x
j
+
(10)
n
u
−
1
+1
≤i≤j≤n
n
u
−
1
+1
≤i≤n
for
m
u−
1
+1
≤
l
≤
m
u
(
n
0
=
m
0
= 0). For the inversion, first solve the equations
y
1
=
g
1
(
x
)
,
=
g
n
1
(
x
)
.
By the construction of
G
, the equations above are of variables
x
n
r
−
1
+1
,
···
,
n
1
···
,x
n
.
If one finds a solution
x
n
r
−
1
+1
,
···
,x
n
, substitute them into other equations
y
m
1
+1
=
g
m
1
+1
(
x
)
,
···
,y
m
=
g
m
(
x
). Next, solve the equations
y
m
1
+1
=
g
m
1
+1
(
x
),
···
,y
m
2
=
g
m
2
(
x
) and substitute the solution
x
n
r
−
2
+1
,
···
,x
n
r
−
1
into other
equations
y
m
2
+1
=
g
m
2
+1
(
x
)
,
,y
m
=
g
m
(
x
). Continuing such steps, enables
the inversion of
G
. In most cases, the ranks of the coecient matrices of
g
l
(
x
)
are small. We know that the rank attacks [46] recover a part of
T
when
n
···
−
n
r−
1
or
n
1
is small, so the values
n
n
r−
1
and
n
1
should be made large enough.
In the original scheme of Tsujii
et al.
[44],
n
=
m
=
r
,
n
l
=
m
l
=
l
and
g
l
(
x
)=
x
l
×
−
(
x
1
,
···
,x
l−
1
-linear) + (
x
1
,
···
,x
l−
1
-quadratic)
.
Shamir's signature scheme [42] is quite similar. For both schemes, attacks to
recover the secret keys had already been proposed [28,13].
The central map
G
of UOV [31] is as follows.
g
l
(
x
)=
1
≤i≤m
(
x
m
+1
,
···
,x
n
-linear)
x
j
+(
x
m
+1
,
···
,x
n
-quadratic)
=
x
t
0
m
∗
∗∗
x
+ (liner form)
.
,r
n−m
)
t
In the process of signature generation, first choose constants
r
=(
r
1
,
···
k
n−m
(
u
=
n
∈
−
m
) randomly and substitute them with
x
m
+1
=
r
1
,
···
,
n
=
r
n−m
.
(11)
Then
g
1
(
x
)
,
,x
m
and are inverted by the
elimination. Kipnis-Shamir proposed an attack [33,31] to find (a part of) the
secret key
S
on UOV with the complexity is
O
(
q
n−
2
m
m
4
), which means that
n
must be suciently larger than 2
m
on UOV.
The Rainbow [20] is a multi-layer UOV, with a central map given by
g
l
(
x
)=
x
t
⎛
···
,g
m
(
x
) are linear forms of
x
1
,
···
⎞
0
n
u
−
1
0
0
⎝
⎠
x
+ (linear)
0
∗
n
u
−n
u
−
1
0
∗
∗
n−n
u
for
m
u−
1
+1
≤
l
≤
m
u
. For the signature generation, first choose random values
,r
n−m
)
t
k
n−m
r
=(
r
1
,
,x
n
=
r
n−m
. Then, one
can invert
G
in a similar way to the UOV case. Because
F
is given by
f
l
(
x
)=
x
t
S
1
0
n
1
∗
···
∈
and input
x
m
+1
=
r
1
,
···
S
1
x
+ (linear)
,
∗∗
n−n
1
