On Provable Security of UOV and HFE Signature Schemes against Chosen-Message Attack

摘要

The multivariate public key cryptosystem (MPKC) is considered to be one of the candidates of post-quantum cryptography. Unbalanced 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 underlying trapdoor function.