Paper 2012/273

Public-Key Cryptography from New Multivariate Quadratic Assumptions

Yun-Ju Huang, Feng-Hao Liu, and Bo-Yin Yang


In this work, we study a new multivariate quadratic (MQ) assumption that can be used to construct public-key encryption schemes. In particular, we research in the following two directions: We establish a precise \emph{asymptotic} formulation of a family of hard MQ problems, and provide empirical evidence to confirm the hardness. %Since there are many practical solvers studied and implemented during the studies of algebraic attacks, we use We construct public-key encryption schemes, and prove their security under the hardness assumption of this family. Also, we provide a new \emph{perspective} to look at MQ systems that plays a key role to our design and proof of security. As a consequence, we construct the \emph{first} public-key encryption scheme that is \emph{provably secure} under the MQ assumption. Moreover, our public-key encryption scheme is efficient in the sense that it only needs a ciphertext length $L + \poly(k)$ to encrypt a message $M\in \{0, 1 \}^{L}$ for any un-prespecified polynomial $L$, where $k$ is the security parameter. This is essentially \emph{optimal} since an additive overhead is the best we can hope for.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. full version of the paper published at PKC 2012
public key encryptionmultivariate quadratic equations
Contact author(s)
fenghao @ cs brown edu
2012-05-29: received
Short URL
Creative Commons Attribution


      author = {Yun-Ju Huang and Feng-Hao Liu and Bo-Yin Yang},
      title = {Public-Key Cryptography from New Multivariate Quadratic Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2012/273},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.