Practical Cryptanalysis of a Public-Key Encryption Scheme Based on New Multivariate Quadratic Assumptions
In this paper, we investigate the security of a public-key encryption scheme introduced by Huang, Liu and Yang (HLY) at PKC’12. This new scheme can be provably reduced to the hardness of solving a set of quadratic equations whose coefficients of highest d
- PDF / 337,871 Bytes
- 19 Pages / 439.363 x 666.131 pts Page_size
- 41 Downloads / 208 Views
Abstract. In this paper, we investigate the security of a public-key encryption scheme introduced by Huang, Liu and Yang (HLY) at PKC’12. This new scheme can be provably reduced to the hardness of solving a set of quadratic equations whose coefficients of highest degree are chosen according to a discrete Gaussian distributions. The other terms being chosen uniformly at random. Such a problem is a variant of the classical problem of solving a system of non-linear equations (PoSSo), which is known to be hard for random systems. The main hypothesis of Huang, Liu and Yang is that their variant is not easier than solving PoSSo for random instances. In this paper, we disprove this hypothesis. To this end, we exploit the fact that the new problem proposed by Huang, Liu and Yang reduces to an easy instance of the Learning With Errors (LWE) problem. The main contribution of this paper is to show that security and efficiency are essentially incompatible for the HLY proposal. That is, one cannot find parameters which yield a secure and a practical scheme. For instance, we estimate that a public-key of at least 1.03 GB is required to achieve 80-bit security against the simplest of our attacks. As a proof of concept, we present 3 practical attacks against all the parameters proposed by Huang, Liu and Yang. With the most efficient attack, we have been able to recover the private-key in roughly 5 minutes for the first challenge i.e. Case 1 proposed by HLY and less than 30 minutes for the second challenge i.e. Case 2 .
1 Introduction At PKC 2012 Huang, Liu and Yang (HLY) proposed a new public-key encryption scheme [17]. It follows a line of research, called Multivariate Quadratic (MQ) H. Krawczyk (Ed.): PKC 2014, LNCS 8383, pp. 446–464, 2014. c International Association for Cryptologic Research 2014
Practical Cryptanalysis of a Public-Key Encryption Scheme
447
cryptography, to construct public-key encryption schemes from the known hard problem of solving systems of polynomial equations. This line of research dates back to the mid eighties with the design of C∗ [24], later followed by many other proposals. While this family of designs is commonly considered to be an interesting alternative to constructions based on number-theoretic problems (in the post-quantum setting), it suffers from a lack of clear security reductions to well-understood problems, leading to a series of attacks. In contrast, [17] is part of a recent trend in MQ cryptography of designing cryptosystems whose security can be provably reduced to the the hardness of solving a system of non-linear equations (other examples include [3,8]). The key innovation of HuangLiu-Yang [17] is a MQ scheme in which the public key is noise-free and non-linear but ciphertexts are noisy and linear. Hence, the scheme proposed by Huang, Liu, and Yang can be viewed as a hybrid between the Learning with Errors (LWE) problem [27] and MQ cryptosystems. The semantic security of the scheme [17] can be provably reduced to the difficulty of solving a system of non-linear equations which i
Data Loading...
