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

Access this Article

Author(s)

    • WANG Yacheng
    • Graduate School of Information Science and Technology, The University of Tokyo
    • IKEMATSU Yasuhiko
    • Graduate School of Information Science and Technology, The University of Tokyo
    • DUONG Dung Hoang
    • School of Computing and Information Technology, University of Wollongong
    • TAKAGI Tsuyoshi
    • Graduate School of Information Science and Technology, The University of Tokyo

Abstract

<p>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 EFC<i><sub>p</sub></i><sup>-</sup> and EFC<sub><i>pt</i><sup>2</sup></sub><sup>-</sup> 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 EFC<i><sub>p</sub></i><sup>-</sup> and EFC<sub><i>pt</i><sup>2</sup></sub><sup>-</sup>, 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 EFC<i><sub>p</sub></i><sup>-</sup> and EFC<sub><i>pt</i><sup>2</sup></sub><sup>-</sup> through a hybrid attack of algebraic attack and exhaustive search.</p>

Journal

  • IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E102.A(9), 1028-1036, 2019

    The Institute of Electronics, Information and Communication Engineers

Codes

Page Top