Cryptography Reference
In-Depth Information
q
,
g
(
x
)
k
[
x
]
an irreducible polynomial of degree
n
,
K
=
k
[
x
]
/g
(
x
)
afieldwith
adegree
n
extension of
k
,and
F
HFE
:
K
∈
→
K
defined by
n−
1
n−
1
n−
1
a
ij
X
q
i
+
q
j
+
b
i
X
q
i
+
c,
F
HFE
(
X
)=
i
=0
j
=0
i
=0
n, q
i
+
q
j
>d
where
a
ij
,b
i
,c
∈
K
such that
∀
a
ij
,
1
≤
i, j
≤
⇒
a
ij
=0
n, q
i
>d
and
∀
b
i
,
1
≤
i
≤
⇒
b
i
=0
. That is,
d
is the maximum degree of
φ
−
1
F
HFE
.TheHFEfunctionis
P
HFE
S
and its generator
GenHFEfunc
is a probabilistic algorithm which takes a security parameter
1
λ
and
output
(
P
HFE
,
(
S, F
HFE
,T
))
,where
q
,
n
,and
d
are bounded by polynomial on
λ
.
=
T
◦
φ
◦
F
HFE
◦
◦
Definition 6.
We say that the HFE function generator
is
GenHFEfunc
(
t
(
λ
)
,
(
λ
))
-secure if there is no inverting algorithm that takes
P
HFE
generated
∈
R
k
n
, then finds a preimage
x
such that
P
HFE
(
x
)=
y
at
t
(
λ
)
processing time with probability at least
(
λ
)
.
←
GenHFEfunc
(1
λ
)
and a challenge
y
via
(
P
HFE
,
·
)
The HFE signature scheme (
GenHFE
,
SigHFE
,
VerHFE
) is a PFDH-like scheme
using a neither surjective nor injective function, the HFE function
P
HFE
.The
key-generation algorithm
GenHFE
(1
λ
), on input 1
λ
, runs (
P
HFE
,
(
S, F
HFE
,T
))
←
GenHFEfunc
(1
λ
). It outputs (
pk
,
sk
), where
pk
=
P
HFE
and
sk
=(
S, F
HFE
,T
). The
signing and the verification algorithms use a hash function
H
:
k
n
which maps a bit string of arbitrary length to an element in
k
n
.Thesigning
algorithm
SigHFE
sk
}
∗
→
{
0
,
1
(
M
)isasfollows.
Signing algorithm
SigHFE
sk
(
M
)
1:
r
0;
2:
repeat
3:
←
φ
−
1
(
T
−
1
(
H
(
r, M
)));
r
y
←
←
r
+1;
4:
until
{
z
|
F
HFE
(
z
)=
y
}
=
∅
5:
x
∈
R
{
S
−
1
(
φ
(
x
));
z
|
F
HFE
(
z
)=
y
}
;
x
←
6:
return
σ
=(
x, r
)
The verification algorithm
VerHFE
pk
(
σ, M
), on a signature
σ
=(
x, r
)anda
message
M
, returns 1 if
P
HFE
(
x
)=
H
(
r, M
). Otherwise, it returns 0. Note that,
x
∈
R
{
z
|
F
HFE
(
z
)=
y
}
at the step 5 can be computed by using the Berlekamp
algorithm.
In the signing algorithm, it repeats the loop until
.
In Quartz [24] which uses a variant of the HFE function, it loops until
#
{
z
|
F
HFE
(
z
)=
y
}
=
∅
{
z
|
F
HFE
(
z
)=
y
}
= 1. The algorithm outputs only
x
such that
x
always has no
2nd preimage.
Analysis of the scheme.
It is known that each element in target space of the HFE
function has various number of preimage [9]. This means that the output of the
signing algorithm is non-uniformly distributed even though
H
(
r, M
) distributes
uniformly. Suppose that
x
0
is an element in domain such that
P
HFE
(
x
0
)has
i
preimages. Then, the signing algorithm returns
x
0
without repeating loops with
