[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

HFERP - A New Multivariate Encryption Scheme

  • Conference paper
  • First Online:
Post-Quantum Cryptography (PQCrypto 2018)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 10786))

Included in the following conference series:

Abstract

In 2016, Yasuda et al. presented a new multivariate encryption technique based on the Square and Rainbow primitives and utilizing the plus modifier that they called SRP. The scheme achieved a smaller blow-up factor between the plaintext space and ciphertext space than most recent multivariate encryption proposals, but proved to be too aggressive and was completely broken by Perlner et al. in 2017. The scheme suffered from the same MinRank weakness that has allowed effective attacks on several notable big field multivariate schemes: HFE, multi-HFE, HFE-, for example.

We propose a related new encryption scheme retaining the desirable traits of SRP and patching its weaknesses. We call the scheme HFERP because it utilizes a similar construction as SRP with an HFE primitive replacing the Square polynomial. The effect of this substitution is to increase the Q-rank of the pubic key to such a degree that the MinRank attack is impossible. HFERP still retains the relatively small blow-up factor between the plaintext space and ciphertext space, and is thus a candidate for secure multivariate encryption without an essential doubling in size between plaintext and ciphertext.

The rights of this work are transferred to the extent transferable according to title 17 \(\S \) 105 U.S.C.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Certain commercial equipment, instruments, or materials are identified in this paper in order to specify the experimental procedure adequately. Such identification is not intended to imply recommendation or endorsement by the National Institute of Standards and Technology, nor is it intended to imply that the materials or equipment identified are necessarily the best available for the purpose.

References

  1. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Sci. Stat. Comput. 26, 1484 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  2. Mosca, M.: Cybersecurity in a quantum world: will we be ready? In: Workshop on Cybersecurity in a Post-Quantum World, Invited Presentation (2015). https://csrc.nist.gov/csrc/media/events/workshop-on-cybersecurity-in-a-post-quantum-world/documents/presentations/session8-mosca-michele.pdf

  3. Yasuda, T., Sakurai, K.: A multivariate encryption scheme with rainbow. In: Qing, S., Okamoto, E., Kim, K., Liu, D. (eds.) ICICS 2015. LNCS, vol. 9543, pp. 236–251. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29814-6_19

    Chapter  Google Scholar 

  4. Kipnis, A., Patarin, J., Goubin, L.: Unbalanced oil and vinegar signature schemes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 206–222. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_15

    Chapter  Google Scholar 

  5. Ding, J., Schmidt, D.: Rainbow, a new multivariable polynomial signature scheme. In: Ioannidis, J., Keromytis, A., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 164–175. Springer, Heidelberg (2005). https://doi.org/10.1007/11496137_12

    Chapter  Google Scholar 

  6. Petzoldt, A., Chen, M.-S., Yang, B.-Y., Tao, C., Ding, J.: Design principles for HFEv- based multivariate signature schemes. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 311–334. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_14

    Chapter  Google Scholar 

  7. Patarin, J.: Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68339-9_4

    Chapter  Google Scholar 

  8. Tao, C., Diene, A., Tang, S., Ding, J.: Simple matrix scheme for encryption. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 231–242. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38616-9_16

    Chapter  Google Scholar 

  9. Ding, J., Petzoldt, A., Wang, L.: The cubic simple matrix encryption scheme. [32], pp. 76–87 (2014)

    Google Scholar 

  10. Porras, J., Baena, J., Ding, J.: ZHFE, A new multivariate public key encryption scheme. [32], pp. 229–245 (2014)

    Google Scholar 

  11. Moody, D., Perlner, R.A., Smith-Tone, D.: An asymptotically optimal structural attack on the ABC multivariate encryption scheme. [32], pp. 180–196 (2014)

    Google Scholar 

  12. Moody, D., Perlner, R., Smith-Tone, D.: Key recovery attack on the cubic ABC simple matrix multivariate encryption scheme. In: Avanzi, R., Heys, H. (eds.) SAC 2016. LNCS, vol. 10532, pp. 543–558. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69453-5_29

    Chapter  Google Scholar 

  13. Moody, D., Perlner, R.A., Smith-Tone, D.: Improved attacks for characteristic-2 parameters of the cubic ABC simple matrix encryption scheme. [31], pp. 255–271 (2017)

    Google Scholar 

  14. Cabarcas, D., Smith-Tone, D., Verbel, J.A.: Key recovery attack for ZHFE. [31], pp. 289–308 (2017)

    Google Scholar 

  15. Vates, J., Smith-Tone, D.: Key recovery attack for all parameters of HFE-. [31], pp. 272–288 (2017)

    Google Scholar 

  16. Perlner, R., Petzoldt, A., Smith-Tone, D.: Total break of the SRP encryption scheme. In: Adams, C., Camenisch, J. (eds.) SAC 2017. LNCS, vol. 10719, pp. 355–373. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-72565-9_18

    Chapter  Google Scholar 

  17. Matsumoto, T., Imai, H.: Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In: Barstow, D., Brauer, W., Brinch Hansen, P., Gries, D., Luckham, D., Moler, C., Pnueli, A., Seegmüller, G., Stoer, J., Wirth, N., Günther, C.G. (eds.) EUROCRYPT 1988. LNCS, vol. 330, pp. 419–453. Springer, Heidelberg (1988). https://doi.org/10.1007/3-540-45961-8_39

    Chapter  Google Scholar 

  18. Berlekamp, E.R.: Factoring polynomials over large finite fields. Math. Comput. 24, 713–735 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  19. Clough, C., Baena, J., Ding, J., Yang, B.-Y., Chen, M.: Square, a new multivariate encryption scheme. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 252–264. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00862-7_17

    Chapter  Google Scholar 

  20. Patarin, J.: The oil and vinegar algorithm for signatures. Presented at the Dagsthul Workshop on Cryptography (1997)

    Google Scholar 

  21. Patarin, J., Goubin, L., Courtois, N.: \(C_{-+}^{*}\), and HM: variations around two schemes of T. Matsumoto and H. Imai. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 35–50. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-49649-1_4

    Chapter  Google Scholar 

  22. Kipnis, A., Shamir, A.: Cryptanalysis of the oil and vinegar signature scheme. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 257–266. Springer, Heidelberg (1998). https://doi.org/10.1007/978-3-319-72565-9_18

    Chapter  Google Scholar 

  23. Kipnis, A., Shamir, A.: Cryptanalysis of the HFE public key cryptosystem by relinearization. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 19–30. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_2

    Chapter  Google Scholar 

  24. Faugère, J., Din, M.S.E., Spaenlehauer, P.: Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology. In: Koepf, W. (ed.) Proceedings of International Symposium on Symbolic and Algebraic Computation, ISSAC 2010, Munich, Germany, 25–28 July 2010, pp. 257–264. ACM (2010)

    Google Scholar 

  25. Bettale, L., Faugère, J., Perret, L.: Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic. Des. Codes Cryptogr. 69, 1–52 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  26. Ding, J., Hodges, T.J.: Inverting HFE systems is quasi-polynomial for all fields. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 724–742. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_41

    Chapter  Google Scholar 

  27. Goubin, L., Courtois, N.T.: Cryptanalysis of the TTM cryptosystem. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 44–57. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44448-3_4

    Chapter  Google Scholar 

  28. Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I: the user language. J. Symb. Comput. 24, 235–265 (1997). Computational algebra and number theory (London, 1993)

    Article  MathSciNet  MATH  Google Scholar 

  29. Yang, B.-Y., Chen, J.-M.: Theoretical analysis of XL over small fields. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds.) ACISP 2004. LNCS, vol. 3108, pp. 277–288. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27800-9_24

    Chapter  Google Scholar 

  30. Bardet, M., Faugre, J., Salvy, B., Yang, B.: Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems. In: MEGA 2005 Eighth International Symposium On Effective Methods in Algebraic Geometry (2005)

    Google Scholar 

  31. Lange, T., Takagi, T. (eds.): PQCrypto 2017. LNCS, vol. 10346. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59879-6

    Google Scholar 

  32. Mosca, M. (ed.): PQCrypto 2014. LNCS, vol. 8772. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11659-4

    MATH  Google Scholar 

Download references

Acknowledgments

The first and fourth authors were supported by JST CREST (Grant Number JPMJCR14D6).

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Louisville, Louisville, KY, USA

    Daniel Smith-Tone & Jeremy Vates

  2. National Institute of Standards and Technology, Gaithersburg, MD, USA

    Ray Perlner & Daniel Smith-Tone

  3. Institute of Mathematics for Industry, Kyushu University, Fukuoka, Japan

    Yasuhiko Ikematsu & Tsuyoshi Takagi

Authors
  1. Yasuhiko Ikematsu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ray Perlner
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Daniel Smith-Tone
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Tsuyoshi Takagi
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Jeremy Vates
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jeremy Vates .

Editor information

Editors and Affiliations

  1. Technische Universiteit Eindhoven, Eindhoven, The Netherlands

    Tanja Lange

  2. Florida Atlantic University, Boca Raton, Florida, USA

    Rainer Steinwandt

A Toy Example

A Toy Example

The purpose of the following toy example is to help the reader understand the process of generating a public key for an instance of HFERP as well as an example of encryption and decryption. The parameters used are by no means secure and are soley for instructional purposes.

Parameters of this toy example are as follows: \(q=7,~d=o=r=2,~s=1, \text {and}~ l=0\). Then, construct \(\mathbb {E}\) a degree 2 extension field over \(\mathbb {F}_7\). The chosen HFE core map is \(f=\xi ^{12}X^{14}+\xi ^{6}X^8+\xi ^{29}X^2\) where \(\xi \in \mathbb {E}\). Let \(\mathcal {T}\) and \(\mathcal {U}\) be the following affine maps:

$$\begin{aligned}\begin{gathered} \mathcal {T}=\left[ \begin{matrix} 2&{}1&{}2&{}4&{}5&{}0&{}3\\ 1&{}1&{}3&{}3&{}4&{}4&{}4\\ 4&{}2&{}1&{}3&{}1&{}0&{}6\\ 0&{}1&{}0&{}1&{}5&{}5&{}5&{}\\ 5&{}5&{}3&{}6&{}4&{}2&{}4\\ 2&{}5&{}1&{}6&{}5&{}6&{}0\\ 1&{}1&{}2&{}2&{}6&{}4&{}3\\ \end{matrix}\right] ,\mathcal {U}=\left[ \begin{matrix} 4&{}6&{}6&{}4\\ 3&{}2&{}0&{}2\\ 1&{}1&{}6&{}5\\ 3&{}6&{}6&{}6\\ \end{matrix}\right] \end{gathered}\end{aligned}$$

With the parameters described above, \(\mathcal {F}\) can be represented as the following matrices over \(\mathbb {F}_7\)

$$\begin{aligned}\begin{gathered} F_1=\left[ \begin{matrix} 0&{}1&{}0&{}0\\ 4&{}0&{}0&{}0\\ 0&{}0&{}0&{}0\\ 0&{}0&{}0&{}0\\ \end{matrix}\right] ,F_2=\left[ \begin{matrix} 0&{}3&{}0&{}0\\ 1&{}6&{}0&{}0\\ 0&{}0&{}0&{}0\\ 0&{}0&{}0&{}0\\ \end{matrix}\right] ,F_3=\left[ \begin{matrix} 3&{}1&{}6&{}1\\ 3&{}1&{}4&{}5\\ 3&{}4&{}0&{}0\\ 3&{}2&{}0&{}0\\ \end{matrix}\right] ,\\ F_4=\left[ \begin{matrix} 5&{}1&{}0&{}3\\ 0&{}5&{}0&{}3\\ 0&{}4&{}0&{}0\\ 6&{}1&{}0&{}0\\ \end{matrix}\right] ,F_5=\left[ \begin{matrix} 6&{}0&{}3&{}4\\ 6&{}2&{}4&{}2\\ 6&{}3&{}0&{}0\\ 0&{}3&{}0&{}0\\ \end{matrix}\right] ,F_6=\left[ \begin{matrix} 4&{}4&{}1&{}1\\ 3&{}0&{}0&{}3\\ 3&{}6&{}0&{}0\\ 1&{}2&{}0&{}0\\ \end{matrix}\right] ,F_7=\left[ \begin{matrix} 6&{}3&{}2&{}3\\ 4&{}4&{}0&{}6\\ 2&{}3&{}1&{}3\\ 6&{}4&{}0&{}6\\ \end{matrix}\right] \end{gathered}\end{aligned}$$

\(P_1\) and \(P_2\) represent the HFE component, \(P_3 \rightarrow P_6\) represent the rainbow component, and \(P_7\) represents the plus component. With the public key generated by \(\mathcal {P}=\mathcal {T}\circ \mathcal {F}\circ \mathcal {U}\), its matrix form over \(\mathbb {F}_7\) is:

$$\begin{aligned}\begin{gathered} P_1=\left[ \begin{matrix} 1&{}1&{}2&{}5\\ 1&{}2&{}3&{}2\\ 3&{}2&{}4&{}4\\ 3&{}3&{}0&{}3\\ \end{matrix}\right] ,P_2=\left[ \begin{matrix} 0&{}2&{}0&{}6\\ 4&{}5&{}2&{}0\\ 6&{}3&{}3&{}4\\ 3&{}1&{}2&{}2\\ \end{matrix}\right] ,P_3=\left[ \begin{matrix} 2&{}3&{}1&{}4\\ 4&{}5&{}4&{}5\\ 3&{}5&{}5&{}1\\ 5&{}1&{}0&{}6\\ \end{matrix}\right] ,\\ P_4=\left[ \begin{matrix} 0&{}6&{}0&{}2\\ 1&{}3&{}0&{}2\\ 5&{}1&{}5&{}1\\ 5&{}3&{}0&{}5\\ \end{matrix}\right] ,P_5=\left[ \begin{matrix} 4&{}3&{}2&{}3\\ 6&{}5&{}2&{}4\\ 4&{}3&{}1&{}5\\ 5&{}2&{}4&{}5\\ \end{matrix}\right] ,P_6=\left[ \begin{matrix} 1&{}4&{}2&{}2\\ 3&{}3&{}6&{}2\\ 5&{}4&{}0&{}0\\ 3&{}5&{}5&{}4\\ \end{matrix}\right] ,P_7=\left[ \begin{matrix} 1&{}3&{}6&{}0\\ 0&{}3&{}4&{}0\\ 1&{}2&{}4&{}2\\ 2&{}1&{}6&{}4\\ \end{matrix}\right] \end{gathered}\end{aligned}$$

Given the following plaintext, (2, 6, 1, 5), the resulting ciphertext is (0, 0, 1, 3, 0, 4, 0).

Decryption: Given a ciphertext (0, 0, 1, 3, 0, 4, 0), the following process is how you would obtain its corresponding plaintext.

Part of the secret key:

$$\begin{aligned}\begin{gathered} \mathcal {T}^{-1}=\left[ \begin{matrix} 1&{}6&{}4&{}2&{}2&{}2&{}5\\ 5&{}4&{}4&{}6&{}0&{}5&{}2\\ 5&{}3&{}5&{}2&{}3&{}2&{}4\\ 5&{}6&{}5&{}5&{}2&{}1&{}1\\ 2&{}5&{}4&{}2&{}1&{}5&{}2\\ 2&{}5&{}6&{}6&{}3&{}5&{}5\\ 1&{}2&{}5&{}4&{}4&{}0&{}5\\ \end{matrix}\right] ,\mathcal {U}^{-1}=\left[ \begin{matrix} 4&{}5&{}2&{}1\\ 3&{}1&{}3&{}1\\ 4&{}1&{}2&{}0\\ 5&{}6&{}1&{}1\\ \end{matrix}\right] \end{gathered}\end{aligned}$$

Feed the ciphertext through \(\mathcal {T}^{-1}\) to get

$$\begin{aligned} (0,6,2,6,0,4,6) \end{aligned}$$
(7)

The first \(d=2\) elements are the corresponding HFE outputs. Take these elements and adjust the HFE core map as follows:

$$ f:=f-0\xi ^{1-1}-6\xi ^{2-1}=\xi ^{12}X^{14}+\xi ^{6}X^8+\xi ^{29}X^2+\xi $$

Perform the Berlekamp algorithm to find the preimage of f. In doing so in this toy example, you get (0, 6). Next, construct the vector:

$$ \overline{u}=\left[ 0,6,u_1,u_2 \right] . $$

Construct equations of the form \(\overline{u}F_1\overline{u}^\top = x_i\) where \(x_i\) refers to the \(i^{th}\) element of (7), for \(i \in \{3,4,5,6\}\). This will result with the following equations:

$$ \left[ \begin{matrix} 6u_1+1\\ 3u_1+3u_2+5\\ 2u_2+2\\ u_1+2u_2\\ \end{matrix}\right] = \left[ \begin{matrix} 2\\ 6\\ 0\\ 4\\ \end{matrix}\right] $$

Solving this system of equations gives us \(u_1=6\) and \(u_2=6\). Thus,

$$ \overline{u}=\left[ 0,6,6,6 \right] . $$

Finally, feed this through \(\mathcal {U}^{-1}\) to get the plaintext, \(\left[ 2,6,1,5 \right] \).

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer International Publishing AG, part of Springer Nature (outside the US)

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Ikematsu, Y., Perlner, R., Smith-Tone, D., Takagi, T., Vates, J. (2018). HFERP - A New Multivariate Encryption Scheme. In: Lange, T., Steinwandt, R. (eds) Post-Quantum Cryptography. PQCrypto 2018. Lecture Notes in Computer Science(), vol 10786. Springer, Cham. https://doi.org/10.1007/978-3-319-79063-3_19

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-79063-3_19

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-79062-6

  • Online ISBN: 978-3-319-79063-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics