The Secure Parameters and Efficient Decryption Algorithm for Multivariate Public Key Cryptosystem EFC

Yacheng WANG  Yasuhiko IKEMATSU  Dung Hoang DUONG  Tsuyoshi TAKAGI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.9   pp.1028-1036
Publication Date: 2019/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.1028
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Cryptography and Information Security
multivariate cryptography,  extension field cancellation,  decryption algorithm,  hybrid attack,  

Full Text: FreePDF

At PQCrypto 2016, Szepieniec et al. proposed a new type of trapdoor called Extension Field Cancellation (EFC) for constructing secure multivariate encryption cryptosystems. They also specifically suggested two schemes EFCp- and EFCpt2- that apply this trapdoor and some modifiers. Although both of them seem to avoid all attacks used for cryptanalysis on multivariate cryptography, their decryption efficiency has room for improvement. On the other hand, their security was analyzed mainly through an algebraic attack of computing the Gröbner basis of the public key, and there possibly exists more effective attacks. In this paper, we introduce a more efficient decryption approach for EFCp- and EFCpt2-, which manages to avoid all redundant computation involved in the original decryption algorithms without altering their public key. In addition, we estimate the secure parameters for EFCp- and EFCpt2- through a hybrid attack of algebraic attack and exhaustive search.