Paper 2008/320

Public Key Block Cipher Based on Multivariate Quadratic Quasigroups

Danilo Gligoroski, Smile Markovski, and Svein J. Knapskog


We have designed a new class of public key algorithms based on quasigroup string transformations using a specific class of quasigroups called \emph{multivariate quadratic quasigroups (MQQ)}. Our public key algorithm is a bijective mapping, it does not perform message expansions and can be used both for encryption and signatures. The public key consist of $n$ quadratic polynomials with $n$ variables where $n=140, 160, \ldots$. A particular characteristic of our public key algorithm is that it is very fast and highly parallelizable. More concretely, it has the speed of a typical modern symmetric block cipher -- the reason for the phrase \emph{"A Public Key Block Cipher"} in the title of this paper. Namely the reference C code for the 160--bit variant of the algorithm performs decryption in less than 11,000 cycles (on Intel Core 2 Duo -- using only one processor core), and around 6,000 cycles using two CPU cores and OpenMP 2.0 library. However, implemented in Xilinx Virtex-5 FPGA that is running on 249.4 MHz it achieves decryption throughput of 399 Mbps, and implemented on four Xilinx Virtex-5 chips that are running on 276.7 MHz it achieves encryption throughput of 44.27 Gbps. Compared to fastest RSA implementations on similar FPGA platforms, MQQ algorithm is more than 10,000 times faster.

Available format(s)
Publication info
Published elsewhere. Updated and extended version of the paper presented at MATH'08 - Cambridge, Massachusetts, USA, March 24-26, 2008.
Key CryptosystemsFast signature generationMultivariate Quadratic PolynomialsQuasigroup String TransformationsMultivariate Quadratic Quasigroup
Contact author(s)
danilog @ item ntnu no
2008-08-02: revised
2008-08-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Danilo Gligoroski and Smile Markovski and Svein J.  Knapskog},
      title = {Public Key Block Cipher Based on Multivariate Quadratic Quasigroups},
      howpublished = {Cryptology ePrint Archive, Paper 2008/320},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.