A Secure Variant of Yasuda, Takagi and Sakurai's Signature Scheme

摘要

Yasuda, Takagi and Sakurai proposed a new signature scheme in PQCrypto 2013 using quadratic forms over finited fields of odd characteristic. Later on two independent attacks were proposed by Hashimoto in PQCrypto 2014 and by Zhang and Tan in ICISC 2014 to break their scheme. The purpose of this paper is to fix the security problem of Yasuda, Takagi and Sakurai's scheme. We achieve this purpose by mixing their scheme with a special type HFEv polynomials to produce a new scheme, YTS-HFEv. We analyze its security and propose a practical parameter set with public key size about 57 KB and security level 2~(80).