Multivariate Public Key Cryptography (MPKC) is one of the main candidates for secure communication in a post-quantum era. Recently, Yasuda and Sakurai proposed at ICICS 2015 a new multivariate encryption scheme called SRP, which offers efficient decryption, a small blow up factor between plaintext and ciphertext and resists all known attacks against multivariate schemes. However, similar to other MPKC schemes, the key sizes of SRP are quite large. In this paper we propose a technique to reduce the key size of the SRP scheme, which enables us to reduce the size of the public key by up to 54%. Furthermore, we can use the additional structure in the public key polynomials to speed up the encryption process of the scheme by up to 50%. We show by experiments that our modifications do not weaken the security of the scheme.

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.

ZHFE, proposed by Porras et al. at PQCrypto'14, is one of the very few existing multivariate encryption schemes and a very promising candidate for post-quantum cryptosystems. The only one drawback is its slow key generation. At PQCrypto'16, Baena et al. proposed an algorithm to construct the private ZHFE keys, which is much faster than the original algorithm, but still inefficient for practical parameters. Recently, Zhang and Tan proposed another private key generation algorithm, which is very fast but not necessarily able to generate all the private ZHFE keys. In this paper we propose a new efficient algorithm for the private key generation and estimate the number of possible keys generated by all existing private key generation algorithms for the ZHFE scheme. Our algorithm generates as many private ZHFE keys as the original and Baena et al.'s ones and reduces the complexity from O(n2ω+1) by Baena et al. to O(nω+3), where n is the number of variables and ω is a linear algebra constant. Moreover, we also analyze when the decryption of the ZHFE scheme does not work.