From MQ to MQQ Cryptography: Weaknesses & New Solutions

Abstract. Public Key Cryptosystems have been in use for more than three decades. A number of schemes based on integer factorization problem, discrete log problem, residuosity problem, digital signature methods, Lucas sequence, Lattice problems, error-correcting codes, braid groups etc. have been designed. Recently, Multivariate Quadratic (MQ) Polynomials could be efficiently used for design of a number of interesting cryptosystems. However, successful attacks on some of these schemes encouraged researchers to design new trapdoor functions suitable for present cryptographic applications. Multivariate Quadratic Quasigroup (MQQ) has been one of the latest ideas in this direction but is limited to the construction of MQQ of lower orders. Our significant contribution in this direction is efficient generation of MQQs of higher order suitable for design of secure public key cryptosystems