Cryptography Reference
In-Depth Information
probability 1
/q
n
1
/i
. In particular, the probability that
x
1
is chosen is
i
2
/i
1
times higher than
x
2
is chosen, where the number of preimage of
P
HFE
(
x
1
)and
P
HFE
(
x
2
)be
i
1
and
i
2
, respectively.
To simulate the signing oracle in the security proof, it is required to sample
signatures from the real distribution. However, it seems to be dicult for the
HFE scheme, since the structure of
F
HFE
is hidden due to the pair of secret
mappings
S
and
T
. The same thing may be said of the Quartz-like scheme.
·
4 Slightly Modified Schemes
In the UOV-based and the HFE-based schemes, it might be dicult to sam-
ple from the actual distribution of signatures without knowledge of the secret
key. This is an obstacle for the provable security against chosen-message attack.
To solve this problem, we slightly modify the signing algorithm whose output
is uniformly distributed. Note that we do not change the underlying trapdoor
function.
In this section, for each of the UOV and the HFE functions, we present basic
idea for the simple modification of the signing algorithm, a proof of the security
against chosen-message attack, and analysis of its eciency.
4.1 Modified UOV Signature Scheme
A basic idea for the modification of the UOV signing algorithm is to use a
random salt hashed with a message, and to re-choose a random salt instead
of vinegar variables. In the original signing algorithm, the higher the rank of
A
(
x
v
) is, the higher the probability of ending the loop is. This means that
such a set of vinegar variables causing higher rank tends to be output more
frequently by signing algorithm. In our modified UOV signature scheme, hash
values
y
are generated via
y
←
H
(
M
||
r
)where
r
is a random salt. If the linear
x
v
)=
H
(
M
equation system represented as
F
UOV
(
r
) has no solution, then
the signer tries again with new random salt
r
and generates hash value
H
(
M
x
n
,
||
||
r
)
x
v
is uniformly
instead of choosing new vinegar variables. As a result, the output
x
n
is also uniformly distributed, since if
A
(
x
v
)hasrank
distributed. The output
x
v
)is
q
n−i
-to-1 mapping for each element in the range.
The modified UOV signature scheme (
GenUOV
∗
,
SigUOV
∗
,
i
,amap
x
n
→
F
UOV
(
x
n
,
VerUOV
∗
)isde-
GenUOV
∗
, on input 1
λ
, runs
fined as follows. The key-generation algorithm
←
GenUOVfunc
(1
λ
). It outputs (
pk
,
sk
), where
pk
=(
P
UOV
,l
),
sk
=(
S, F
UOV
,l
), and
l
is a length of the random salt bounded by polynomial on
λ
.
GenUOV
∗
is the same as the original
GenUOV
except that public and secret keys
contain
l
. The signing algorithm
SigUOV
∗
is the follows.
(
P
UOV
,
(
S, F
UOV
))
Signing algorithm
SigUOV
sk
(
M
)
1:
x
v
∈
R
k
v
;
2:
repeat
3:
l
;
y
r
∈
R
{
0
,
1
}
←
H
(
M
||
r
);
