Cryptography Reference
In-Depth Information
On Provable Security of UOV and HFE
Signature Schemes against Chosen-Message
Attack
Koichi Sakumoto, Taizo Shirai, and Harunaga Hiwatari
Sony Corporation
5-1-12 Kitashinagawa Shinagawa-ku, Tokyo 141-0001, Japan
{
Koichi.Sakumoto,Taizo.Shirai,Harunaga.Hiwatari
}
@jp.sony.com
Abstract.
The multivariate public key cryptosystem (MPKC) is con-
sidered to be one of the candidates of post-quantum cryptography. Un-
balanced Oil-Vinegar (UOV) scheme and Hidden Field Equation (HFE)
scheme are well-known schemes in MPKC. However, little attention has
been given to provable security for these schemes. In this paper, we study
the provable security of the UOV and the HFE signature schemes in the
sense of the existential unforgeability against adaptive chosen-message
attack (EUF-CMA). Concretely, we suggest that a usual security proof
for the Full-Domain Hash scheme cannot directly apply to that of the
UOV and the HFE signature schemes. However, we show that the UOV
and the HFE signature schemes can be modified into ones achieving the
EUF-CMA in the random oracle model, without changing each underly-
ing trapdoor function.
Keywords:
signature scheme, MPKC, multivariate, distribution, UOV,
HFE, provable security.
1
Introduction
One of the recent research challenges in public key cryptography is to find alter-
native public key cryptosystem which has resistance to a quantum computer [3].
The multivariate public key cryptosystem (MPKC) is one of the candidates for
post-quantum cryptography. MPKC is based on a problem of solving a sys-
tem of multivariate quadratic polynomials, which is called an MQ problem [9].
The Unbalanced Oil-Vinegar (UOV) scheme [16] and the Hidden Field Equation
(HFE) scheme [22] are well-known and deeply studied schemes in MPKC. These
schemes use a trapdoor one-way function whose security relies both on the MQ
problem and on the Isomorphism of Polynomials (IP) problem. Compared with
RSA, the computation in MPKC can be implemented eciently [4,7], since the
arithmetic operations are performed over a small finite field.
Many digital signature schemes based on integer factoring or discrete log-
arithm achieve the existential unforgeability against adaptive chosen-message
attack (EUF-CMA) [14]. Recently, Sakumoto et al. proposed provably secure
identification/signature schemes based on the MQ problem [25]. By contrast,
