Multivariate cryptography

<h2 id="history">History</h2>
<p>Tsutomu Matsumoto and <a href="/facts/Hideki_Imai/1XHvIse3">Hideki Imai</a> (1988) presented their so-called C* scheme at the <a href="/facts/Eurocrypt/TgVIMDmb">Eurocrypt</a> conference. Although C* has been broken by Jacques Patarin (1995), the general principle of Matsumoto and Imai has inspired a generation of improved proposals. In later work, the "Hidden Monomial Cryptosystems" was developed by (in French) Jacques Patarin. It is based on a ground and an extension field. "<a href="/facts/Hidden_Field_Equations/NyUA3uca">Hidden Field Equations</a>" (HFE), developed by Patarin in 1996, remains a popular multivariate scheme today [P96]. The security of HFE has been thoroughly investigated, beginning with a direct <a href="/facts/Gr%25C3%25B6bner_basis/efMrjM7w">Gröbner basis</a> attack [FJ03, GJS06], key-recovery attacks (Kipnis & Shamir 1999) [BFP13], and more. The plain version of HFE is considered to be practically broken, in the sense that secure parameters lead to an impractical scheme. However, some simple variants of HFE, such as the <i>minus variant</i> and the <i>vinegar variant</i> allow one to strengthen the basic HFE against all known attacks. 
</p><p>In addition to HFE, Patarin developed other schemes. In 1997 he presented “Balanced Oil & Vinegar” and in 1999 “<a href="/facts/Unbalanced_Oil_and_Vinegar/EMz6456I">Unbalanced Oil and Vinegar</a>”, in cooperation with Aviad Kipnis and Louis Goubin (Kipnis, Patarin & Goubin 1999).
</p>
<h2 id="construction">Construction</h2>
<p>Multivariate Quadratics involves a public and a private key. The private key consists of two affine transformations, S and T, and an easy to invert quadratic map 
  
    
      
        
          P
          ′
        
        :
        
          F
          
            m
          
        
        →
        
          F
          
            n
          
        
      
    
    {\displaystyle P'\colon F^{m}\rightarrow F^{n}}
  
. We denote the 
  
    
      
        n
        ×
        n
      
    
    {\displaystyle n\times n}
  
 matrix of the <a href="/facts/Affine_transformation/BD7yDr10">affine</a> <a href="/facts/Endomorphism/s7NNlSea">endomorphisms</a>

S
        :
        
          F
          
            n
          
        
        →
        
          F
          
            n
          
        
      
    
    {\displaystyle S\colon F^{n}\rightarrow F^{n}}
  
 by 
  
    
      
        
          M
          
            S
          
        
      
    
    {\displaystyle M_{S}}
  
 and the shift vector by 
  
    
      
        
          v
          
            S
          
        
        ∈
        
          F
          
            n
          
        
      
    
    {\displaystyle v_{S}\in F^{n}}
  
 and similarly for 
  
    
      
        T
        :
        
          F
          
            m
          
        
        →
        
          F
          
            m
          
        
      
    
    {\displaystyle T\colon F^{m}\rightarrow F^{m}}
  
. In other words,
</p>
<ul><li>
  
    
      
        S
        (
        x
        )
        =
        
          M
          
            S
          
        
        x
        +
        
          v
          
            S
          
        
      
    
    {\displaystyle S(x)=M_{S}x+v_{S}}
  
 and</li>
<li>
  
    
      
        T
        (
        y
        )
        =
        
          M
          
            T
          
        
        y
        +
        
          v
          
            T
          
        
      
    
    {\displaystyle T(y)=M_{T}y+v_{T}}
  
.</li></ul>
<p>The triple 
  
    
      
        (
        
          S
          
            −
            1
          
        
        ,
        
          
            
              P
              ′
            
          
          
            −
            1
          
        
        ,
        
          T
          
            −
            1
          
        
        )
      
    
    {\displaystyle (S^{-1},{P'}^{-1},T^{-1})}
  
 is the private key, also known as the trapdoor. The public key is the composition 
  
    
      
        P
        =
        S
        ∘
        
          P
          ′
        
        ∘
        T
      
    
    {\displaystyle P=S\circ P'\circ T}
  
 which is by assumption hard to invert without the knowledge of the trapdoor.
</p>
<h2 id="signature">Signature</h2>
<p>Signatures are generated using the private key and are verified using the public key as follows. The message is <a href="/facts/Hash_function/rk6MlCt3">hashed</a> to a vector in 
  
    
      
        y
        ∈
        
          F
          
            n
          
        
      
    
    {\displaystyle y\in F^{n}}
  
 via a known hash function. The signature is 
</p>

x
        =
        
          P
          
            −
            1
          
        
        (
        y
        )
        =
        
          T
          
            −
            1
          
        
        
          (
          
            
              
                
                  P
                  ′
                
              
              
                −
                1
              
            
            
              (
              
                
                  S
                  
                    −
                    1
                  
                
                (
                y
                )
              
              )
            
          
          )
        
      
    
    {\displaystyle x=P^{-1}(y)=T^{-1}\left({P'}^{-1}\left(S^{-1}(y)\right)\right)}
  
.
<p>The receiver of the signed document must have the public key P in possession. He computes the hash 
  
    
      
        y
      
    
    {\displaystyle y}
  
 and checks that the signature 
  
    
      
        x
      
    
    {\displaystyle x}
  
 fulfils 
  
    
      
        P
        (
        x
        )
        =
        y
      
    
    {\displaystyle P(x)=y}
  
.
</p>
<h2 id="applications">Applications</h2>

<ul><li><a href="/facts/Unbalanced_Oil_and_Vinegar/EMz6456I">Unbalanced Oil and Vinegar</a></li>
<li><a href="/facts/Hidden_Field_Equations/NyUA3uca">Hidden Field Equations</a></li>
<li>SFLASH by <a href="/facts/NESSIE/IXgAcAhx">NESSIE</a></li>
<li>Rainbow</li>
<li>TTS</li>
<li>QUARTZ</li>
<li><a href="/facts/QUAD_(cipher)/YHys73cY">QUAD (cipher)</a></li>
<li>Four multivariate cryptography signature schemes (GeMMS, LUOV, Rainbow and MQDSS) have made their way into the 2nd round of the NIST post-quantum competition: see slide 12 of the report.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a></li></ul>

<ul><li>[BFP13] L. Bettale,  <a href="/facts/Jean-Charles_Faug%25C3%25A8re/7C3AuKAS">Jean-Charles Faugère</a>, and  L. Perret, Cryptanalysis of HFE, Multi-HFE and Variants for Odd and Even Characteristic. DCC'13</li>
<li>[FJ03] <a href="/facts/Jean-Charles_Faug%25C3%25A8re/7C3AuKAS">Jean-Charles Faugère</a> and  A. Joux, Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases. CRYPTO'03</li>
<li>[GJS06] L. Granboulan, Antoine Joux, J. Stern: Inverting HFE Is Quasipolynomial. CRYPTO'06.</li>
<li>Kipnis, Aviad; Shamir, Adi (1999). "Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization". <i>Advances in Cryptology – CRYPTO' 99</i>. Berlin, Heidelberg: Springer. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-48405-1_2">10.1007/3-540-48405-1_2</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-66347-8. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0302-9743">0302-9743</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1729291">1729291</a>.</li>
<li>Kipnis, Aviad; Patarin, Jacques; Goubin, Louis (1999). <a href="https://link.springer.com/content/pdf/10.1007/3-540-48910-X_15.pdf">"Unbalanced Oil and Vinegar Signature Schemes"</a> (PDF). In Jacques Stern (ed.). <i>Advances in Cryptology – CRYPTO' 99</i>. Eurocrypt'99. Springer. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-48910-x_15">10.1007/3-540-48910-x_15</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-540-65889-0. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0302-9743">0302-9743</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1717470">1717470</a>.</li>
<li>Matsumoto, Tsutomu; <a href="/facts/Hideki_Imai/1XHvIse3">Imai, Hideki</a> (1988). "Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption". <i>Lecture Notes in Computer Science</i>. Berlin, Heidelberg: Springer. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-45961-8_39">10.1007/3-540-45961-8_39</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-50251-7. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0302-9743">0302-9743</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0994679">0994679</a>.</li>
<li>Patarin, Jacques (1995). "Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt'88". <i>Advances in Cryptology – CRYPT0' 95</i>. Lecture Notes in Computer Science. Vol. 963. Berlin, Heidelberg: Springer. pp. 248–261. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-44750-4_20">10.1007/3-540-44750-4_20</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-60221-7. <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0302-9743">0302-9743</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1445572">1445572</a>.</li>
<li>[P96] Jacques Patarin, Hidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms (extended version); Eurocrypt '96</li>
<li>Christopher Wolf and <a href="/facts/Bart_Preneel/eUzy4y6c">Bart Preneel</a>, Taxonomy of Public Key Schemes based on the problem of Multivariate Quadratic equations; Current Version: 2005-12-15</li>
<li>An Braeken, Christopher Wolf, and <a href="/facts/Bart_Preneel/eUzy4y6c">Bart Preneel</a>, A Study of the Security of Unbalanced Oil and Vinegar Signature Schemes, Current Version: 2005-08-06</li>
<li>Jintai Ding, Research Project: Cryptanalysis on Rainbow and TTS multivariate public key signature scheme</li>
<li>Jacques Patarin, <a href="/facts/Nicolas_Courtois/zAH5KLbf">Nicolas Courtois</a>, Louis Goubin, SFLASH, a fast asymmetric signature scheme for low-cost smartcards. Primitive specification and supporting documentation.</li>
<li>Bo-Yin Yang, Chen-Mou Cheng, Bor-Rong Chen, and Jiun-Ming Chen, Implementing Minimized Multivariate PKC on Low-Resource Embedded Systems, 2006</li>
<li>Bo-Yin Yang, Jiun-Ming Chen, and Yen-Hung Chen, TTS: High-Speed Signatures on a Low-Cost Smart Card, 2004</li>
<li><a href="/facts/Nicolas_Courtois/zAH5KLbf">Nicolas T. Courtois</a>, Short Signatures, Provable Security, Generic Attacks and Computational Security of Multivariate Polynomial Schemes such as HFE, Quartz and Sflash, 2005</li>
<li>Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of Applied Cryptography, 1997</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.s1on1.com/main/index.cgi/000000A/http://www.minrank.org/hfe/">[1]</a> The HFE public key encryption and signature</li>
<li><a href="http://www-polsys.lip6.fr/Links/hfeboost.html">[2]</a> HFEBoost</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Garey, Michael R. (1979). Computers and intractability : a guide to the theory of NP-completeness. Johnson, David S., 1945-. San Francisco: W.H. Freeman. ISBN 0-7167-1044-7. OCLC 4195125. <a href="0-7167-1044-7" target="_blank">0-7167-1044-7</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Moody, Dustin (22 August 2019). "The 2nd Round of the NIST PQC Standardization Process". NIST. Retrieved 11 October 2020. <a href="https://csrc.nist.gov/Presentations/2019/the-2nd-round-of-the-nist-pqc-standardization-proc" target="_blank">https://csrc.nist.gov/Presentations/2019/the-2nd-round-of-the-nist-pqc-standardization-proc</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Multivariate cryptography open-in-new

Multivariate cryptography