Cryptography Reference
In-Depth Information
and many-to-one [13]. Their trapdoor function
f
satisfies two crucial properties
which are used in the proof of the security for FDH-like signature schemes. First,
f
(
x
) is uniformly distributed when
x
is sampled from a certain distribution
D
. Second, the inversion algorithm of the trapdoor function does not just find
an arbitrary preimage of the input but samples from its preimages under the
appropriate conditional distribution related to
D
. On the other hand, we just
modify the signing algorithm to provide uniform distribution of the signatures,
keeping the underlying trapdoor function untouched.
Organization.
In Section 2 we briefly review some notations and definitions used
throughout this paper. In Section 3 we review the UOV and the HFE signature
schemes and analyze their signature distribution. In Section 4, we describe the
modifications of these signature schemes and prove their EUF-CMA. Section 5
and Section 6 give some extensions and conclusion, respectively.
2 Preliminaries
We start by recalling the definition of a signature scheme.
Definition 1.
Asignaturescheme
(
Gen
,
Sig
,
Ver
)
is defined as follows:
The key-generation algorithm
Gen
is a probabilistic algorithm which given
1
λ
, outputs a pair of matching public and private keys,
(
pk
,
sk
)
.
The signing algorithm
Sig
is a probabilistic algorithm which takes the mes-
sage
M
to be signed and a secret key sk, and returns a signature
σ
=
Sig
sk
(
M
)
.
The verification algorithm
Ver
takes a message
M
, a candidate signature
σ
and pk, and returns a bit
Ver
pk
(
M, σ
)
. The signature is accepted, only
if the bit is equal to one. Otherwise, it is rejected. If
σ
←
Sig
sk
(
M
)
,then
Ver
pk
(
M, σ
)=1
.
In the existential unforgeability under the adaptive chosen message attack sce-
nario [14], the forger can obtain signatures on messages of his adaptive choices
and attempt to output a valid forgery. A valid forgery is a message/signature
pair (
M, σ
) such that
Ver
pk
(
M, σ
) = 1 whereas the forger never requests the sig-
nature on
M
. The security against chosen-message attack, in the random oracle
model, is defined as follows.
Definition 2.
We say that a signature scheme
(
Gen
,
Sig
,
Ver
)
is
(
t
(
λ
)
,q
s
(
λ
)
,
q
H
(
λ
)
,
(
λ
))
-secure if there is no forger
A
who takes a public key pk generated
via
(
pk
, ·
)
←
Gen
(1
λ
)
,afteratmost
q
H
(
λ
)
queries to the random oracle,
q
s
(
λ
)
signature queries, and
t
(
λ
)
processing time, then outputs a valid signature with
probability at least
(
λ
)
.
Rank of a Random Matrix.
Especially, we refer the equation (3) in the paper [19].
This formula gives the probability
p
(
q, m, n, i
) that a random
m
×
n
matrix
A
on
afield
k
with cardinality
q
has the rank
i
(
i>
0) where
m
≤
n
.Then
p
(
q, m, n, i
)
is equal to
