Cryptanalysis of a Theorem: Decomposing the Only Known Solution to the Big APN Problem

详细信息    查看全文

• 关键词：Boolean functions ; APN ; Butterfly structure ; S ; Box decomposition ; CCZ ; equivalence ; Feistel Network ; Bitsliced implementation
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9815
• 期：1
• 页码：93-122
• 全文大小：1,011 KB
• 参考文献：1.Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. J. Cryptol. 4(1), 3–72 (1991)MathSciNet CrossRef MATH
  2.Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
  3.Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption Standard. Springer, Heidelberg (2002)CrossRef MATH
  4.Nyberg, K.: Differentially uniform mappings for cryptography. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 55–64. Springer, Heidelberg (1994)
  5.Browning, K., Dillon, J., McQuistan, M., Wolfe, A.: An APN permutation in dimension six. Finite Fields Theory Appl. 518, 33–42 (2010)MathSciNet CrossRef MATH
  6.Bilgin, B., Bogdanov, A., Knežević, M., Mendel, F., Wang, Q.: Fides: lightweight authenticated cipher with side-channel resistance for constrained hardware. In: Bertoni, G., Coron, J.-S. (eds.) CHES 2013. LNCS, vol. 8086, pp. 142–158. Springer, Heidelberg (2013)CrossRef
  7.Biryukov, A., Perrin, L., Udovenko, A.: Reverse-engineering the S-box of Streebog, Kuznyechik and STRIBOBr1. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 372–402. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49890-3_​15 CrossRef
  8.Biryukov, A., Perrin, L.: On reverse-engineering S-Boxes with hidden design criteria or structure. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 116–140. Springer, Berlin Heidelberg (2015)CrossRef
  9.Bogdanov, A., Leander, G., Nyberg, K., Wang, M.: Integral and multidimensional linear distinguishers with correlation zero. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 244–261. Springer, Heidelberg (2012)CrossRef
  10.Biryukov, A., Shamir, A.: Structural cryptanalysis of SASAS. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 394–405. Springer, Heidelberg (2001)
  11.Biryukov, A., De Cannière, C., Braeken, A., Preneel, B.: A toolbox for cryptanalysis: linear and affine equivalence algorithms. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 33–50. Springer, Heidelberg (2003)CrossRef
  12.Developers, T.S.: SageMath, the Sage Mathematics Software System (Version 7.1) (2016). http://​www.​sagemath.​org
  13.Perrin, L., Udovenko, A., Biryukov, A.: Cryptanalysis of a Theorem: Decomposing the Only Known Solution to the Big APN Problem (Full Version). Cryptology ePrint Archive, Report 2016/539 (2016). http://​eprint.​iacr.​org/​
  14.Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suitable for DES-like cryptosystems. Des. Codes Crypt. 15(2), 125–156 (1998)MathSciNet CrossRef MATH
  15.Blondeau, C., Nyberg, K.: Perfect nonlinear functions and cryptography. Finite Fields Appl. 32, 120–147 (2015). Special Issue: Second Decade of FFAMathSciNet CrossRef MATH
  16.Budaghyan, L., Carlet, C., Pott, A.: New classes of almost bent and almost perfect nonlinear polynomials. IEEE Trans. Inf. Theory 52(3), 1141–1152 (2006)MathSciNet CrossRef MATH
  17.Daemen, J., Govaerts, R., Vandewalle, J.: A new approach to block cipher design. In: Anderson, R. (ed.) FSE 1993. LNCS, vol. 809, pp. 18–32. Springer, Heidelberg (1994)CrossRef
  18.Bracken, C., Leander, G.: A highly nonlinear differentially 4 uniform power mapping that permutes fields of even degree. Finite Fields Appl. 16(4), 231–242 (2010)MathSciNet CrossRef MATH
  19.Bracken, C., Tan, C.H., Tan, Y.: Binomial differentially 4 uniform permutations with high nonlinearity. Finite Fields Appl. 18(3), 537–546 (2012)MathSciNet CrossRef MATH
  20.Li, Y., Wang, M.: Constructing differentially 4-uniform permutations over GF(\(2^{2m}\) ) from quadratic APN permutations over GF(\(2^{2m+1}\) ). Des. Codes Crypt. 72(2), 249–264 (2014)MathSciNet CrossRef MATH
  21.Kyureghyan, G.M., Suder, V.: On inverses of APN exponents. In: 2012 IEEE International Symposium on Information Theory Proceedings (ISIT), pp. 1207–1211. IEEE (2012)
  22.Carlet, C.: Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions. Des. Codes Crypt. 59(1), 89–109 (2011)MathSciNet CrossRef MATH
  23.Li, Y., Wang, M.: Constructing S-Boxes for lightweight cryptography with Feistel structure. In: Batina, L., Robshaw, M. (eds.) CHES 2014. LNCS, vol. 8731, pp. 127–146. Springer, Heidelberg (2014)
  
• 作者单位：Léo Perrin (15)
  Aleksei Udovenko (15)
  Alex Biryukov (15) (16)
  
  15. SnT, University of Luxembourg, Luxembourg City, Luxembourg
  16. CSC, University of Luxembourg, Luxembourg City, Luxembourg
  
• 丛书名：Advances in Cryptology ¨C CRYPTO 2016
• ISBN：978-3-662-53008-5
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9815

文摘

The existence of Almost Perfect Non-linear (APN) permutations operating on an even number of bits has been a long standing open question until Dillon et al., who work for the NSA, provided an example on 6 bits in 2009.