Top

Published in:

2021 | OriginalPaper | Chapter

Multivariate Public Key Cryptosystem from Sidon Spaces

Authors : Netanel Raviv, Ben Langton, Itzhak Tamo

Published in: Public-Key Cryptography – PKC 2021

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A Sidon space is a subspace of an extension field over a base field in which the product of any two elements can be factored uniquely, up to constants. This paper proposes a new a public-key cryptosystem of the multivariate type which is based on Sidon spaces, and has the potential to remain secure even if quantum supremacy is attained. This system, whose security relies on the hardness of the well-known MinRank problem, is shown to be resilient to several straightforward algebraic attacks. In particular, it is proved that the two popular attacks on the MinRank problem, the kernel attack and the minor attack, succeed only with exponentially small probability. The system is implemented in software, and its hardness is demonstrated experimentally.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Shorter Lattice-Based Zero-Knowledge Proofs via One-Time Commitments

next chapter Banquet: Short and Fast Signatures from AES

Available only for authorised users

Since \(|\overline{\mathcal {W}}_{q-1}|=q^k-\frac{q^k-1}{q-1}-1\), a crude lower bound for the number of such elements \(\gamma \) is \(\approx \frac{q-2}{q-1}\cdot q^{k}\).

That is, \(n=2k\) matrices, each containing \(\left( {\begin{array}{c}k+1\\ 2\end{array}}\right) \) elements.

Or more precisely, the square MinRank search problem.

More precisely, \(\mathbf {C}\) contains \(c_d^{(i,j)}\) in entry (d, (i, j)), where the \(n^2\) columns are indexed by all pairs (i, j), \(i,j\in [n]\).

Raviv, N., Langton B., Tamo I.,: The Sidon Cryptosystem (2021). https://github.com/b-langton/Sidon-Cryptosystem

Bachoc, C., Serra, O., Zémor, G.: An analogue of Vosper’s theorem for extension fields. In: arXiv:1501.00602 [math.NT] (2015)

Bardet, M., et al.: Improvements of algebraic attacks for solving the rank decoding and MinRank problems. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12491, pp. 507–536. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64837-4_17CrossRef

Barreto, P., Voloch, J.F.: Efficient computation of roots in finite fields. Des. Codes Crypt. 39(2), 275–280 (2006)MathSciNetCrossRef

Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_27CrossRef

Cheng, C.-M., Hashimoto, Y., Miura, H., Takagi, T.: A polynomial-time algorithm for solving a class of underdetermined multivariate quadratic equations over fields of odd characteristics. In: Mosca, M. (ed.) PQCrypto 2014. LNCS, vol. 8772, pp. 40–58. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11659-4_3CrossRef

Ding, J., Kleinjung, T.: Degree of regularity for HFE-. IACR Cryptology ePrint Archive, p. 570 (2011)

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_12CrossRef

Faugère, J.-C.: FGb: a library for computing gröbner bases. In: Fukuda, K., Hoeven, J., Joswig, M., Takayama, N. (eds.) ICMS 2010. LNCS, vol. 6327, pp. 84–87. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15582-6_17CrossRef

10.

Faugère, J.-C., Levy-dit-Vehel, F., Perret, L.: Cryptanalysis of MinRank. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 280–296. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_16CrossRef

11.

Faugère, J.C., El-Din, M.S., Spaenlehauer, P.J.: Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree \((1, 1)\): algorithms and complexity. J. Symbolic Comput. 46(4), 406–437 (2011)MathSciNetCrossRef

12.

Faugère, J.C., El-Din, M.S., Spaenlehauer, P.J.: Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation, pp. 257–264 (2010)

13.

Gu, C.: Cryptanalysis of Simple Matrix Scheme for Encryption. IACR Cryptology ePrint Archive, p. 1075 (2016)

14.

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_4CrossRef

15.

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_2CrossRef

16.

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_15CrossRef

17.

Makarim, R.H., tevens M.: M4GB: an efficient Gröbner-basis algorithm. In: Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, pp. 293–300 (2017)

18.

Miura, H., Hashimoto, Y., Takagi, T.: Extended algorithm for solving underdefined multivariate quadratic equations. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 118–135. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38616-9_8CrossRef

19.

Moh, T.T.: A fast public key system with signature and master key functions. In: Proceedings of CrypTEC 1999, International Workshop on Cryptographic Techniques and E-Commerce, pp. 63–69. Hong-Kong City University Press (1999)

20.

Niu, Y., Qin, Y., Yansheng, W.: Several kinds of large cyclic subspace codes via Sidon spaces. Discrete Math. 343(5), 111788 (2020)

21.

O’Bryant, K.: A complete annotated bibliography of work related to Sidon sequences. In: arXiv preprint math/0407117 (2004)

22.

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_4CrossRef

23.

Perlner, R., Smith-Tone, D.: Security analysis and key modification for ZHFE. In: Takagi, T. (ed.) PQCrypto 2016. LNCS, vol. 9606, pp. 197–212. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29360-8_13CrossRef

24.

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_14CrossRef

25.

Porras, J., Baena, J., Ding, J.: ZHFE, a new multivariate public key encryption scheme. In: Mosca, M. (ed.) PQCrypto 2014. LNCS, vol. 8772, pp. 229–245. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11659-4_14CrossRef

26.

Roth, R.M., Raviv, N., Tamo, I.: Construction of Sidon spaces with applications to coding. IEEE Trans. Inf. Th. 64(6), 4412–4422 (2017)MathSciNetCrossRef

27.

Schulman, L.J.: Cryptography from tensor problems. In: IACR Cryptol. ePrint Arch. (2012)

28.

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_16CrossRef

29.

Thomae, E., Wolf, C.: Solving underdetermined systems of multivariate quadratic equations revisited. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 156–171. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30057-8_10CrossRef

30.

Vates, J., Smith-Tone, D.: Key recovery attack for all parameters of HFE. In: Lange, T., Takagi, T. (eds.) PQCrypto 2017. LNCS, vol. 10346, pp. 272–288. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59879-6_16CrossRef

31.

Verbel, J., Baena, J., Cabarcas, D., Perlner, R., Smith-Tone, D.: On the complexity of “Superdetermined” minrank instances. In: Ding, J., Steinwandt, R. (eds.) PQCrypto 2019. LNCS, vol. 11505, pp. 167–186. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25510-7_10CrossRef

32.

Wageringel M.: A Sage interface for FGb (2020). https://github.com/mwageringel/fgb_sage

Title: Multivariate Public Key Cryptosystem from Sidon Spaces
Authors: Netanel Raviv
Ben Langton
Itzhak Tamo
Publisher: Springer International Publishing
Book: Public-Key Cryptography – PKC 2021
Print ISBN: 978-3-030-75244-6

Electronic ISBN: 978-3-030-75245-3

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-75245-3_10

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner