×

Nonlinear piece in hand perturbation vector method for enhancing security of multivariate public key cryptosystems. (English) Zbl 1177.94147

Buchmann, Johannes (ed.) et al., Post-quantum cryptography. Second international workshop, PQCrypto 2008, Cincinnati, OH, USA, October 17–19, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-88402-6/pbk). Lecture Notes in Computer Science 5299, 148-164 (2008).
Summary: The piece in hand (PH) is a general scheme which is applicable to any reasonable type of multivariate public key cryptosystems for the purpose of enhancing their security. In this paper, we propose a new class PH method called NLPHPV (NonLinear Piece in Hand Perturbation Vector) method. Although our NLPHPV uses similar perturbation vectors as are used for the previously known internal perturbation method, this new method can avoid redundant repetitions in decryption process. With properly chosen parameter sizes, NLPHPV achieves an observable gain in security from the original multivariate public key cryptosystem. We demonstrate these by both theoretical analyses and computer simulations against major known attacks and provides the concrete sizes of security parameters, with which we even expect the grater security against potential quantum attacks.
For the entire collection see [Zbl 1147.94002].

MSC:

94A60 Cryptography
81P94 Quantum cryptography (quantum-theoretic aspects)

Software:

FGb
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Coppersmith, D., Stern, J., Vaudenay, S.: Attacks on the birational permutation signature schemes. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 435–443. Springer, Heidelberg (1994) · Zbl 0877.94030 · doi:10.1007/3-540-48329-2_37
[2] 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) · Zbl 1082.94514 · doi:10.1007/3-540-45539-6_27
[3] Ding, J.: A new variant of the Matsumoto-Imai cryptosystem through perturbation. In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol. 2947, pp. 305–318. Springer, Heidelberg (2004) · Zbl 1198.94091 · doi:10.1007/978-3-540-24632-9_22
[4] 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) · Zbl 1126.68393 · doi:10.1007/11496137_12
[5] Ding, J., Gower, J.E., Schmidt, D., Wolf, C., Yin, Z.: Complexity estimates for the F4 attack on the perturbed Matsumoto-Imai cryptosystem. In: Smart, N. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 262–277. Springer, Heidelberg (2005) · Zbl 1122.94034 · doi:10.1007/11586821_18
[6] Ding, J., Gower, J.E.: Inoculating multivariate schemes against differential attacks. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 290–301. Springer, Heidelberg (2006) · Zbl 1151.94505 · doi:10.1007/11745853_19
[7] Ding, J., Wolf, C., Yang, B.Y.: -Invertible Cycles for \(\mathcal{M}\) ultivariate \(\mathcal{Q}\) uadratic ( \(\mathcal{MQ}\) ) public key cryptography. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 266–281. Springer, Heidelberg (2007) · Zbl 1161.94006 · doi:10.1007/978-3-540-71677-8_18
[8] Faugère, J.C., Joux, A.: Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 44–60. Springer, Heidelberg (2003) · Zbl 1122.94371 · doi:10.1007/978-3-540-45146-4_3
[9] Fouque, P.A., Granboulan, L., Stern, J.: Differential cryptanalysis for multivariate schemes. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 341–353. Springer, Heidelberg (2005) · Zbl 1137.94344 · doi:10.1007/11426639_20
[10] Goubin, L., Courtois, N.: Cryptanalysis of the TTM cryptosystem. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 44–57. Springer, Heidelberg (2000) · Zbl 0980.94017 · doi:10.1007/3-540-44448-3_4
[11] Ito, D., Fukushima, Y., Kaneko, T.: On the security of piece in hand concept based on sequential solution method. Technical Report of IEICE, ISEC2006-30, SITE2006-27 (2006-7) (July 2006) (in Japanese)
[12] Kasahara, M., Sakai, R.: A new principle of public key cryptosystem and its realization. Technical Report of IEICE, ISEC2000-92 (2000-11) (November 2000) (in Japanese)
[13] Kasahara, M., Sakai, R.: A construction of public key cryptosystem for realizing ciphertext of size 100 bit and digital signature scheme. IEICE Transactions on Fundamentals E87-A(1), 102–109 (2004)
[14] Kasahara, M., Sakai, R.: A construction of public-key cryptosystem based on singular simultaneous equations. IEICE Transactions on Fundamentals E88-A(1), 74–80 (2005) · doi:10.1093/ietfec/E88-A.1.74
[15] 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) · Zbl 0933.94031 · doi:10.1007/3-540-48910-X_15
[16] 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) · Zbl 0940.94012 · doi:10.1007/3-540-48405-1_2
[17] Matsumoto, T., Imai, H., Harashima, H., Miyakawa, H.: A class of asymmetric cryptosystems using obscure representations of enciphering functions. In: 1983 National Convention Record on Information Systems, IECE Japan, pp. S8–5 (1983) (in Japanese)
[18] Matsumoto, T., Imai, H.: Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 419–453. Springer, Heidelberg (1988) · Zbl 0655.94013 · doi:10.1007/3-540-45961-8_39
[19] Moh, T.T.: A public key system with signature and master key functions. Communications in Algebra 27, 2207–2222 (1999) · Zbl 0933.94022 · doi:10.1080/00927879908826559
[20] Patarin, J.: Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt 1988. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 248–261. Springer, Heidelberg (1995) · Zbl 0868.94025 · doi:10.1007/3-540-44750-4_20
[21] Patarin, J.: Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996) · Zbl 1301.94125 · doi:10.1007/3-540-68339-9_4
[22] 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–49. Springer, Heidelberg (1998) · doi:10.1007/3-540-49649-1_4
[23] Shamir, A.: Efficient signature schemes based on birational permutations. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 1–12. Springer, Heidelberg (1994) · Zbl 0877.94041 · doi:10.1007/3-540-48329-2_1
[24] Tadaki, K., Tsujii, S.: On the enhancement of security by piece in hand matrix method for multivariate public key cryptosystems. In: Proc. SCIS 2007, vol. 2C1-3 (2007)
[25] Tsujii, S., Kurosawa, K., Itoh, T., Fujioka, A., Matsumoto, T.: A public-key cryptosystem based on the difficulty of solving a system of non-linear equations. IECE Transactions (D) J69-D(12), 1963–1970 (1986) (in Japanese)
[26] Tsujii, S., Fujioka, A., Hirayama, Y.: Generalization of the public-key cryptosystem based on the difficulty of solving a system of non-linear equations. IEICE Transactions (A) J72-A(2), 390–397 (1989) (in Japanese) (An English translation of [26] is included in [29] as an appendix)
[27] Tsujii, S.: A new structure of primitive public key cryptosystem based on soldiers in hand matrix. Technical Report TRISE 02-03, Chuo University (July 2003)
[28] Tsujii, S., Fujita, R., Tadaki, K.: Proposal of MOCHIGOMA (piece in hand) concept for multivariate type public key cryptosystem. Technical Report of IEICE, ISEC2004-74 (2004-09) (September 2004)
[29] Tsujii, S., Tadaki, K., Fujita, R.: Piece in hand concept for enhancing the security of multivariate type public key cryptosystems: public key without containing all the information of secret key. Cryptology ePrint Archive, Report 2004/366 (December 2004), http://eprint.iacr.org/2004/366
[30] Tsujii, S., Tadaki, K., Fujita, R.: Piece in hand concept for enhancing the security of multivariate type public key cryptosystems: public key without containing all the information of secret key. In: Proc. SCIS 2005, vol. 2E1-3, pp. 487–492 (2005), http://lab.iisec.ac.jp/ tsujii/SCIS2005-2E1-3.pdf
[31] Tsujii, S., Tadaki, K., Fujita, R.: Proposal for piece in hand (soldiers in hand) matrix – general concept for enhancing security of multivariate public key cryptosystems – Ver.2. In: Proc. SCIS 2006, vol. 2A4-1 (2006) (in Japanese), http://lab.iisec.ac.jp/ tsujii/SCIS2006-2A4-1.pdf · Zbl 1177.94147
[32] Tsujii, S., Tadaki, K., Fujita, R.: Proposal for piece in hand matrix ver.2: general concept for enhancing security of multivariate public key cryptosystems. In: Workshop Record of the International Workshop on Post-Quantum Cryptography (PQCrypto 2006), pp. 103–117 (2006), http://postquantum.cr.yp.to/pqcrypto2006record.pdf
[33] Tsujii, S., Tadaki, K., Fujita, R.: Proposal for piece in hand matrix: general concept for enhancing security of multivariate public key cryptosystems. IEICE Transactions on Fundamentals E90-A(5), 992–999 (2007), http://lab.iisec.ac.jp/ tsujii/TTF07.pdf
[34] Tsujii, S., Tadaki, K., Fujita, R.: Nonlinear piece in hand matrix method for enhancing security of multivariate public key cryptosystems. In: Proceedings of the First International Conference on Symbolic Computation and Cryptography (SCC 2008), pp. 124–144 (2008) · Zbl 1177.94147
[35] Wang, L.C., Hu, Y.H., Lai, F., Chou, C.Y., Yang, B.Y.: Tractable rational map signature. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 244–257. Springer, Heidelberg (2005) · Zbl 1081.94555 · doi:10.1007/978-3-540-30580-4_17
[36] Wang, L.C., Yang, B.Y., Hu, Y.H., Lai, F.: A medium-field multivariate public-key encryption scheme. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol. 3860, pp. 132–149. Springer, Heidelberg (2006) · Zbl 1125.94028 · doi:10.1007/11605805_9
[37] Wolf, C., Braeken, A., Preneel, B.: Efficient cryptanalysis of RSE(2)PKC and RSSE(2)PKC. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 294–309. Springer, Heidelberg (2005) · Zbl 1116.94336 · doi:10.1007/978-3-540-30598-9_21
[38] Wolf, C., Preneel, B.: Taxonomy of Public Key Schemes based on the problem of Multivariate Quadratic equations. Cryptology ePrint Archive, Report 2005/077 (December 2005), http://eprint.iacr.org/2005/077
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.