Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Adversary-Dependent Lossy Trapdoor Function from Hardness of Factoring Semi-smooth RSA Subgroup Moduli Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

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

verfasst von : Léo Perrin, Aleksei Udovenko, Alex Biryukov

Erschienen in: Advances in Cryptology – CRYPTO 2016

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

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.
In this paper, we apply methods intended to reverse-engineer S-Boxes with unknown structure to this permutation and find a simple decomposition relying on the cube function over \(GF(2^3)\). More precisely, we show that it is a particular case of a permutation structure we introduce, the butterfly. Such butterflies are 2n-bit mappings with two CCZ-equivalent representations: one is a quadratic non-bijective function and one is a degree \(n+1\) permutation. We show that these structures always have differential uniformity at most 4 when n is odd. A particular case of this structure is actually a 3-round Feistel Network with similar differential and linear properties. These functions also share an excellent non-linearity for \(n=3,5,7\).
Furthermore, we deduce a bitsliced implementation and significantly reduce the hardware cost of a 6-bit APN permutation using this decomposition, thus simplifying the use of such a permutation as building block for a cryptographic primitive.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel FHE Circuit Privacy Almost for Free
Nächstes Kapitel The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS
Fußnoten
1
The maximum is taken over all non-zero line indices.
 
2
This object is also sometimes referred to as the “correlation matrix”. Up to a multiplication by a constant factor, the coefficients in the LAT of a function also form its Walsh Spectrum.
 
3
If we had attacked U instead of \(T^{-1}\), then detaching a Feistel function in this way leads only to a nonlinear Feistel function (regardless of the side), which supports our choice of \(T'^{-1}\) as an easier target.
 
4
As \(S_{\mathcal {I}}\) is a permutation, we ignore the first line and the first column of its LAT.
 
5
For larger fields the inverse function does not satisfy the property and therefore such propagation is impossible. An anonymous reviewer pointed out that this works in \(\mathbb {F}_{2^{3}}\) because the inverse function there has boolean algebraic degree 2 and therefore its derivative is linear.
 
6
Actually we optimized the search by utilizing the equivalence classes given by Theorem 2.
 
7
We used the digital cell library SAED90n-1P9M in the “normal \(V_t\), high temperature, nominal voltage” corner.
 
8
We also considered implementing the cube function using finite field arithmetic but could not easily improve our results.
 
Literatur
1.
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)CrossRefMATH
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)MathSciNetCrossRefMATH
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.
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)MathSciNetCrossRefMATH
15.
Blondeau, C., Nyberg, K.: Perfect nonlinear functions and cryptography. Finite Fields Appl. 32, 120–147 (2015). Special Issue: Second Decade of FFAMathSciNetCrossRefMATH
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)MathSciNetCrossRefMATH
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)MathSciNetCrossRefMATH
19.
Bracken, C., Tan, C.H., Tan, Y.: Binomial differentially 4 uniform permutations with high nonlinearity. Finite Fields Appl. 18(3), 537–546 (2012)MathSciNetCrossRefMATH
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)MathSciNetCrossRefMATH
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)MathSciNetCrossRefMATH
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)
Metadaten
Titel
Cryptanalysis of a Theorem: Decomposing the Only Known Solution to the Big APN Problem
verfasst von
Léo Perrin
Aleksei Udovenko
Alex Biryukov
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology – CRYPTO 2016

Print ISBN: 978-3-662-53007-8

Electronic ISBN: 978-3-662-53008-5

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-53008-5_4

Premium Partner

    Bildnachweise