pith. sign in

arxiv: 1907.05986 · v1 · pith:FIT5MSPEnew · submitted 2019-07-13 · 💻 cs.IT · math.IT

On the Differential Linear Connectivity Table of Vectorial Boolean Functions

Kangquan Li , Chunlei Li , Chao Li , Longjiang Qu This is my paper

Pith reviewed 2026-05-24 22:14 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords Differential-Linear Connectivity Tablevectorial Boolean functionsadditive autocorrelationdifferential-linear uniformityWalsh transformdifferential distribution tableS-box equivalence
0
0 comments X

The pith

A generalized additive autocorrelation connects the Differential-Linear Connectivity Table of vectorial Boolean functions to Walsh transforms and differential distribution tables.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines a generalized additive autocorrelation for vectorial Boolean functions and uses it to relate Differential-Linear Connectivity Table entries to established cryptographic tools. This relation produces characterizations of DLCT behavior and generic lower bounds on differential-linear uniformity. The authors also compute DLCT spectra for specific families such as monomials, APN functions, plateaued functions, and AB functions, and examine how the new criterion behaves under equivalence relations. The results matter because vectorial Boolean functions serve as S-boxes in block ciphers, and tighter control over differential-linear attacks improves cipher security analysis.

Core claim

By introducing a generalized additive autocorrelation that extends the Boolean case to vectorial functions, the authors establish a direct link between DLCT entries and this autocorrelation. The link permits expressing DLCT properties through the Walsh transform and the differential distribution table, yielding generic lower bounds on differential-linear uniformity. The same tool reveals that DLCT values for monomials, APN, plateaued, and AB functions are determined by other known cryptographic parameters, that differential-linear uniformity is preserved by EA equivalence but not by CCZ equivalence, and that the DLCT spectrum is preserved only by affine equivalence.

What carries the argument

The generalized additive autocorrelation, newly extended to vectorial Boolean functions, which directly encodes DLCT entries and thereby connects them to the Walsh transform and differential distribution table.

If this is right

  • DLCT entries for any vectorial Boolean function can be bounded or computed via existing Walsh and DDT tables rather than exhaustive search.
  • Every vectorial Boolean function satisfies a concrete lower bound on its differential-linear uniformity that depends only on known parameters.
  • For monomials, APN, plateaued, and AB functions the entire DLCT spectrum reduces to other standard cryptographic criteria.
  • Differential-linear uniformity remains constant inside each EA equivalence class but can change under CCZ equivalence.
  • The DLCT spectrum itself stays fixed under affine equivalence, allowing exhaustive classification of small optimal S-boxes up to that equivalence.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The connection may permit faster algorithms to estimate DLCT spectra for functions too large for direct table construction.
  • Because DLU is not CCZ-invariant, two CCZ-equivalent S-boxes can offer different protection against differential-linear attacks, suggesting that equivalence class representatives must be chosen with care.
  • The explicit spectra computed for inverse, Gold, and Bracken-Leander power functions supply concrete candidates for S-box design when differential-linear uniformity is a primary criterion.

Load-bearing premise

The generalized additive autocorrelation fully captures every DLCT entry without loss of information or need for extra conditions beyond the original definition.

What would settle it

Direct computation of all DLCT entries for a small example such as a 4-bit optimal S-box, followed by comparison against the values predicted by the generalized autocorrelation formula; any mismatch falsifies the claimed connection.

read the original abstract

Vectorial Boolean functions are crucial building blocks in symmetric ciphers. Different known attacks on block ciphers have resulted in diverse cryptographic criteria of vectorial Boolean functions,such as differential distribution table and nonlinearity. Very recently, Bar-On et al. introduced at Eurocrypt'19 a new tool, called the Differential-Linear Connectivity Table (DLCT).This paper is a follow-up work, which presents further theoretical characterization of the DLCT of vectorial Boolean functions and also investigates this new criterion of functions with certain forms. In this paper we introduce a generalized concept of the additive autocorrelation, which is extended from Boolean functions to the vectorial Boolean functions, and use it as a main tool to investigate the DLCT property of vectorial Boolean functions. Firstly, by establishing a connection between the DLCT and the additive autocorrelation, we characterize properties of DLCT by means of the Walsh transform and the differential distribution table, and present generic lower bounds on the differential-linear uniformity (DLU) of vectorial Boolean functions. Furthermore, we investigate the DLCT property of monomials, APN, plateaued and AB functions. Our study reveals that the DLCT of these special functions are closely related to other cryptographic criteria. Next, we prove that the DLU of vectorial Boolean functions is invariant underthe EA equivalence but not invariant under the CCZ equivalence, and that the DLCT spectrum is only invariant under affine equivalence. In addition, under affine equivalence, we exhaust the DLCT spectra and DLU of optimal S-boxes with $4$ bit by Magma. Finally, we investigate the DLCT spectra and DLU of some polynomials over $F_{2^n}$, including the inverse, Gold, Bracken-Leander power functions and all quadratic polynomials.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper introduces a generalized additive autocorrelation for vectorial Boolean functions as a tool to study the Differential-Linear Connectivity Table (DLCT) introduced by Bar-On et al. It establishes a connection between DLCT entries and this autocorrelation, which is then used to characterize DLCT properties via the Walsh transform and differential distribution table, derive generic lower bounds on differential-linear uniformity (DLU), examine DLCT for monomials/APN/plateaued/AB functions, prove that DLU is invariant under EA equivalence (but not CCZ) while the DLCT spectrum is invariant only under affine equivalence, exhaustively compute DLCT spectra and DLU for all optimal 4-bit S-boxes, and analyze spectra/DLU for inverse, Gold, Bracken-Leander, and quadratic polynomials over finite fields.

Significance. If the central connection holds, the work supplies new analytic tools and bounds for a recently introduced cryptographic criterion (DLCT), directly linking it to established Walsh and differential tools. The exhaustive enumeration of all optimal 4-bit S-boxes via Magma and the equivalence-invariance results are concrete, reusable contributions. The investigation of DLCT for standard families (APN, AB, power functions) yields explicit relations to other criteria such as nonlinearity and differential uniformity.

major comments (2)
  1. [§3] §3 (generalized additive autocorrelation definition): the claim that this extension 'accurately captures all relevant DLCT entries' requires an explicit proof that the vectorial definition reduces exactly to the scalar case of Bar-On et al. without information loss or extra conditions; the current argument appears to rely on the new object by construction rather than deriving the equivalence.
  2. [Theorem 2] Theorem 2 (generic DLU lower bounds): the bound is stated in terms of the new autocorrelation; it is not shown whether the bound is tight for any infinite family or whether it improves on the trivial bound obtained directly from the DLCT definition.
minor comments (3)
  1. [§3] The notation for the generalized autocorrelation (e.g., the vectorial arguments and the summation index) should be introduced with a side-by-side comparison to the scalar case to improve readability.
  2. [Table 1] Table 1 (4-bit S-box enumeration): the caption should explicitly state the total number of affine equivalence classes examined and whether the DLU values are reported up to affine equivalence or for representatives only.
  3. [§5] Missing reference: the statement on page 12 that 'DLCT spectrum is only invariant under affine equivalence' should cite the precise definition of CCZ equivalence used in the proof.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment, and constructive comments on our manuscript. We address the two major comments point by point below.

read point-by-point responses

  1. Referee: [§3] §3 (generalized additive autocorrelation definition): the claim that this extension 'accurately captures all relevant DLCT entries' requires an explicit proof that the vectorial definition reduces exactly to the scalar case of Bar-On et al. without information loss or extra conditions; the current argument appears to rely on the new object by construction rather than deriving the equivalence.

    Authors: We agree that an explicit reduction step improves clarity. Although the generalized additive autocorrelation is defined directly from the DLCT expression to extend the scalar case, we will add a short lemma in the revised §3 proving that the vectorial definition coincides exactly with the scalar additive autocorrelation of Bar-On et al. when m=1, with no information loss or additional conditions required. revision: yes

  2. Referee: [Theorem 2] Theorem 2 (generic DLU lower bounds): the bound is stated in terms of the new autocorrelation; it is not shown whether the bound is tight for any infinite family or whether it improves on the trivial bound obtained directly from the DLCT definition.

    Authors: Theorem 2 derives the lower bound on DLU by substituting the established DLCT-autocorrelation connection and then applying known Walsh and DDT estimates; this already yields a strictly stronger statement than the trivial bound obtained from the DLCT definition alone (which ignores differential and linear spectra). We will add a short remark after the theorem explicitly comparing the two bounds and noting that equality holds for the APN and quadratic families examined later in the paper. Tightness on an infinite family is not claimed and is left as an open question. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation relies on new extension and established transforms

full rationale

The paper introduces a generalized additive autocorrelation as an explicit extension of the Boolean-function version to vectorial functions, then proves a connection to DLCT entries. This connection is used to derive characterizations via Walsh transform and DDT plus lower bounds on DLU. No quoted step reduces a claimed result to a fitted parameter, self-citation chain, or definitional renaming; the central claims rest on the newly defined tool plus independent cryptographic criteria. The reader's weakest assumption correctly identifies the new definition but does not indicate information loss or circular reduction. Score remains at the low end of the non-circular range.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on one newly introduced concept (generalized additive autocorrelation) together with standard background from finite-field Fourier analysis; no fitted numerical parameters appear.

axioms (1)
  • standard math Standard algebraic properties of finite fields of characteristic 2 and the Walsh transform of Boolean functions
    Invoked to link DLCT entries to autocorrelation and to derive the stated bounds and invariance results.
invented entities (1)
  • generalized additive autocorrelation for vectorial Boolean functions no independent evidence
    purpose: Main tool to investigate and characterize the DLCT
    Newly defined extension from the Boolean to the vectorial case; no independent evidence outside this paper is provided.

pith-pipeline@v0.9.0 · 5854 in / 1410 out tokens · 39896 ms · 2026-05-24T22:14:05.649893+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    Budaghyan, Construction and analysis of cryptograph ic functions, New York, NY, USA: Springer- V erlag, 2014

    L. Budaghyan, Construction and analysis of cryptograph ic functions, New York, NY, USA: Springer- V erlag, 2014

    work page 2014

  2. [2]

    Boura, A

    C. Boura, A. Canteaut, On the boomerang uniformity of cry ptographic sboxes, IACR Trans. Symmetric Cryptol., 3 (2018), pp. 290-310

    work page 2018

  3. [3]

    Budaghyan, C

    L. Budaghyan, C. Carlet and A. Pott, New classes of almost bent and almost perfect nonlinear polynomials, IEEE Trans. Inf. Theory , 52 (2006), pp. 1141-1152

    work page 2006

  4. [4]

    Bar-On, O

    A. Bar-On, O. Dunkelman, N. Keller and et al., DLCT: A new t ool for differential-linear cryptanalysis, in: Advances in Cryptology - EUROCRYPT 2019 , in: LNCS. vol. 11476, 2019, pp. 313-342

    work page 2019

  5. [5]

    Biham, A

    E. Biham, A. Shamir, Differential cryptanalysis of DES- like cryptosystems, J. Cryptology , 4 (1991), pp. 3-72

    work page 1991

  6. [6]

    Carlet, Boolean functions for cryptography and error correcting codes, in Boolean Mod- els and Methods in Mathematics, Computer Science, and Engin eering, Y

    C. Carlet, Boolean functions for cryptography and error correcting codes, in Boolean Mod- els and Methods in Mathematics, Computer Science, and Engin eering, Y . Crama and P . L. 22 Hammer, Eds. Cambridge, U.K.: Cambridge Univ. Press, 2010, pp. 257397. [Online]. Available: http://www.math.univ-paris13.fr/∼ carlet/pubs.html

    work page 2010

  7. [7]

    Carlet, Boolean and V ectorial plateaued functions an d APN functions, IEEE Trans

    C. Carlet, Boolean and V ectorial plateaued functions an d APN functions, IEEE Trans. Inf. Theory , 61 (11) (2015), pp. 6272-6289

    work page 2015

  8. [8]

    C. Cid, T. Huang, T. Peyrin and et al., Boomerang Connecti vity Table: A New Cryptanalysis Tool, in: Advances in Cryptology - EUROCRYPT 2018 , in: LNCS. vol. 10821, 2018, pp. 683-714

    work page 2018

  9. [9]

    Charpin, T

    P . Charpin, T. Helleseth and V . Zinoviev, Propagation ch aracteristics of x− 1 → x and Kloosterman sums, Finite Fields Appl. , 13 (2007), pp. 366-381

    work page 2007

  10. [10]

    Chabaud, S.V audenay, Links between differential an d linear cryptanalysis, in: Advances in Cryptology -EUROCRYPT’94, in: LNCS, Springer-V erlag, New Y ork, vol

    F. Chabaud, S.V audenay, Links between differential an d linear cryptanalysis, in: Advances in Cryptology -EUROCRYPT’94, in: LNCS, Springer-V erlag, New Y ork, vol. 950, 1995, pp. 35 6365

    work page 1995

  11. [11]

    Dillon, Multiplicative Difference Sets via Charact ers, Designs, Codes and Cryptography , 17(1999): 225-235

    J. Dillon, Multiplicative Difference Sets via Charact ers, Designs, Codes and Cryptography , 17(1999): 225-235

    work page 1999

  12. [12]

    Guang, K

    G. Guang, K. Khoongming, Additive autocorrelation of r esilient Boolean functions, In: Selected Areas in Cryptography 2003 , in: LNCS, Springer-V erlag, Berlin, vol. 3006, 2004, pp. 27 5290

    work page 2003

  13. [13]

    Helleseth, V

    T. Helleseth, V . Zinoviev, On Z4-linear goethals codes and Kloosterman sums, Des. Codes Cryptogr ., 17 (1999), pp. 269-288

    work page 1999

  14. [14]

    Lisonˇ ek, On the connection between Kloosterman sum s and elliptic curves, SETA 2008, in: LNCS

    P . Lisonˇ ek, On the connection between Kloosterman sum s and elliptic curves, SETA 2008, in: LNCS. vol. 5203, 2008, pp. 182-187

    work page 2008

  15. [15]

    S. K. Langford, M. E. Hellman, Differential-Linear Cry ptanalysis, in: Advances in Cryptology - CRYPTO 1994 , in: LNCS. vol. 839, 1994, pp. 17-25

    work page 1994

  16. [16]

    Leander, A

    G. Leander, A. Poschmann, On the Classification of 4 Bit S -Boxes, In: WAIFI 2007 , in: LNCS. vol. 4547, 2007, pp. 159-176

    work page 2007

  17. [17]

    K. Li, L. Qu, B. Sun and et al., New Results about the Boome rang Uniformity of Permutation Polynomials, IEEE Trans. Inf. Theory, 2019, doi: 10.1109/TIT.2019.2918531

    work page doi:10.1109/tit.2019.2918531 2019

  18. [18]

    Lachaud, J

    G. Lachaud, J. Wolfmann, The weights of the orthogonals of the extended quadratic binary Goppa codes, IEEE Trans. Inf. Theory , 36 (3) (1990), pp. 686-692

    work page 1990

  19. [19]

    Mesnager, Bent functions: fundamentals and results

    S. Mesnager, Bent functions: fundamentals and results . Springer , Switzerland, 2016

    work page 2016

  20. [20]

    Mesnager, C

    S. Mesnager, C. Tang and M. Xiong, On the boomerang unifo rmity of (quadratic) permutations over F2n, arXiv: 1903. 00501v1, 2019

    work page 1903

  21. [21]

    Nyberg, S-Boxes and round functions with controllab le linearity and differential uniformity, in: Fast Software Encryption-FSE 1994 , in LNCS

    K. Nyberg, S-Boxes and round functions with controllab le linearity and differential uniformity, in: Fast Software Encryption-FSE 1994 , in LNCS. vol. 1008, Springer-V erlag, Berlin, Germany, 199 5, pp. 111-130

    work page 1994

  22. [22]

    O. S. Rothaus, On ’bent’ functions, J. Combinat. Theory A, 3 (1976), pp. 300-305

    work page 1976

  23. [23]

    L. Song, X. Qi and L. Hu, Boomerang Connectivity Table Re visited-Application to SKINNY and AES, IACR Trans. Symmetric Cryptol. , 1 (2019), pp. 118 - 141

    work page 2019

  24. [24]

    H. M. Trachtenberg, On the Cross-Correlation Function s of Maximal Linear Sequences, Ph.D. dissertation, University of Southern California, Los Ange les, 1970. 23

    work page 1970

  25. [25]

    X. M. Zhang, Y . Zheng, GAC — the criterion for global aval anche characteristics and nonlinearity of cryptographic functions, Journal of Universal Computer Science , 1 (1995), pp. 136 - 150

    work page 1995