© The Institution of Engineering and Technology
It was reported that a multivariate public key cryptosystem (MPKC) could be strengthened if its public key is generated by composition of two original public keys. In fact, two existing keys are used to constitute two quadratic rounds of the new key. But such a two-round scheme, called 2R, was claimed to have been decomposed, and even a further improved 2R, named 2R−, was shown to be similarly vulnerable. The result casts doubts on the principle of using a two-round structure to improve the security. However, this study clearly states that the decomposition attacks depend on the prerequisite that either of the rounds is quadratic. It shows that these attacks, even the conceivable extended ones, do not work in theory or in practice if the first round is of higher degree, although the threat still remains when only the degree of the second round is changed. Therefore adopting a cubic first round becomes a rule in the design of the 2-round schemes. The analysis and experiments in this study also demonstrate that the new schemes with such an indecomposable two-round public key can provide the desired security against many other known and potential attacks on MPKCs and that the key size can be practically controlled.
References
-
-
1)
-
Jakobsen, T.: `Cryptanalysis of block ciphers with probabilistic non-linear relations of low degree', Proc. CRYPTO'98, August 1998, Santa Barbara, CA, USA, p. 212–222, (LNCS, 1462).
-
2)
-
M. Clausen ,
A. Dress ,
J. Grabmeier ,
M. Karpinski
.
On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields.
Theor. Comput. Sci.
,
2 ,
151 -
164
-
3)
-
Patarin, J.: `The oil and vinegar signature scheme', Presented at the Dagstuhl Workshop on Cryptography, September 1997.
-
4)
-
Faugère, J.-C.: `A new efficient algorithm for computing Gröbner bases without reduction to zero (F', Proc. ISSAC'02, July 2002, Lille, France, p. 75–83.
-
5)
-
J. Patarin
.
Hidden fields equations (HFE) and isomorphisms of polynomial (IP): two new families of asymmetric algorithms (extended version).
-
6)
-
Coppersmith, D., Stern, J., Vaudenay, S.: `Attacks on the birational permutation signature schemes', Proc. CRYPTO'93, August 1993, Santa Barbara, CA, USA, p. 435–443, (LNCS, 773).
-
7)
-
Courtois, N.T., Goubin, L., Patarin, J.: `SFLASH, a fast asymmetric signature scheme', IACR Cryptology ePrint Archive: report 2003/211, , available at: http://www.eprint.iacr.org, 2003.
-
8)
-
Dubois, V., Fouque, P.-A., Stern, J.: `Cryptanalysis of SFLASH with slightly modified parameters', Proc. EUROCRYPT'07, May 2007, Barcelona, Spain, p. 264–275, (LNCS, 4515).
-
9)
-
Faugère, J.-C., Joux, A.: `Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases', Proc. CRYPTO'03, August 2003, Santa Barbara, CA, USA, p. 44–60, (LNCS, 2729).
-
10)
-
Faugère, J.-C., Levy-Dit-Vehel, F., Perret, L.: `Cryptanalysis of MinRank', Proc. CRYPTO'08, August 2008, Santa Barbara, CA, USA, p. 280–296, (LNCS, 5157).
-
11)
-
Huang, M.-D., Rao, A.J.: `Interpolation of sparse multivariate polynomials over large finite fields with applications', Proc. Seventh Ann. ACM-SIAM Symp. on Discrete Algorithms, January 1996, Atlanta, Georgia, USA, p. 508–517.
-
12)
-
Moh, T., Chen, J., Yang, B.: `Building instances of TTM immune to the Goubin-Courtois attack and Ding-Schmidt attack', IACR Cryptology ePrint Archive, report 2004/168, 2006, available at: http://www.eprint.iacr.org.
-
13)
-
Wang, L.-C., Yang, B.-Y., Hu, Y.-H., Lai, F.: `A medium field multivariate encryption scheme', Proc. CT-RSA'06, February 2006, San Jose, CA, USA, p. 132–149, (LNCS, 3860).
-
14)
-
Ars, G., Faugère, J.-C., Imai, H., Kawazoe, M., Sugita, M.: `Comparison between XL and Gröbner basis algorithms', Proc. ASIACRYPT'04, December 2004, Jeju Island, Korea, p. 338–353, (LNCS, 3329).
-
15)
-
http://magma.maths.usyd.edu.au/users/allan/gb/, accessed April 2008.
-
16)
-
Faugère, J.-C., Perret, L.: `Cryptanalysis of 2R- schemes', Proc. CRYPTO'06, August 2006, Santa Barbara, CA, USA, p. 357–372, (LNCS, 4117).
-
17)
-
Ding, J., Schmidt, D.: `A defect of the implementation schemes of the TTM cryptosystem', IACR Cryptology ePrint Archive, report 2003/086, 2003, available at: http://www.eprint.iacr.org.
-
18)
-
P.W. Shor
.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.
SIAM J. Comput.
,
5 ,
1484 -
1509
-
19)
-
Fouque, P., Granboulan, L., Stern, J.: `Differential cryptanalysis for multivariate schemes', Proc. EUROCRYPT'05, May 2005, Aarhus, Denmark, p. 341–535, (LNCS, 3494).
-
20)
-
Patarin, J.: `Hidden fields equations (HFE) and isomorphisms of polynomial (IP): two new families of asymmetric algorithms', Proc. EUROCRYPT'96, May 1996, Saragossa, Spain, p. 33–48, (LNCS, 1070).
-
21)
-
Ding, J.: `A new variant of the Matsumoto-Imai cryptosystem through perturbation', Proc. PKC'04, March 2004, Singapore, p. 305–318, (LNCS, 2947).
-
22)
-
Patarin, J., Goubin, L., Courtois, N.: `C*', Proc. ASIACRYPT'98, October 1998, Beijing, China, p. 35–50, (LNCS, 1514).
-
23)
-
Shamir, A.: `Efficient signature schemes based on birational permutations', Proc. CRYPTO'93, August 1993, Santa Barbara, CA, USA, p. 1–12, (LNCS, 773).
-
24)
-
Kipnis, A., Patarin, J., Goubin, L.: `Unbalanced oil and vinegar signature scheme', Proc. EUROCRYPT'99, May 1999, Prague, Czech, p. 206–222, (LNCS, 1592).
-
25)
-
Courtois, N., Klimov, A., Patarin, J., Shamir, A.: `Efficient algorithms for solving overdefined systems of multivariate polynomial equations', Proc. EUROCRYPT'00, May 2000, Bruges, Belgium, p. 392–407, (LNCS, 1807).
-
26)
-
Jakobsen, T., Knudsen, L.R.: `The interpolation attack on block ciphers', Proc. FSE'97, January 1997, Haifa, Israel, p. 28–40, (LNCS, 1267).
-
27)
-
Dinur, I., Shamir, A.: `Cubic attacks on tweakable black box polynomials', Proc. EUROCRYPT'09, April 2009, Cologne, Germany, p. 278–299, (LNCS, 5479).
-
28)
-
Courtois, N.: `Higher order correlation attacks, XL algorithm and cryptanalysis of Toyocrypt', Proc. ICISC'02, November 2002, Seoul, Korea, p. 182–199, (LNCS, 2587).
-
29)
-
J.-C. Faugère
.
A new efficient algorithm for computing Gröbner bases (F4).
J. Pure Appl. Algebra
,
61 -
88
-
30)
-
Yang, B.Y., Chen, J.M.: `Building secure tame-like multivariate public-key cryptosystems: the new TTS', Proc. ACISP'05, July 2005, Brisbane, Australia, p. 518–531, (LNCS, 3574).
-
31)
-
A.K. Lenstra
.
Factoring multivariate polynomials over algebraic number fields.
SIAM J. Comput.
,
3 ,
591 -
598
-
32)
-
Patarin, J.: `Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt'88', Proc. CRYPTO'95, August 1995, Santa Barbara, CA, USA, p. 248–261, (LNCS, 963).
-
33)
-
D.Y. Grigoriev ,
M. Karpinski ,
M.F. Singer
.
Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields.
SIAM J. Comput.
,
6 ,
1059 -
1063
-
34)
-
https://www.cosic.esat.kuleuven.be/nessie/, accessed September 2007.
-
35)
-
Matsumoto, T., Imai, H.: `Public quadratic polynomial-tuples for efficient signature-verification and message encryption', Proc. EUROCRYPT'88, May 1988, Davos, Switzerland, p. 419–453, (LNCS, 330).
-
36)
-
Courtois, N.: `The security of hidden field equations (HFE)', Proc. CT-RSA'01, April 2001, San Francisco, CA, USA, p. 266–281, (LNCS, 2020).
-
37)
-
Nie, X., Jiang, X., Hu, L., Ding, J.: `Cryptanalysis of two new instances of TTM cryptosystem', IACR Cryptology ePrint Archive, report 2007/381, 2007, available at: http://www.eprint.iacr.org.
-
38)
-
Biham, E.: `Cryptanalysis of Patarin's 2-round public key system with S boxes (2R)', Proc. EUROCRYPT'00, May 2000, Bruges, Belgium, p. 408–416, (LNCS, 1807).
-
39)
-
Patarin, J., Goubin, L.: `Asymmetric cryptography with S-boxes', Proc. ICICS'97, November 1997, Beijing, China, p. 369–380, (LNCS, 1334).
-
40)
-
C. Wolf ,
A. Braeken ,
B. Preneel
.
On the security of stepwise triangular systems.
Des. Codes Cryptogr.
,
3 ,
285 -
302
-
41)
-
Kurosawa, K., Iwata, T., Quang, V.D.: `Root finding interpolation attack', Proc. SAC'00, August 2000, Waterloo, Ontario, Canada, p. 303–314, (LNCS, 2012).
-
42)
-
Kipnis, A., Shamir, A.: `Cryptanalysis of the HFE public key cryptosystem by relinearization', Proc. CRYPTO'99, August 1999, Santa Barbara, CA, USA, p. 19–30, (LNCS, 1666).
-
43)
-
Ding, J., Hu, L., Nie, X., Li, J., Wagner, J.: `High order linearization equation (HOLE) attack on multivariate public key cryptosystems', Proc. PKC'07, April 2007, Beijing, China, p. 233–248, (LNCS, 4450).
-
44)
-
Ding, J., Hodges, T.: `Cryptanalysis of an implementation scheme of TTM', IACR Cryptology ePrint Archive, report 2003/084, 2003, available at: http://www.eprint.iacr.org.
-
45)
-
J. Patarin ,
L. Goubin
.
Asymmetric cryptography with S-boxes (extended version).
-
46)
-
A. Dür ,
J. Grabmeier
.
Applying coding theory to sparse interpolation.
SIAM J. Comput.
,
4 ,
695 -
704
-
47)
-
Billet, O., Gilbert, H.: `A traceable block cipher', Proc. ASIACRYPT'03, November 2003, Taipei, Taiwan, p. 331–346, (LNCS, 2894).
-
48)
-
Kipnis, A., Shamir, A.: `Cryptanalysis of the oil & vinegar signature scheme', Proc. CRYPTO'98, August 1998, Santa Barbara, CA, USA, p. 257–267, (LNCS, 1462).
-
49)
-
Patarin, J., Courtois, N., Goubin, L.: `FLASH, a fast multivariate signature Algorithm', Proc. CT-RSA'01, April 2001, San Francisco, CA, USA, p. 298–307, (LNCS, 2020).
-
50)
-
Moh, T.: `Two new examples of TTM', IACR Cryptology ePrint Archive, report 2007/144, 2007, available at: http://www.eprint.iacr.org.
-
51)
-
T. Moh
.
A public key system with signature and master key functions.
Commun. Algebr.
,
5 ,
2207 -
2222
-
52)
-
Ye, D., Lam, K., Dai, Z.: `Cryptanalysis of “2R” schemes', Proc. CRYPTO'99, August 1999, Santa Barbara, CA, USA, p. 315–325, (LNCS, 1666).
-
53)
-
Nie, X., Hu, L., Li, J., Updegrove, C., Ding, J.: `Breaking a new instance of TTM cryptosystems', Proc. ACNS'06, June 2006, Singapore, p. 210–225, (LNCS, 3989).
-
54)
-
Youssef, A.M., Gong, G.: `On the interpolation attacks on block ciphers', Proc. FSE'00, April 2000, New York, NY, USA, p. 109–120, (LNCS, 1978).
-
55)
-
Goubin, L., Courtois, N.: `Cryptanalysis of the TTM cryptosystem', Proc. ASIACRYPT'00, December 2000, Kyoto, Japan, p. 44–57, (LNCS, 1976).
-
56)
-
Dubois, V., Fouque, P.-A., Shamir, A.: `Practical cryptanalysis of SFLASH', Proc. CRYPTO'07, 19–23 August 2007, Santa Barbara, CA, USA, p. 1–12, (LNCS, 4622).
-
57)
-
Ben-Or, M., Tiwari, P.: `A deterministic algorithm for sparse multivariate polynomial interpolation', Proc. 20th ACM Symp. on Theory of Computing, May 1998, Chicago, IL, USA, p. 301–309.
-
58)
-
Moriai, S., Shimoyama, T., Kaneko, T.: `Interpolation attacks of the block cipher: SNAKE', Proc. FSE'99, March 1999, Rome, Italy, p. 275–289, (LNCS, 1636).
-
59)
-
D. Ye ,
Z. Dai ,
K. Lam
.
Decomposing attacks on asymmetric cryptography based on mapping composition.
J. Cryptol.
,
2 ,
137 -
150
-
60)
-
D. Cox ,
J. Little ,
D. O'shea
.
(1991)
Ideals, varieties and algorithms: an introduction to computational algebraic geometry and communicative algebra.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2007.0110
Related content
content/journals/10.1049/iet-ifs.2007.0110
pub_keyword,iet_inspecKeyword,pub_concept
6
6