request@qapp.tech
RU
Multivariate cryptography

Summary

A robust family of quantum-resistant cryptographic algorithms based on the assumed computational complexity of solving systems of nonlinear multivariable equations over a finite field. In particular, certain digital signature algorithms, such as Rainbow (NIST post-quantum competition finalist) and GeMSS (NIST post-quantum competition alternate finalist), are based on this particular problem. Cryptographic algorithms from this family are relatively efficient and provide small signatures for large keys.
    More on the topic

    The potential appearance of a quantum computer able to implement Shor's algorithm poses a threat to traditional digital signature schemes based on factorization and discrete logarithm problems. So, it has been proposed to use multivariate cryptography as a countermeasure.

    This class of cryptographic algorithms is based on the complex problem of solving a system of polynomial equations over a finite field. Generally, this problem is NP-complete. There are several methods of solving it, including linearization methods (XL), methods based on Gröbner bases (F4, F5 etc.). However, as the number of variables increases, these methods quickly become inefficient.
      The first multivariate cryptographic scheme was proposed in 1988 by T. Matsumoto and H. Imai. The scheme was hacked in 1995 by J. Patarin.

      In turn, he developed the so-called HFE (Hidden Field Equations) scheme in 1996. However, in 2005 A. Shamir proposed an efficient attack to compromise it.

      Another scheme worth mentioning is the digital signature scheme SFLASH. In 2003 it became the winner of the NESSIE research project, but already in 2007, it was compromised.

      In addition to HFE, J. Patarin has developed the original UOV (Unbalanced Oil and Vinegar) digital signature scheme, which has later become the prototype for many of the current UOV schemes, such as LUOV and Rainbow, both participants of the NIST post-quantum competition.
      The private key of a multivariate polynomial-based scheme consists of a triple: one easy-to-invert quadratic map and two invertible linear maps. The public key is their composition – a random nonlinear transformation. To encrypt a message, one needs to apply a transformation corresponding to the public key to it. For decryption, one applies the inverse of the private-key transformations to the message one by one.

      The main challenges associated with multivariate cryptographic algorithms are:
      • the private transformation has a definite structure, necessary for the efficiency, but at the same time, it makes it possible to construct specific algebraic attacks;
      • quadratic equation systems over a finite field determine rather large key lengths.

      Many years of successfully cryptanalyzing this algorithm class demonstrate how necessary it is to be particularly careful when selecting synthesis parameters.

      At the same time these algorithms are relatively simple and efficient compared to other quantum-resistant algorithms. Moreover, they have relatively small signatures.
        How to implement multivariate cryptography for business data protection?

        The QApp team attaches great significance to studying multivariate cryptographic algorithms, including the digital signature algorithm Rainbow — the NIST post-quantum competition finalist.