IACR News item: 29 May 2012
Yun-Ju Huang, Feng-Hao Liu, Bo-Yin Yang
ePrint Report
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.
Additional news items may be found on the IACR news page.