Cryptography Reference
In-Depth Information
At first, we define the parameters that determine the layer structure of Rain-
bow. Let
t
be the number of layers of Rainbow. Let
v
1
,...,v
t
+1
be a sequence
of positive
t
+ 1 integers, such that
0
<v
1
<v
2
<
···
<v
t
<v
t
+1
.
For
h
=1
,...,t
,thesets
V
h
,O
h
of the indices of the Vinegar and Oil variables
of the
h
-th layer of Rainbow are defined by
V
h
=
{
1
,
2
...,v
h
}
,O
h
=
{
v
h
+1
,v
h
+2
,...,v
h
+1
−
1
,v
h
+1
}
.
The number of elements in
O
h
and
V
h
are
v
h
+1
−
v
i
and
v
i
, respectively, and
denote
o
h
=
v
h
+1
−
v
h
. Note that the smallest integer in
O
1
is
v
1
+ 1. We define
n
=
v
t
+1
, which is the maximum number of variables used in Rainbow.
Rainbow consists of
t
layers of multivariate polynomials of
n
variables. For
h
=1
,
2
,...,t
,the
h
-th layer of Rainbow deploys the following system of
o
h
multivariate polynomials:
α
(
k
)
β
(
k
)
g
k
(
x
1
,...,x
n
)=
i,j
x
i
x
j
+
i,j
x
i
x
j
i∈O
h
,j∈V
h
i,j∈V
h
,i≤j
γ
(
k
)
i
x
i
+
η
(
k
)
+
(
k
∈
O
h
)
,
(11)
i∈V
h
+1
where
α
(
k
)
i,j
,β
(
k
)
i,j
,γ
(
k
)
,η
(
k
)
L
.Notethat
g
k
is essentially a polynomial of
v
h
+
o
h
variables. We call variables
x
i
∈
i
V
j
) the Oil and Vinegar
variables, respectively. Then the central map of Rainbow is constructed by
(
i
∈
O
h
)and
x
j
(
i
∈
G
=(
g
v
1
+1
,...,g
n
):
L
n
L
n−v
1
.
→
Note that we can easily compute one of the preimages of
G
for any element of
L
n−v
1
.Forasystemof
o
h
equations for the
h
-th layer,
g
k
(
b
1
,...,b
v
h
,x
v
h
+1
,...,x
v
h
+1
)=
a
k
(
k
∈
O
h
)
L
o
h
and
becomes
o
h
linear equations of
o
h
variables for any (
a
v
h
+1
,...,a
v
h
+1
)
∈
L
v
h
. The values of the Oil variables in the
h
-th layer obtained by
solving these linear equations are used for the Vinegar variables in the (
h
+ 1)-th
layer.
Next, we describe the key generation, the signature generation and the veri-
fication of Rainbow.
(
b
1
,...,b
v
h
)
∈
Key Generation.
The secret key consists of the central map,
G
,andtwoane
transformations
A
1
:
L
m
L
m
(
m
=
n
v
1
)
,A
2
:
L
n
L
n
. The public
→
−
→
key consists of
L
, which is either a field,
K
,or
Z
/N
Z
, and the composed map
L
m
,whichisasystemof
m
quadratic polynomials
of
n
variables over
L
. In what follows, let us suppose that
F
is expressed as
F
=(
f
v
1
+1
,...,f
n
)
T
.
A
2
:
L
n
F
=
A
1
◦
G
◦
→
