Cryptography Reference
In-Depth Information
(
q
H
+
q
s
)
q
s
2
−l
.
Therefore,
A
outputs a forgery of a certain message with probability at least
(1
The probability that
B
answers to all queries is at least 1
−
−
(
q
H
+
q
s
)
q
s
2
−l
). Since the simulation of the random oracle is perfect and reveals
no information about
α
,
H
(
m
r
) corresponds to the challenge
y
, rather than to
another random value
h
if
,sothat
B
does not fail with probability 1
/
(
q
H
+
q
s
+1).
Therefore, the simulator
B
finds an inverse of
y
for
P
UOV
with probability at least
(1
−
(
q
H
+
q
s
)
q
s
2
−l
)
/
(
q
H
+
q
s
+1). Then,
||
(
q
H
+
q
s
)
q
s
2
−l
).
The running time of
B
is at most
t
+(
q
H
+
q
s
+1)(
t
UOV
+
O
(1)). Then,
t
(
q
H
+
q
s
+1)
/
(1
≤
−
≥
t
−
(
q
H
+
q
s
+1)(
t
UOV
+
O
(1)).
B HFEV Signature Schemes
Let
T
,
φ
,
q
,
n
,
d
,
k
,and
K
be the parameters defined in Definition 5. Let
S
:
k
n
+
v
→
k
n
+
v
be an invertible ane transformation
v
a positive inte-
φ
−
1
φ
−
1
ger, and a map
defined by
:
k
n
+
v
→
K
×
k
v
,
(
x
1
,...,x
n
+
v
)
→
(
φ
−
1
(
x
1
,...,x
n
)
,x
n
+1
,...,x
n
+
v
). The map
F
HFEV
is defined by
F
HFEV
:
K
×
k
v
→
K,
(
X, x
n
+1
,...,x
n
+
v
)
→
n−
1
n−
1
n−
1
a
ij
X
q
if
+
q
j
+
b
if
(
x
n
+1
,...,x
n
+
v
)
X
q
if
+
c
(
x
n
+1
,...,x
n
+
v
)
,
if
=0
j
=0
if
=0
where
q
if
+
q
j
>d
a
ij
,
q
if
>d
⇒
a
ij
=0for
∀
⇒
b
if
≡
0for
∀
b
if
,
a
ij
are secret
elements in
K
,and
b
if
:
k
n
K
and
c
:
k
n
K
are secret linear and quadratic
maps, respectively. The HFEV function is
P
HFEV
→
→
φ
−
1
S
and
its generator
GenHFEVfunc
is a probabilistic algorithm which takes a security
parameter 1
λ
and output (
P
HFEV
,
(
S, F
HFEV
,T
)), where
v
is bounded by polynomial
on
λ
.
Using the idea in Section 4.1 and 4.2, we define the modified HFEV signature
scheme (
GenHFEV
∗
,
SigHFEV
∗
,
VerHFEV
∗
) as follows. The key-generation algo-
rithm
GenHFEV
∗
(1
λ
), on input 1
λ
, runs (
P
HFEV
,
(
S, F
HFEV
,T
))
=
T
◦
φ
◦
F
HFEV
◦
◦
←
GenHFEVfunc
(1
λ
).
It outputs (
pk
,
sk
), where
pk
=(
P
HFEV
,l
),
sk
=(
S, F
HFEV
,T,l,N
),
l
is the length
of a random salt, and
N
is a threshold.
l
and
N
are bounded by polynomial on
λ
. The signing and verification algorithms use a hash function
H
:
{
0
,
1
}
∗
→
k
n
which maps a bit string of arbitrary length to an element in
k
n
.Thesigning
algorithm
SigHFEV
sk
(
M
)isasfollows:
Signing algorithm
SigHFEV
sk
(
M
)
1:
(
x
n
+1
,...,x
n
+
v
)
∈
R
k
v
;
2:
repeat
3:
l
;
y
φ
−
1
(
T
−
1
(
H
(
M
r
∈
R
{
0
,
1
}
←
||
r
)));
u
∈
R
{
1
,...,N
}
;
F
HFEV
(
z, x
n
+1
,...,x
n
+
v
)=
y
≤
u
≤
{
z
∈
K
|
}
4:
until
1
#
5:
x
∈
R
{
F
HFEV
(
z, x
n
+1
,...,x
n
+
v
)=
y
z
∈
K
|
}
;
6:
(
x
1
,...,x
n
)
φ
(
x
);
x
S
−
1
(
x
1
,...,x
n
+
v
);
←
←
7:
return
σ
=(
x, r
)
The verification algorithm
VerHFEV
pk
(
σ, M
), on input a signature
σ
=(
x, r
)and
a message
M
, returns 1 if
P
HFEV
(
x
)=
H
(
M
||
r
). Otherwise, it returns 0.
