REVIEW 8 minor 44 references
On the Differential-Linear Connectivity Table of Vectorial Boolean Functions
T0 review · 0 major / 8 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The DLCT is half the autocorrelation table of the cryptographic S-box.
desk verdict Solid theory paper connecting DLCT to autocorrelation; main results hold, but Proposition 3 contains a real (if isolated) error that should be corrected. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The carrying object is the autocorrelation table of a vectorial Boolean function, defined by $AC_F(u,v)=\sum_{x\in\mathbb F_2^n}(-1)^{v\cdot(F(x)+F(x+u))}$, whose entries the DLCT matches up to the factor $1/2$. The two workhorse identities are the Fourier relation between $AC_F$ and the squared Walsh transform $W_F(\omega,v)^2$, and the Fourier duality between each row of the autocorrelation table and the corresponding row of the differential distribution table. These identities let the paper convert known autocorrelation bounds into DLCT bounds, force divisibility of the entries from the algebraic degree, and express the tables of APN, plateaued, and AB functions as Walsh transforms of auxiliary Boolean functions.
What would settle it
Compute the DLCT and autocorrelation tables directly from the definitions for any explicit S-box, for instance the inverse map $x\mapsto x^{-1}$ on $\mathbb F_{2^8}$; if any entry fails $DLCT_F(u,v)=\frac12 AC_F(u,v)$, Proposition 1 is false. To test the lower bound, search exhaustively or by large random sampling among $(6,6)$-permutations for one whose absolute indicator is $8$; since the theorem requires $\Delta_F>2^{6/2}=8$, such a permutation would refute it.
Extended reading notes
Core claim
On its own terms, the paper establishes that the DLCT is the autocorrelation table up to a constant factor: $DLCT_F(u,v) = \frac{1}{2}AC_F(u,v)$ for all $(u,v)$, so $\max_{u\neq 0, v\neq 0}|DLCT_F(u,v)|=\Delta_F/2$ where $\Delta_F$ is the absolute indicator. It proves the Fourier identity $AC_F(u,v)=2^{-n}\sum_{\omega\in\mathbb F_2^n}(-1)^{u\cdot\omega}W_F(\omega,v)^2$ and the dual relation with the differential distribution table, and from these derives $\Delta_F \ge \sqrt{(2^{m+n+1}-2^{2n})/(2^m-1)}$ whenever $m\ge n$; for $(n,n)$-permutations this says $\Delta_F>2^{n/2}$. It also shows that for permutations the autocorrelation entries are divisible by $8$, hence DLCT entries by $4$, that the autocorrelation spectrum is affine-invariant and its absolute version EA-invariant but not CCZ-invariant, and that the optimal 4-bit S-boxes have exactly three possible DLCT spectra. For APN, plateaued, and AB functions the autocorrelation is shown to be, up to sign and a power of two, the Walsh transform of a balanced Boolean function attached to the function.
Load-bearing premise
The exhaustive DLCT spectra claimed for optimal 4-bit S-boxes inherit the completeness of the external classification that every optimal 4-bit S-box is equivalent to one of sixteen representatives; the paper computes autocorrelation spectra from those representatives but does not re-derive the classification itself.
Editorial extensions
If this is right
- Any known bound or construction for the absolute indicator of vectorial Boolean functions transfers directly to the largest DLCT entry, so the DLCT inherits a mature theory instead of starting from scratch.
- Every $(n,n)$-permutation has some nonzero input difference and output mask with $|DLCT|>2^{n/2-1}$, and every such entry is divisible by $4$; both facts constrain what differential-linear distinguishers can achieve.
- The DLCT spectrum is affine-invariant and its absolute spectrum is EA-invariant, so it can be used as a fingerprint in S-box classification, while two CCZ-equivalent functions may have different tables.
- For APN functions, the DLCT is determined by the Walsh transform of the indicator of the image of the derivative; hence the question of how small the DLCT can be for an APN function is the same as the question of the linearity of balanced Boolean functions.
- For quadratic functions the DLCT entries lie in $\{0,\pm 2^n\}$, or smaller subsets for Gold monomials, which means these functions either have no differential-linear correlation for a given pair or have the maximum possible one.
Reading between the lines
- Not stated in the paper: the classical global-avalanche-characteristics criteria for Boolean functions can be reinterpreted, column by column, as design criteria for differential-linear resistance of S-boxes.
- Not stated in the paper: because the DLCT spectrum is not CCZ-invariant while differential uniformity and nonlinearity are, the table can distinguish some CCZ-equivalent S-boxes, making it a candidate invariant for S-box classification.
- Not stated in the paper: combining the lower bound with the divisibility law suggests the true minimal absolute indicator for small permutations is larger than the generic bound, and an exhaustive search at $n=6$ would give the exact value.
- A testable extension beyond the paper: compute DLCT spectra for the known optimal 6-bit and 8-bit S-box families directly from autocorrelation, avoiding new attack simulations.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the differential-linear connectivity table (DLCT) of vectorial Boolean functions and proves that DLCT_F(u,v) = (1/2)AC_F(u,v), where AC_F is the autocorrelation function. It then characterizes the autocorrelation in terms of the Walsh transform and the DDT, derives a lower bound on the absolute indicator for (n,m)-functions with m≥n, establishes divisibility properties, and analyzes invariance under affine, EA, and CCZ equivalence. It exhaustively lists the autocorrelation spectra of optimal 4-bit S-boxes using the Leander–Poschmann classification. The paper also gives results for APN, plateaued, AB functions, and for specific polynomial families including Gold, Kasami, Welch, Bracken–Leander, quadratic, and inverse functions.
Significance. The equivalence between DLCT and autocorrelation is a clean and useful bridge that lets cryptanalysts transfer the extensive autocorrelation theory to differential-linear attacks. The lower bound Δ_F ≥ sqrt((2^{m+n+1}-2^{2n})/(2^m-1)) for m≥n is a new generic result, and the exhaustive table of autocorrelation spectra for optimal 4-bit S-boxes is a practical reference. The connections for APN and AB functions to Walsh transforms of balanced or dual Boolean functions are elegant and likely to stimulate further work. The paper does not provide machine-checked proofs or code, but the derivations are standard and reproducible. The main theoretical claims are sound, although a few local errors need correction.
minor comments (8)
- [Section 3-B, Proposition 3] The displayed identity ∑_{u∈F2^n,v∈F2^m} ACF(u,v) = 2^{m+n} is not true for a general (n,m)-function. Summing the preceding identity ∑_v ACF(u,v) = 2^m DDT(u,0) over all u yields 2^m ∑_{z∈Im F}|F^{-1}(z)|^2, which equals 2^{m+n} only when every fiber of F has size 1, i.e., when F is a permutation. For the constant function F: F2 → F2, every ACF entry is 2 and the total sum is 8, not 4. Please restrict the identity to permutations or remove it; this error does not affect the proofs of Theorem 1 or Proposition 4.
- [Section 3-A, Proposition 2] In the first displayed formula, the term ACF(u,v) inside the sum should be ACF(ω,v); the proof correctly uses ACF(ω,v). Please correct the statement.
- [Section 3-F, Propositions 7 and 8] The formulas ACF(u,v) = -2^{2r_v-n-1} W_{\tilde f_v}(u) and ACF(u,v) = -W_{γ_u}(v) are derived under the assumption u≠0 and v≠0, respectively, using the fact that the total Walsh sum is zero. For u=0 or v=0 the formulas fail. Since the autocorrelation spectrum excludes u=0 and v=0, please state the restriction explicitly.
- [Section 3-D, Proposition 6] The exponent in the statement appears as 2^{n+d(u,v)/2}; from the proof it should be 2^{(n+d(u,v))/2}. Also, the definition of d(u,v) should clarify that the nonzero case corresponds to the derivative being identically zero on the subspace, and the role of the constant c should be specified precisely.
- [Section 4-A, Theorem 3] The proof states that φ_v is linear on ker(L_v) 'by direct computations'. This is a key step, and the paper should either provide the computation or give a reference, so that the reader can verify the linearity claim.
- [Section 3-D, Proposition 5] The cited divisibility theorem for Walsh transforms is stated as 'degree d ... divisible by 2^{⌈ n/(d−1) ⌉}', but the subsequent application uses 2^{⌈ (n−1)/(d−1) ⌉} for a function of degree at most d−1, which suggests the exponent in the theorem statement should be corrected (likely 2^{⌈ n/d ⌉}). Please check the original source and fix the typo.
- [Table II] The notation for the spectra (e.g., '-860') is not defined; please clarify that the subscripts indicate multiplicities, or reformat the table for readability.
- [Section 3-E] The exhaustive claim for optimal 4-bit S-boxes depends on the completeness of the Leander–Poschmann classification [27]; the paper should explicitly state that the completeness is cited rather than re-derived, and that the spectra were computed from the listed representatives.
Circularity Check
No circularity: the DLCT-autocorrelation identity follows from the definitions, the bounds are derived, and Table II rests on an external classification rather than on the paper's own claims.
full rationale
The paper's central mathematical content is definitional and derivational, not circular. Proposition 1 proves DLCT_F(u,v) = (1/2)AC_F(u,v) by expanding the count in Definition 1 as #M0 - #M1, which is exactly the autocorrelation sum; the DLCT and the autocorrelation have independent definitions, so this is a genuine equivalence rather than a fitted input or a renaming. Proposition 2 is the standard Fourier relation between squared Walsh coefficients and autocorrelation, and Proposition 3 gives the Fourier relation between a DDT row and the autocorrelation row together with its inverse; these are Parseval/Fourier identities. Theorem 1 follows from Proposition 4 by a Cauchy-Schwarz argument on row sums of squared DDT entries; no parameter is fitted and no target value is imported. The divisibility results are proved from McEliece's Walsh-divisibility theorem, and the equivalence-invariance statements are computed directly. Table II's exhaustiveness inherits the external Leander-Poschmann classification of optimal 4-bit S-boxes; the paper computes autocorrelation spectra for the 16 representatives and does not claim to re-prove the completeness of that classification, so this is an independent external dependency, not a self-supporting premise. The note that the paper merges [12] and [28] is an authorship disclosure, not a load-bearing citation. No step defines an input in terms of an output, relabels a fitted parameter as a prediction, or justifies a conclusion solely by a self-citation. One non-circular correctness defect should be flagged: in Proposition 3 (Section 3-B), after the correct identity sum_v ACF(u,v) = 2^m DDT_F(u,0), the paper infers sum_{u,v} ACF(u,v) = 2^{m+n}. This inference is false for non-permutations; for example, the constant (1,1)-function has total sum 8 while 2^{m+n} = 4. The error is not used in the proofs of Proposition 1 or Theorem 1, but Proposition 3 as stated needs a permutation restriction or removal of the total-sum claim. This is a correctness issue, not circularity, and does not raise the circularity score.
Assumptions & free parameters
assumptions (6)
- standard math McEliece's divisibility theorem for Walsh coefficients of Boolean functions of algebraic degree d: all values divisible by 2^{ceil(n/(d-1))}.
- domain assumption Leander-Poschmann classification: every optimal 4-bit S-box with differential uniformity and nonlinearity 4 is affine-equivalent to one of 16 representatives.
- standard math Weil bound for exponential sums over finite fields applies to the exponential sums arising from Kasami derivatives.
- standard math Known autocorrelation spectrum of the inverse mapping x -> x^{-1} in terms of Kloosterman sums.
- standard math Support characterization of the Walsh spectrum of Kasami exponents, attributed to Dillon.
- domain assumption Every quadratic APN permutation is crooked and the hyperplanes Im(D_uF) are distinct.
Cite this review
Pith. "Pith review of On the Differential-Linear Connectivity Table of Vectorial Boolean Functions." pith.science (2026). https://pith.science/paper/VLKLRJ5D
@misc{pith2026190807445,
author = {Pith},
title = {Pith review of: On the Differential-Linear Connectivity Table of Vectorial Boolean Functions},
year = {2026},
howpublished = {\url{https://pith.science/paper/VLKLRJ5D}},
note = {Machine review of arXiv:1908.07445}
}
abstract
Vectorial Boolean functions are crucial building-blocks in symmetric ciphers. Different known attacks on block ciphers have resulted in diverse cryptographic criteria for vectorial Boolean functions, such as differential uniformity and nonlinearity. Very recently, Bar-On et al. introduced at Eurocrypt'19 a new tool, called the differential-linear connectivity table (DLCT), which allows for taking into account the dependency between the two subciphers $E_0$ and $E_1$ involved in differential-linear attacks. This new notion leads to significant improvements of differential-linear attacks on several ciphers. This paper presents a theoretical characterization of the DLCT of vectorial Boolean functions and also investigates this new criterion for some families of functions with specific forms. More precisely, we firstly reveal the connection between the DLCT and the autocorrelation of vectorial Boolean functions, we characterize properties of the DLCT by means of the Walsh transform of the function and of its differential distribution table, and we present generic bounds on the highest magnitude occurring in the DLCT of vectorial Boolean functions, which coincides (up to a factor~\(2\)) with the well-established notion of absolute indicator. Next, we investigate the invariance property of the DLCT of vectorial Boolean functions under the affine, extended-affine, and Carlet-Charpin-Zinoviev (CCZ) equivalence and exhaust the DLCT spectra of optimal $4$-bit S-boxes under affine equivalence. Furthermore, we study the DLCT of APN, plateaued and AB functions and establish its connection with other cryptographic criteria. Finally, we investigate the DLCT and the absolute indicator of some specific polynomials with optimal or low differential uniformity, including monomials, cubic functions, quadratic functions and inverses of quadratic permutations.
Reference graph
Works this paper leans on
-
[1]
DLCT: A new tool for differential-linear cryptanal ysis
Achiya Bar-On, Orr Dunkelman, Nathan Keller, and Ariel W eizman. DLCT: A new tool for differential-linear cryptanal ysis. pages 313–342, 2019
work page 2019
-
[2]
T.D. Bending and D. Fon-Der-Flaass. Crooked functions, bent functions, and distance regular graphs. The Electronic Journal of Combinatorics , 5, 1998
work page 1998
-
[3]
On almost perfect nonlinear functions ove r Fn 2
Thierry Berger, Anne Canteaut, Pascale Charpin, and Yan n Laigle-Chapuy. On almost perfect nonlinear functions ove r Fn 2 . IEEE Transactions on Information Theory , 52(9):4160–4170, 2006
work page 2006
-
[4]
Fides: Lightweight auth enticated cipher with side-channel resistance for constrained hardw are
Begül Bilgin, Andrey Bogdanov, Miroslav Kneževi ´c, Florian Mendel, and Qingju Wang. Fides: Lightweight auth enticated cipher with side-channel resistance for constrained hardw are. pages 142–158, 2013
work page 2013
-
[5]
New links between diff erential and linear cryptanalysis
Céline Blondeau and Kaisa Nyberg. New links between diff erential and linear cryptanalysis. pages 388–404, 2013
work page 2013
-
[6]
On the boomerang unif ormity of cryptographic sboxes
Christina Boura and Anne Canteaut. On the boomerang unif ormity of cryptographic sboxes. 2018(3):290–310, 2018
work page 2018
-
[7]
A highly nonlinear diff erentially 4 uniform power mapping that permutes fields of ev en degree
Carl Bracken and Gregor Leander. A highly nonlinear diff erentially 4 uniform power mapping that permutes fields of ev en degree. Finite Fields and Their Applications , 16(4):231–242, July 2010
work page 2010
-
[8]
Construction and Analysis of Cryptographic Functions
Lilya Budaghyan. Construction and Analysis of Cryptographic Functions . New Y ork, NY , USA: Springer-V erlag, 2014
work page 2014
Show all 44 references
-
[9]
New class es of almost bent and almost perfect nonlinear polynomials
Lilya Budaghyan, Claude Carlet, and Alex Pott. New class es of almost bent and almost perfect nonlinear polynomials. IEEE Transactions on Information Theory , 52(3):1141–1152, March 2006
2006
-
[10]
Decomposing bent fu nctions
Anne Canteaut and Pascale Charpin. Decomposing bent fu nctions. IEEE Transactions on Information Theory , 49(8):2004–2019, Aug. 2003
2004
-
[11]
Kyureghya n
Anne Canteaut, Pascale Charpin, and Gohar M. Kyureghya n. A new class of monomial bent functions. Finite Fields and Their Applications , 14(1):221–241, Jan. 2008. 27
2008
-
[12]
Obs ervations on the DLCT and absolute indicators
Anne Canteaut, Lukas Kölsch, and Friedrich Wiemer. Obs ervations on the DLCT and absolute indicators. Cryptology ePrint Archive, https://eprint.iacr .org/2019/848.pdf, 2019
2019
-
[13]
Recursive lower bounds on the nonlinear ity profile of boolean functions and their applications
Claude Carlet. Recursive lower bounds on the nonlinear ity profile of boolean functions and their applications. IEEE Transactions on Information Theory , 54(3):1262–1272, March 2008
2008
-
[14]
Boolean functions for cryptography and error-correcting codes
Claude Carlet. Boolean functions for cryptography and error-correcting codes. In Yves Crama and Peter L. Hammer, e ditors, Boolean Models and Methods in Mathematics, Computer Scienc e, and Engineering , pages 257–397. Cambridge University Press, 2010
2010
-
[15]
C odes, bent functions and permutations suitable for DES-lik e cryptosystems
Claude Carlet, Pascale Charpin, and Victor Zinoviev. C odes, bent functions and permutations suitable for DES-lik e cryptosystems. Designs, Codes and Cryptography , 15(2):125–156, 1998
1998
-
[16]
Links between diff erential and linear cryptanalysis
Florent Chabaud and Serge V audenay. Links between diff erential and linear cryptanalysis. pages 356–365, 1995
1995
-
[17]
P ropagation characteristics of x ↦→x− 1 and Kloosterman sums
Pascale Charpin, Tor Helleseth, and Victor Zinoviev. P ropagation characteristics of x ↦→x− 1 and Kloosterman sums. Finite Fields and Their Applications , 13(2):366–381, April 2007
2007
-
[18]
Boomerang connectivity table: A new cryptanalysis t ool
Carlos Cid, Tao Huang, Thomas Peyrin, Y u Sasaki, and Lin g Song. Boomerang connectivity table: A new cryptanalysis t ool. pages 683–714, 2018
2018
-
[19]
John F. Dillon. Multiplicative difference sets via add itive characters. Designs, Codes and Cryptography , 17(1-3):225–235, 1999
1999
-
[20]
Construction of Bent functions and bal anced Boolean functions with high nonlinearity
Hans Dobbertin. Construction of Bent functions and bal anced Boolean functions with high nonlinearity. pages 61–7 4, 1995
1995
-
[21]
Keskar, and Subha moy Maitra
Sugata Gangopadhyay, Pradipkumar H. Keskar, and Subha moy Maitra. Patterson-Wiedemann construction revisited. Discrete Mathematics, 306(14):1540–1556, 2006
2006
-
[22]
Additive autocorrelat ion of resilient Boolean functions
Guang Gong and Khoongming Khoo. Additive autocorrelat ion of resilient Boolean functions. pages 275–290, 2004
2004
-
[23]
Correction to the paper: Patterson-Wied emann construction revisited
Selçuk Kavut. Correction to the paper: Patterson-Wied emann construction revisited. Discrete Applied Mathematics , 202:185– 187, 2016
2016
-
[24]
Construc tion and search of balanced boolean functions on even number of variables towards excellent autocorrelation profile
Selçuk Kavut, Subhamoy Maitra, and Deng Tang. Construc tion and search of balanced boolean functions on even number of variables towards excellent autocorrelation profile. Des. Codes Cryptogrography , 87(2–3):261–276, 2019
2019
-
[25]
Selçuk Kavut, Subhamoy Maitra, and Melek D. Yücel. Sear ch for boolean functions with excellent profiles in the rotat ion symmetric class. IEEE Trans. Information Theory , 53(5):1743–1751, 2007
2007
-
[26]
Langford and Martin E
Susan K. Langford and Martin E. Hellman. Differential- linear cryptanalysis. pages 17–25, 1994
1994
-
[27]
On the classificatio n of 4 bit S-boxes
Gregor Leander and Axel Poschmann. On the classificatio n of 4 bit S-boxes. In Arithmetic of Finite Fields , pages 159–176. Springer Berlin Heidelberg, 2007
2007
-
[28]
On th e differential-linear connectivity table of vectorial boo lean functions
Kangquan Li, Chunlei Li, Chao Li, and Longjiang Qu. On th e differential-linear connectivity table of vectorial boo lean functions. CoRR., http://arxiv.org/abs/1907.05986, 2019
1907 arXiv
-
[29]
New res ults about the boomerang uniformity of permutation polynom ials
Kangquan Li, Longjiang Qu, Bing Sun, and Chao Li. New res ults about the boomerang uniformity of permutation polynom ials. IEEE Transactions on Information Theory , 2019
2019
-
[30]
Modifications of Pat terson-Wiedemann functions for cryptographic applicatio ns
Subhamoy Maitra and Palash Sarkar. Modifications of Pat terson-Wiedemann functions for cryptographic applicatio ns. IEEE Trans. Information Theory , 48(1):278–284, 2002
2002
-
[31]
James L. Massey. SAFER K-64: A byte-oriented block-cip hering algorithm. pages 1–17, 1994
1994
-
[32]
McEliece
Robert J. McEliece. Weight congruences for p-ary cyclic codes. Discrete Mathematics , 3(1-3):177–192, 1972
1972
-
[33]
Bent Functions: Fundamentals and Results
Sihem Mesnager. Bent Functions: Fundamentals and Results . Springer International Publishing, 2016
2016
-
[34]
On t he boomerang uniformity of (quadratic) permutations over F2n
Sihem Mesnager, Chunming Tang, and Maosheng Xiong. On t he boomerang uniformity of (quadratic) permutations over F2n . CoRR, 2019
2019
-
[35]
Differentially uniform mappings for cry ptography
Kaisa Nyberg. Differentially uniform mappings for cry ptography. pages 55–64, 1994
1994
-
[36]
S-boxes and round functions with control lable linearity and differential uniformity
Kaisa Nyberg. S-boxes and round functions with control lable linearity and differential uniformity. pages 111–13 0, 1995
1995
-
[37]
Oscar S. Rothaus. On “bent” functions. Journal of Combinatorial Theory, Series A , 20(3):300–305, May 1976
1976
-
[38]
The block cipher SC2000
Takeshi Shimoyama, Hitoshi Yanami, Kazuhiro Y okoyama , Masahiko Takenaka, Kouichi Itoh, Jun Yajima, Naoya Torii, and Hidema Tanaka. The block cipher SC2000. pages 312–327, 2002
2002
-
[39]
Boomerang connectiv ity table revisited
Ling Song, Xianrui Qin, and Lei Hu. Boomerang connectiv ity table revisited. 2019(1):118–141, 2019. 28
2019
-
[40]
The lower bound on the sec ond-order nonlinearity of a class of boolean functions with high nonlinearity
Guanghong Sun and Chuankun Wu. The lower bound on the sec ond-order nonlinearity of a class of boolean functions with high nonlinearity. Applicable Algebra in Engineering, Communication and Comp uting, 22(1):37–45, Dec. 2009
2009
-
[41]
Construction of n-variable ( n ≡ 2 mod 4 ) balanced boolean functions with maximum absolute value in autocorrelation spectra < 2n/ 2
Deng Tang and Subhamoy Maitra. Construction of n-variable ( n ≡ 2 mod 4 ) balanced boolean functions with maximum absolute value in autocorrelation spectra < 2n/ 2. IEEE Trans. Information Theory , 64(1):393–402, 2018
2018
-
[42]
Bent Functions: Results and Applications to Cryptography
Natalia Tokareva. Bent Functions: Results and Applications to Cryptography . Academic Press, 2015
2015
-
[43]
GAC — the criterion for global avalanche characteristics of cryptographic functi ons
Xian-Mo Zhang and Y uliang Zheng. GAC — the criterion for global avalanche characteristics of cryptographic functi ons. In J.UCS The Journal of Universal Computer Science , pages 320–337. Springer Berlin Heidelberg, 1996
1996
-
[44]
Relatin g differential distribution tables to other properties of o f substitution boxes
Xian-Mo Zhang, Y uliang Zheng, and Hideki Imai. Relatin g differential distribution tables to other properties of o f substitution boxes. Designs, Codes and Cryptography , 19(1):45–63, 2000
2000
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.