APN Permutations - Revision history

NikiSpithaki: /* An APN Permutation in Dimension 6 */

2024-11-21T14:28:21Z

An APN Permutation in Dimension 6

← Older revision		Revision as of 14:28, 21 November 2024
Line 116:		Line 116:
	<center><math>+w^8x^{12}+w^{35}x^{11}+w^{44}x^{10}+w^{45}x^8+w^8x^7+w^{61}x^6+w^{59}x^5+w^{20}x^4+w^{12}x^3+w^{37}x^2+w^2x</math></center>		<center><math>+w^8x^{12}+w^{35}x^{11}+w^{44}x^{10}+w^{45}x^8+w^8x^7+w^{61}x^6+w^{59}x^5+w^{20}x^4+w^{12}x^3+w^{37}x^2+w^2x</math></center>

	where <math>w=u^{-2}</math><ref name="Dillon"></ref>.		where <math>w=u^{-2}</math>.<ref name="Dillon"></ref>

	It was used later in the cryptosystem Fides<ref name="BBKMW">B. Bilgin, A. Bogdanov, M. Knezevic, F. Mendel and Q. Wang. <i>Fides: lightweight authenticated cipher with side-channel resistance for constrained hardware.</i> Proceedings of International Workshop Cryptographic Hardware and Embedded Systems CHES 2013, Lecture Notes in Computer Science 8086, pp. 142-158, 2013.</ref>, which has been subsequently broken due to its weaknesses in the linear component.		It was used later in the cryptosystem Fides<ref name="BBKMW">B. Bilgin, A. Bogdanov, M. Knezevic, F. Mendel and Q. Wang. <i>Fides: lightweight authenticated cipher with side-channel resistance for constrained hardware.</i> Proceedings of International Workshop Cryptographic Hardware and Embedded Systems CHES 2013, Lecture Notes in Computer Science 8086, pp. 142-158, 2013.</ref>, which has been subsequently broken due to its weaknesses in the linear component.

NikiSpithaki: /* An APN Permutation in Dimension 6 */

2024-11-21T14:27:54Z

An APN Permutation in Dimension 6

← Older revision		Revision as of 14:27, 21 November 2024
Line 108:		Line 108:
	2. If <math>F\in\mathbb{F}_{2^m}[x]</math>, then <math>F</math> is not APN.		2. If <math>F\in\mathbb{F}_{2^m}[x]</math>, then <math>F</math> is not APN.

	The question of whether APN permutations exist in even dimension was a long-standing problem until, in 2009, Dillon presented an APN permutation (of algebraic degree <math>n-2</math> and nonlinearity <math>2^{n-1}-2^{n/2}</math>) in dimension 6~~<ref name="Dillon"></ref>~~.		The question of whether APN permutations exist in even dimension was a long-standing problem until, in 2009, Dillon presented an APN permutation (of algebraic degree <math>n-2</math> and nonlinearity <math>2^{n-1}-2^{n/2}</math>) in dimension 6.

	This function is CCZ-equivalent to the Kim function <math>\kappa(x)=x^3+x^{10}+ux^{24}</math> (where <math>u</math> is a primitive element of <math>\mathbb{F}_{2^6}</math>) and it is given by the polynomial		This function is CCZ-equivalent to the Kim function <math>\kappa(x)=x^3+x^{10}+ux^{24}</math> (where <math>u</math> is a primitive element of <math>\mathbb{F}_{2^6}</math>) and it is given by the polynomial
Line 116:		Line 116:
	<center><math>+w^8x^{12}+w^{35}x^{11}+w^{44}x^{10}+w^{45}x^8+w^8x^7+w^{61}x^6+w^{59}x^5+w^{20}x^4+w^{12}x^3+w^{37}x^2+w^2x</math></center>		<center><math>+w^8x^{12}+w^{35}x^{11}+w^{44}x^{10}+w^{45}x^8+w^8x^7+w^{61}x^6+w^{59}x^5+w^{20}x^4+w^{12}x^3+w^{37}x^2+w^2x</math></center>

	where <math>w=u^{-2}</math>.		where <math>w=u^{-2}</math><ref name="Dillon"></ref>.

	It was used later in the cryptosystem Fides<ref name="BBKMW">B. Bilgin, A. Bogdanov, M. Knezevic, F. Mendel and Q. Wang. <i>Fides: lightweight authenticated cipher with side-channel resistance for constrained hardware.</i> Proceedings of International Workshop Cryptographic Hardware and Embedded Systems CHES 2013, Lecture Notes in Computer Science 8086, pp. 142-158, 2013.</ref>, which has been subsequently broken due to its weaknesses in the linear component.		It was used later in the cryptosystem Fides<ref name="BBKMW">B. Bilgin, A. Bogdanov, M. Knezevic, F. Mendel and Q. Wang. <i>Fides: lightweight authenticated cipher with side-channel resistance for constrained hardware.</i> Proceedings of International Workshop Cryptographic Hardware and Embedded Systems CHES 2013, Lecture Notes in Computer Science 8086, pp. 142-158, 2013.</ref>, which has been subsequently broken due to its weaknesses in the linear component.

NikiSpithaki: /* An APN Permutation in Dimension 6 */

2024-11-21T09:18:13Z

An APN Permutation in Dimension 6

← Older revision		Revision as of 09:18, 21 November 2024
Line 111:		Line 111:

	This function is CCZ-equivalent to the Kim function <math>\kappa(x)=x^3+x^{10}+ux^{24}</math> (where <math>u</math> is a primitive element of <math>\mathbb{F}_{2^6}</math>) and it is given by the polynomial		This function is CCZ-equivalent to the Kim function <math>\kappa(x)=x^3+x^{10}+ux^{24}</math> (where <math>u</math> is a primitive element of <math>\mathbb{F}_{2^6}</math>) and it is given by the polynomial
	<center><math>g(x)=w^{45}x^{60}+w^{41}x^{58}+w^{43}x^{57}+w^{4}x^{56}+w^{50}x^{54}+w^{20}x^{53}+w^{45}x^{52}+w^{20}x^{51}+w^{23}x^{50}+w^{36}x^{49}+w^{56}x^{48}+w^{21}x^{46}+w^5x^{45}+w^{21}x^{44~~}+w^{28}x^{43~~}</math></center>		<center><math>g(x)=w^{45}x^{60}+w^{41}x^{58}+w^{43}x^{57}+w^{4}x^{56}+w^{50}x^{54}+w^{20}x^{53}+w^{45}x^{52}+w^{20}x^{51}+w^{23}x^{50}+w^{36}x^{49}+w^{56}x^{48}+w^{21}x^{46}+w^5x^{45}+w^{21}x^{44}</math></center>
	<center><math>+w^3x^{42}+w^{59}x^{41}+w^{58}x^{40}+w^{57}x^{39}+w^{53}x^{38}+w^{37}x^{37}+w^{40}x^{36}+w^{18}x^{35}+w^{41}x^{34}+w^{54}x^{33}+w^3x^{32}+w^{49}x^{30}+w^{41}x^{29~~}+w^{42}x^{28~~}</math></center>		<center><math>+w^{28}x^{43}+w^3x^{42}+w^{59}x^{41}+w^{58}x^{40}+w^{57}x^{39}+w^{53}x^{38}+w^{37}x^{37}+w^{40}x^{36}+w^{18}x^{35}+w^{41}x^{34}+w^{54}x^{33}+w^3x^{32}+w^{49}x^{30}+w^{41}x^{29}</math></center>
	<center><math>+w^{50}x^{27}+w^{53}x^{26}+w^{58}x^{25}+w^9x^{24}+x^{23}+w^{28}x^{22}+w^3x^{21}+w^{21}x^{20}+w^{52}x^{19}+w^{60}x^{17}+w^{59}x^{16}+w^{10}x^{15}+w^{42}x^{13~~}+w^8x^{12~~}</math></center>		<center><math>+w^{42}x^{28}+w^{50}x^{27}+w^{53}x^{26}+w^{58}x^{25}+w^9x^{24}+x^{23}+w^{28}x^{22}+w^3x^{21}+w^{21}x^{20}+w^{52}x^{19}+w^{60}x^{17}+w^{59}x^{16}+w^{10}x^{15}+w^{42}x^{13}</math></center>
	<center><math>+w^{35}x^{11}+w^{44}x^{10}+w^{45}x^8+w^8x^7+w^{61}x^6+w^{59}x^5+w^{20}x^4+w^{12}x^3+w^{37}x^2+w^2x</math></center>		<center><math>+w^8x^{12}+w^{35}x^{11}+w^{44}x^{10}+w^{45}x^8+w^8x^7+w^{61}x^6+w^{59}x^5+w^{20}x^4+w^{12}x^3+w^{37}x^2+w^2x</math></center>

	where <math>w=u^{-2}</math>.		where <math>w=u^{-2}</math>.

NikiSpithaki: /* An APN Permutation in Dimension 6 */

2024-11-20T14:15:31Z

An APN Permutation in Dimension 6

← Older revision		Revision as of 14:15, 20 November 2024
Line 110:		Line 110:
	The question of whether APN permutations exist in even dimension was a long-standing problem until, in 2009, Dillon presented an APN permutation (of algebraic degree <math>n-2</math> and nonlinearity <math>2^{n-1}-2^{n/2}</math>) in dimension 6<ref name="Dillon"></ref>.		The question of whether APN permutations exist in even dimension was a long-standing problem until, in 2009, Dillon presented an APN permutation (of algebraic degree <math>n-2</math> and nonlinearity <math>2^{n-1}-2^{n/2}</math>) in dimension 6<ref name="Dillon"></ref>.

	This function is CCZ-equivalent to the Kim function <math>\kappa(x)=x^3+x^{10}+ux^{24}</math> (where <math>u</math> is a primitive element of <math>\mathbb{F}_{2^6}</math>)~~, whose associated code~~ <math>C^{~~\perp~~}_F</math> ~~is therefore a double simplex code~~. It was used later in the cryptosystem Fides<ref name="BBKMW">B. Bilgin, A. Bogdanov, M. Knezevic, F. Mendel and Q. Wang. <i>Fides: lightweight authenticated cipher with side-channel resistance for constrained hardware.</i> Proceedings of International Workshop Cryptographic Hardware and Embedded Systems CHES 2013, Lecture Notes in Computer Science 8086, pp. 142-158, 2013.</ref>, which has been subsequently broken due to its weaknesses in the linear component.		This function is CCZ-equivalent to the Kim function <math>\kappa(x)=x^3+x^{10}+ux^{24}</math> (where <math>u</math> is a primitive element of <math>\mathbb{F}_{2^6}</math>) and it is given by the polynomial
			<center><math>g(x)=w^{45}x^{60}+w^{41}x^{58}+w^{43}x^{57}+w^{4}x^{56}+w^{50}x^{54}+w^{20}x^{53}+w^{45}x^{52}+w^{20}x^{51}+w^{23}x^{50}+w^{36}x^{49}+w^{56}x^{48}+w^{21}x^{46}+w^5x^{45}+w^{21}x^{44}+w^{28}x^{43}</math></center>
			<center><math>+w^3x^{42}+w^{59}x^{41}+w^{58}x^{40}+w^{57}x^{39}+w^{53}x^{38}+w^{37}x^{37}+w^{40}x^{36}+w^{18}x^{35}+w^{41}x^{34}+w^{54}x^{33}+w^3x^{32}+w^{49}x^{30}+w^{41}x^{29}+w^{42}x^{28}</math></center>
			<center><math>+w^{50}x^{27}+w^{53}x^{26}+w^{58}x^{25}+w^9x^{24}+x^{23}+w^{28}x^{22}+w^3x^{21}+w^{21}x^{20}+w^{52}x^{19}+w^{60}x^{17}+w^{59}x^{16}+w^{10}x^{15}+w^{42}x^{13}+w^8x^{12}</math></center>
			<center><math>+w^{35}x^{11}+w^{44}x^{10}+w^{45}x^8+w^8x^7+w^{61}x^6+w^{59}x^5+w^{20}x^4+w^{12}x^3+w^{37}x^2+w^2x</math></center>

			where <math>w=u^{-2}</math>.

			It was used later in the cryptosystem Fides<ref name="BBKMW">B. Bilgin, A. Bogdanov, M. Knezevic, F. Mendel and Q. Wang. <i>Fides: lightweight authenticated cipher with side-channel resistance for constrained hardware.</i> Proceedings of International Workshop Cryptographic Hardware and Embedded Systems CHES 2013, Lecture Notes in Computer Science 8086, pp. 142-158, 2013.</ref>, which has been subsequently broken due to its weaknesses in the linear component.

	Dillon's function is also EA-equivalent to an involution and it is studied further in the introduction of the <i>butterfly construction</i><ref name="PUB">L. Perrin, A. Udovenko, A. Biryukov. <i>Cryptanalysis of a theorem: decomposing the only known solution to the big APN problem.</i> Proceedings of CRYPTO 2016, Lecture Notes in Computer Science 9815, part II, pp. 93-122, 2016.</ref>. Unfortunately, this construction does not allow obtaining APN permutations in more than six variables<ref name="PST">L. Perrin, A. Canteaut, S. Tian. <i>If a generalized butterfly is APN then it operates on 6 bits.</i> Special Issue on Boolean Functions and Their Applications 2018, Cryptography and Communications 11 (6), pp. 1147-1164, 2019.</ref>.		Dillon's function is also EA-equivalent to an involution and it is studied further in the introduction of the <i>butterfly construction</i><ref name="PUB">L. Perrin, A. Udovenko, A. Biryukov. <i>Cryptanalysis of a theorem: decomposing the only known solution to the big APN problem.</i> Proceedings of CRYPTO 2016, Lecture Notes in Computer Science 9815, part II, pp. 93-122, 2016.</ref>. Unfortunately, this construction does not allow obtaining APN permutations in more than six variables<ref name="PST">L. Perrin, A. Canteaut, S. Tian. <i>If a generalized butterfly is APN then it operates on 6 bits.</i> Special Issue on Boolean Functions and Their Applications 2018, Cryptography and Communications 11 (6), pp. 1147-1164, 2019.</ref>.

NikiSpithaki: /* APN Permutations and Codes */

2024-11-20T13:45:40Z

APN Permutations and Codes

← Older revision		Revision as of 13:45, 20 November 2024
Line 92:		Line 92:
	A binary linear <math>[2^k-1,k,2^{k-1}]-</math>code <math>C</math> in <math>\mathbb{F}_2^n</math> is called <i>simplex</i>. Simplex codes constitute a family of linear error-correcting or error-detecting block codes, easily implemented as polynomial codes (i.e. codes whose encoding and decoding algorithms may be conveniently expressed in terms of polynomials over a base field).		A binary linear <math>[2^k-1,k,2^{k-1}]-</math>code <math>C</math> in <math>\mathbb{F}_2^n</math> is called <i>simplex</i>. Simplex codes constitute a family of linear error-correcting or error-detecting block codes, easily implemented as polynomial codes (i.e. codes whose encoding and decoding algorithms may be conveniently expressed in terms of polynomials over a base field).

	A code <math>C</math> is called a <i>double simplex code</i> if it can be written as a direct sum of two simplex <math>[2^k-1,k,2^{k-1}]-</math>codes. The following result provides a connection between APN permutations and double simplex codes:		A <math>2k-</math>dimensional code <math>C</math> is called a <i>double simplex code</i> if it can be written as a direct sum of two simplex <math>[2^k-1,k,2^{k-1}]-</math>codes. The following result provides a connection between APN permutations and double simplex codes:

	<strong>Theorem.</strong><ref name="Dillon2">Browning, K.A. & Dillon, J.F. & Kibler, R.E. & McQuistan, M.T.. (2009). <i>APN polynomials and related codes.</i> Journal of Combinatorics, Information & System Sciences. 34.</ref> Let <math>F:\mathbb{F}_{2^n}\rightarrow\mathbb{F}_{2^n}</math> be APN, with <math>F(0)=0</math>.		<strong>Theorem.</strong><ref name="Dillon2">Browning, K.A. & Dillon, J.F. & Kibler, R.E. & McQuistan, M.T.. (2009). <i>APN polynomials and related codes.</i> Journal of Combinatorics, Information & System Sciences. 34.</ref> Let <math>F:\mathbb{F}_{2^n}\rightarrow\mathbb{F}_{2^n}</math> be APN, with <math>F(0)=0</math>.

NikiSpithaki: /* APN Permutations and Codes */

2024-11-19T15:25:12Z

APN Permutations and Codes

← Older revision		Revision as of 15:25, 19 November 2024
Line 96:		Line 96:
	<strong>Theorem.</strong><ref name="Dillon2">Browning, K.A. & Dillon, J.F. & Kibler, R.E. & McQuistan, M.T.. (2009). <i>APN polynomials and related codes.</i> Journal of Combinatorics, Information & System Sciences. 34.</ref> Let <math>F:\mathbb{F}_{2^n}\rightarrow\mathbb{F}_{2^n}</math> be APN, with <math>F(0)=0</math>.		<strong>Theorem.</strong><ref name="Dillon2">Browning, K.A. & Dillon, J.F. & Kibler, R.E. & McQuistan, M.T.. (2009). <i>APN polynomials and related codes.</i> Journal of Combinatorics, Information & System Sciences. 34.</ref> Let <math>F:\mathbb{F}_{2^n}\rightarrow\mathbb{F}_{2^n}</math> be APN, with <math>F(0)=0</math>.

	<math>F</math> is CCZ-equivalent to an APN permutation if and only if <math>C_F^{\perp}</math> is a double simplex code (i.e. <math>C_F^{\perp}=C_1\oplus C_2</math>, where <math>C_1, C_2</math> are simplex <math>[2^n-1,n,2^{n-1}]-</math>codes).		<math>F</math> is CCZ-equivalent to an APN permutation if and only if <math>C_F^{\perp}</math> is a double simplex code, i.e. <math>C_F^{\perp}=C_1\oplus C_2</math>, where <math>C_1, C_2</math> are simplex <math>[2^n-1,n,2^{n-1}]-</math>codes.

	==An APN Permutation in Dimension 6==		==An APN Permutation in Dimension 6==

NikiSpithaki: /* APN Permutations and Codes */

2024-11-19T15:23:15Z

APN Permutations and Codes

← Older revision		Revision as of 15:23, 19 November 2024
Line 66:		Line 66:
	Any linear subspace <math>C</math> of <math>\mathbb{F}_2^n</math> of dimension <math>k</math> is called a <i>binary linear code of length</i> <math>n</math> <i>and dimension</i> <math>k</math> and is denoted by <math>[n,k,d]</math>, where <math>d</math> is the minimum Hamming distance of <math>C</math>.		Any linear subspace <math>C</math> of <math>\mathbb{F}_2^n</math> of dimension <math>k</math> is called a <i>binary linear code of length</i> <math>n</math> <i>and dimension</i> <math>k</math> and is denoted by <math>[n,k,d]</math>, where <math>d</math> is the minimum Hamming distance of <math>C</math>.

	Any linear <math>[n,k,d]</math> code <math>C</math> is associated with its <i>dual</i> <math>[n,n-k,d^{\perp}]</math> code, denoted by <math>C^{\perp}</math> and defined as <math>C^{\perp}=\{x\in\mathbb{F}_2^n\;\|\;c\cdot x=0, \;\forall c\in C\}.</math>		Any linear <math>[n,k,d]-</math>code <math>C</math> is associated with its <i>dual</i> <math>[n,n-k,d^{\perp}]-</math>code, denoted by <math>C^{\perp}</math> and defined as <math>C^{\perp}=\{x\in\mathbb{F}_2^n\;\|\;c\cdot x=0, \;\forall c\in C\}.</math>

	Let <math>\mathcal{H}</math> be a binary <math>(r\times n)</math> matrix. We say that a linear binary code <math>C</math> of length <math>n</math> is defined by the <i>parity check matrix</i> <math>\mathcal{H}</math> if <math>C=\{c\in\mathbb{F}_2^n\;\|\;c\mathcal{H}^t=0\},</math> where <math>\mathcal{H}^t</math> is the transposed matrix of <math>\mathcal{H}</math>.		Let <math>\mathcal{H}</math> be a binary <math>(r\times n)</math> matrix. We say that a linear binary code <math>C</math> of length <math>n</math> is defined by the <i>parity check matrix</i> <math>\mathcal{H}</math> if <math>C=\{c\in\mathbb{F}_2^n\;\|\;c\mathcal{H}^t=0\},</math> where <math>\mathcal{H}^t</math> is the transposed matrix of <math>\mathcal{H}</math>.

NikiSpithaki: /* APN Permutations and Codes */

2024-11-19T15:22:39Z

APN Permutations and Codes

← Older revision		Revision as of 15:22, 19 November 2024
Line 64:		Line 64:
	==APN Permutations and Codes==		==APN Permutations and Codes==


	The (Hamming) weight of any vector <math>x\in \mathbb{F}_2^n</math> is denoted by <math>wt(x)</math>, and the (Hamming) distance between any two vectors <math>x</math> and <math>y</math> from <math>\mathbb{F}_2^n</math> is denoted by <math>d(x,y)</math>.
	Any linear subspace <math>C</math> of <math>\mathbb{F}_2^n</math> of dimension <math>k</math> is called a <i>binary linear code of length</i> <math>n</math> <i>and dimension</i> <math>k</math> and is denoted by <math>[n,k,d]</math>, where <math>d</math> is the minimum Hamming distance of <math>C</math>.		Any linear subspace <math>C</math> of <math>\mathbb{F}_2^n</math> of dimension <math>k</math> is called a <i>binary linear code of length</i> <math>n</math> <i>and dimension</i> <math>k</math> and is denoted by <math>[n,k,d]</math>, where <math>d</math> is the minimum Hamming distance of <math>C</math>.

NikiSpithaki: /* APN Permutations and Codes */

2024-11-19T15:21:47Z

APN Permutations and Codes

← Older revision		Revision as of 15:21, 19 November 2024
Line 94:		Line 94:
	A binary linear <math>[2^k-1,k,2^{k-1}]-</math>code <math>C</math> in <math>\mathbb{F}_2^n</math> is called <i>simplex</i>. Simplex codes constitute a family of linear error-correcting or error-detecting block codes, easily implemented as polynomial codes (i.e. codes whose encoding and decoding algorithms may be conveniently expressed in terms of polynomials over a base field).		A binary linear <math>[2^k-1,k,2^{k-1}]-</math>code <math>C</math> in <math>\mathbb{F}_2^n</math> is called <i>simplex</i>. Simplex codes constitute a family of linear error-correcting or error-detecting block codes, easily implemented as polynomial codes (i.e. codes whose encoding and decoding algorithms may be conveniently expressed in terms of polynomials over a base field).

			A code <math>C</math> is called a <i>double simplex code</i> if it can be written as a direct sum of two simplex <math>[2^k-1,k,2^{k-1}]-</math>codes. The following result provides a connection between APN permutations and double simplex codes:

	<strong>Theorem.</strong><ref name="Dillon2">Browning, K.A. & Dillon, J.F. & Kibler, R.E. & McQuistan, M.T.. (2009). <i>APN polynomials and related codes.</i> Journal of Combinatorics, Information & System Sciences. 34.</ref> Let <math>F:\mathbb{F}_{2^n}\rightarrow\mathbb{F}_{2^n}</math> be APN, with <math>F(0)=0</math>.		<strong>Theorem.</strong><ref name="Dillon2">Browning, K.A. & Dillon, J.F. & Kibler, R.E. & McQuistan, M.T.. (2009). <i>APN polynomials and related codes.</i> Journal of Combinatorics, Information & System Sciences. 34.</ref> Let <math>F:\mathbb{F}_{2^n}\rightarrow\mathbb{F}_{2^n}</math> be APN, with <math>F(0)=0</math>.

NikiSpithaki: /* APN Permutations and Codes */

2024-11-19T15:14:32Z

APN Permutations and Codes

← Older revision		Revision as of 15:14, 19 November 2024
Line 76:		Line 76:

	<strong>Theorem.</strong> Let <math>F</math> be a function on <math>\mathbb{F}_{2^m}</math> such that <math>F(0) = 0</math> and let <math>C_F</math> be the		<strong>Theorem.</strong> Let <math>F</math> be a function on <math>\mathbb{F}_{2^m}</math> such that <math>F(0) = 0</math> and let <math>C_F</math> be the
	<math>[2^m − 1,k,d]</math> code defined by the parity check matrix		<math>[2^m − 1,k,d]-</math>code defined by the parity check matrix

	<div><math>\mathcal{H}_F=\begin{pmatrix}		<div><math>\mathcal{H}_F=\begin{pmatrix}