Paper 2012/328

The Multivariate Probabilistic Encryption Scheme MQQ-ENC

Danilo Gligoroski and Simona Samardjiska

Abstract

We propose a new multivariate probabilistic encryption scheme with decryption errors MQQ-ENC that belongs to the family of MQQ-based public key schemes. Similarly to MQQ-SIG, the trapdoor is constructed using quasigroup string transformations with multivariate quadratic quasigroups, and a minus modifier with relatively small and fixed number of removed equations. To make the decryption possible and also efficient, we use a universal hash function to eliminate possibly wrong plaintext candidates. We show that, in this way, the probability of erroneous decryption becomes negligible. MQQ-ENC is defined over the fields $\mathbb{F}_{2^k}$ for any $k \geq 1$, and can easily be extended to any $\mathbb{F}_{p^k}$, for prime $p$. One important difference from MQQ-SIG is that in MQQ-ENC we use left MQQs (LMQQs) instead of bilinear MQQs. Our choice can be justified by our extensive experimental analysis that showed the superiority of the LMQQs over the bilinear MQQs for the design of MQQ-ENC. We apply the standard cryptanalytic techniques on MQQ-ENC, and from the results, we pose a plausible conjecture that the instances of the MQQ-ENC trapdoor are hard instances with respect to the MQ problem. Under this assumption, we adapt the Kobara-Imai conversion of the McEliece scheme for MQQ-ENC and prove that it provides $\mathsf{IND-CCA}$ security despite the negligible probability of decryption errors. We also recommend concrete parameters for MQQ-ENC for encryption of blocks of 128 bits for a security level of $\mathcal{O}(2^{128})$.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Accepted for oral presentation at SCC 2012
Keywords
Multivariate Quadratic Quasigroup MQQLeft Multivariate Quadratic Quasigroup LMQQOne way encryption$\mathsf{IND-CCA}$ security
Contact author(s)
simonas @ item ntnu no
History
2012-06-12: received
Short URL
https://ia.cr/2012/328
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/328,
      author = {Danilo Gligoroski and Simona Samardjiska},
      title = {The Multivariate Probabilistic Encryption Scheme MQQ-ENC},
      howpublished = {Cryptology ePrint Archive, Paper 2012/328},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/328}},
      url = {https://eprint.iacr.org/2012/328}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.