Cryptography Reference
In-Depth Information
can also be modified similarly. Let the HFE
−
function generator
GenHFEfunc
−
be a probabilistic algorithm which takes a security parameter 1
λ
and out-
puts (
P
HFE
−
,
(
S, F
HFE
,T,m
)), where
m
is the number of neglected polynomials
whichislessthan
n
. The key-generation algorithm
GenHFE
−∗
, on input 1
λ
,
runs (
P
HFE
−
,
(
S, F
HFE
,T,m
))
←
GenHFEfunc
−
(1
λ
). It outputs (
pk
,
sk
), where
pk
=(
P
HFE
−
,l
),
sk
=(
S, F
HFE
,T,l,m,N
),
l
is the length of a random salt bounded
by polynomial on
λ
,and
N
is a threshold which is
d
or less. In the signing and
the verification algorithms, a random salt
r
of
l
bits is concatenated to the mes-
sage
M
before hashing, and a hash function
H
:
}
∗
→
k
n−m
is used. The
{
0
,
1
signing algorithm
SigHFE
−∗
is the follows.
Signing algorithm
SigHFE
−∗
sk
(
M
)
1:
repeat
2:
l
;(
h
1
,...,h
n−m
)
∈
R
k
m
;
r
∈
R
{
0
,
1
}
←
H
(
M
||
r
); (
h
n−m
+1
,...,h
n
)
φ
−
1
(
T
−
1
(
h
1
,...,h
n
));
u
y
←
∈
R
{
1
,...,N
}
;
3:
4:
until
1
≤
u
≤
#
{
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 input a signature
σ
=(
x, r
)and
a message
M
, returns 1 if
P
HFE
−
(
x
)=
H
(
M
r
). Otherwise, it returns 0. We treat
the hash function as the random oracle in our analysis. If
l
is large enough, then
a random salt
r
is fresh every time with overwhelming probability. Therefore,
each
H
(
M
||
r
) is independently and uniformly distributed over
k
n−m
,andthe
output
x
and
r
of the above signing algorithm are also uniformly distributed
over
k
n
and over
||
l
, respectively.
Then, we show the security of the above modified HFE scheme against chosen-
message attack.
Theorem 2.
When a threshold
N
is equal to the max degree
d
of
F
HFE
,ifthe
HFE
−
function generator is
(
,t
)
-secure, then the modified HFE
−
scheme is
(
, t, q
H
,q
s
)
-secure, where
=
(
q
H
+
q
s
+1)
/
(1
{
0
,
1
}
(
q
H
+
q
s
)
q
s
2
−l
)
,
t
=
t
−
(
q
H
+
q
s
+1)(
t
HFE
−
+
O
(1))
,and
t
HFE
−
is running time to compute the HFE
−
function
P
HFE
−
.
Since the proof of Theorem 2 is almost the same proof to that of Theorem 1, it
isomittedinthispaper.
−
Eciency of the modified scheme.
Inthecaseof
N
=
d
, for each element
x
in
domain, the signing algorithm returns
x
without repeating loops with probability
1
/q
n
1
/N
. For the case of
N<d
, the probability is almost the same if
N
is large enough. Therefore, it returns without repeating loops with probability
1
/q
n
·
q
n
=1
/N
. The expected number of loops is
N
. On the other hand, in
the original signing algorithm, it returns without repeating loops with probability
1
·
1
/N
·
−
1
/e
. So the expected number of loops is 1
/
(1
−
1
/e
)
≈
1
.
58. We can see that the
expected number of loops in our modified scheme is (1
0
.
63
N
times
more than in the original scheme. The cost of key generation and verification
are identical to the original one.
−
1
/e
)
N
≈
