Welcome to the resource topic for 2012/273
Title:
Public-Key Cryptography from New Multivariate Quadratic Assumptions
Authors: Yun-Ju Huang, Feng-Hao Liu, Bo-Yin Yang
Abstract: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.
ePrint: https://eprint.iacr.org/2012/273
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .