Cryptography Reference
In-Depth Information
The UOV function and its security notion are defined as follows.
Definition 3.
Let
S
:
k
n
+
v
k
n
+
v
be an invertible ane transformation,
n
and
v
positive integers,
k
a finite field with cardinality
q
,and
F
UOV
:
k
n
+
v
amap
→
→
k
n
,
(
x
1
,...,x
n
+
v
)
→
(
f
1
,...,f
n
)
.
f
ξ
is defined by
f
ξ
=
α
ξij
x
i
x
j
+
α
ξij
x
i
x
j
+
β
ξi
x
i
+
γ
ξ
,
1
≤i≤n<j≤n
+
v
n<i,j≤n
+
v
1
≤i≤n
+
v
for
ξ
=1
,...,n
. In this paper, we denote
x
n
=(
x
1
,...,x
n
)
,
x
v
=(
x
n
+1
,
...,x
n
+
v
)
,andthemap
F
UOV
as
T
x
v
))
T
,
F
UOV
(
x
n
,
x
v
)=
A
(
x
v
)
x
n
+(
g
1
(
x
v
)
,...,g
n
(
where
A
(
x
v
)=[
a
i,j
(
x
v
)]
is an
n
×
n
matrix whose entries
a
i,j
are polynomi-
als of the first degree on
x
n
+1
,...,x
n
+
v
and
g
i
(
x
v
)
is a quadratic polynomial
on
x
n
+1
,...,x
n
+
v
.
x
1
,...,x
n
are called oil variables and
x
n
+1
,...,x
n
+
v
are
called vinegar variables. The UOV function is defined as
P
UOV
S
and
its generation algorithm
GenUOVfunc
is a probabilistic algorithm which takes a
security parameter
1
λ
and output
(
P
UOV
,
(
S, F
UOV
))
,where
q
,
n
,and
v
are bounded
by polynomial on
λ
.
=
F
UOV
◦
Definition 4.
We say that the UOV function generator
GenUOVfunc
is
(
t
(
λ
)
,
(
λ
))
-secure if there is no inverting algorithm that takes as input
P
UOV
generated
via
(
P
UOV
,
∈
R
k
n
, then finds a preimage
x
such that
P
UOV
(
x
)=
y
at
t
(
λ
)
processing time with probability at least
(
λ
)
.
←
GenUOVfunc
(1
λ
)
and a challenge
y
·
)
The UOV signature scheme (
GenUOV
,
SigUOV
,
VerUOV
) is an FDH-like scheme
using the UOV function [16]. If the vinegar variable are fixed to
x
v
, the function
F
UOV
(
x
v
) is defined by a set of linear functions on oil variables
x
n
.Thesigning
algorithm, for a hash value
y
, first randomly chooses the vinegar variables
x
n
,
x
v
and
then computes unknown oil variables
x
n
by solving the linear equation system
x
v
)=
y
. If there is no solution, then we simply retry by choosing new
random vinegar variables
F
UOV
(
x
n
,
x
v
.
The details of the scheme are the follows. The key-generation algorithm
GenUOV
(1
λ
), on input 1
λ
, runs (
P
UOV
,
(
S, F
UOV
))
←
GenUOVfunc
(1
λ
). It outputs
(
pk
,
sk
), where
pk
=
P
UOV
and
sk
=(
S, F
UOV
). The signing and the verification
algorithms use a hash function
H
:
k
n
which maps a bit string of arbi-
trary length to an element in
k
n
. The signing algorithm
SigUOV
sk
}
∗
→
{
0
,
1
(
M
) is as follows.
Signing algorithm
SigUOV
sk
(
M
)
1:
y
H
(
M
);
2:
repeat
3:
←
x
v
∈
R
k
v
;
4:
until
x
v
)=
y
{
z
n
|
F
UOV
(
z
n
,
}
=
∅
x
n
∈
R
{
z
n
|
x
v
)=
y
F
UOV
(
z
n
,
}
;
5:
x
v
);
7:
return
σ
=
x
S
−
1
(
x
n
,
6:
x
←
