Pith. sign in

REVIEW 3 major objections 3 minor 22 references

Feedback linearly extended discrete functions

T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A linear-feedback extension turns any nonlinear function into a bijection, and the solvability of its difference and linear-form equations reduces to the smaller function's equations.

desk verdict The finite-difference half of this paper is plausible, but the linear-form characterization is broken because Lemma 3 is false; the paper should be revised before the linear-form claims are used. read the letter →

arxiv 1908.09422 v5 pith:KMSWS4XG submitted 2019-08-26 cs.CR cs.DM

Claude Gravel , Daniel Panario This is my paper · ORCID
classification cs.CRcs.DM MSC 12E2015A0315B1039A0639A1294A6094B05
keywords vectorspacesoverfinitefieldsdimensionalFredholmalternativetheoremfeedbackshiftregisterblockcipherdifferentialcryptanalysislinearpseudo-randomnessextensionoffunctions
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper studies a recipe for building a bijection $F:\mathbb{F}^n\to\mathbb{F}^n$ from a possibly non-bijective function $f$ on a smaller space, through $F(x)=T(x+B^t f(Ax))$ with matrices satisfying $AB^t=0$. It claims that the two equation families used in cryptanalysis—finite differences $F(x+\alpha)-F(x)=\beta$ and linear forms $\alpha\cdot x-\beta\cdot F(x)=0$—are solvable for $F$ exactly when the same kind of equation is solvable for $f$, with parameters mapped by explicit linear formulas (Lemmas 2 and 3). For compositions of several extensions, the paper proves that beyond a threshold number of rounds the set of feasible parameter pairs has size at most $p^{t_0}$, where $p$ is the field characteristic and $t_0$ is the codimension of an intersection of kernels; when that intersection is trivial, only $(\alpha,\beta)=(0,0)$ remains. Since Feistel ciphers, FOX, and generalized Feistel networks are instances of the construction, the result offers a common lens for differential and linear analyses of those ciphers.

What carries the argument

The central object is the linear extension $F(x)=T(x+B^t f(Ax))$ over a finite field, with $A$ ($m\times n$) and $B$ ($(n-m)\times n$) full-rank matrices satisfying $AB^t=0$, and $T\in\mathrm{GL}(n,\mathbb{F})$. The orthogonality $AB^t=0$ is what makes $F$ invertible and lets the proofs cancel the non-linear term by multiplying by $A T^{-1}$ or project it away with the canonical right projection $R_B$, the matrix for which $M R_M=I$ when $M$ is in standard form; this is the mechanism that reduces equations for $F$ to equations for $f$. The composition results are carried by the kernel intersections $\bigcap_{j=0}^{\ell-1}T^j\ker A$ and $\bigcap_{j=0}^{\ell-1}(T^t)^{-j}\ker B$, whose codimension grows by at most $m$ per step (Lemma 4), yielding the stabilization bound $p^{t_0}$.

What would settle it

Over $\mathrm{GF}(3)$, set $A=[1\ 0]$, $B=[0\ 1]$, $T=I$, and $f(u)=u^2+1$, and let $\alpha=(1,0)$, $\beta=(0,1)$. The equation $\alpha\cdot x-\beta\cdot F(x)=0$ becomes $x_0-(x_1+f(x_0))=0$, which has solution $x=(0,2)$; yet $\alpha^t-\beta^t T=(1,2)$ is not in the row space of $A$ and $\mathrm{im}(f)\cap\ker B^t=\emptyset$, contradicting Lemma 3's claim that no solution exists in this case.

Watch

Extended reading notes

Core claim

The paper establishes that $F$ is bijective for every choice of $f$, with the explicit inverse $G(y)=T^{-1}y-B^t f(A T^{-1}y)$, and gives complete parameter-space characterizations: for the difference equation, solvability for $(\alpha,\beta)$ is determined by whether $T^{-1}\beta-\alpha$ lies in the row space of $B$, and when it does the solutions are exactly the solutions of $f(u+a)-f(u)=b$ with $a=A\alpha$ and $b=R_B^t(T^{-1}\beta-\alpha)$ (Lemma 2). For the linear-form equation, the analogous reduction is controlled by whether $\alpha^t-\beta^t T$ lies in the row space of $A$, with the smaller equation $a\cdot u-b\cdot f(u)=0$ under the same parameter mapping (Lemma 3). For a composition $G_\ell=F_\ell\circ\cdots\circ F_1$, the paper recurses by annihilating the non-linear term with $A T^{-1}$ (difference case) or requiring $\beta^t T^j\in\operatorname{rowsp}A$ (linear-form case), which leads to the kernel intersections $\Theta=\bigcap_{j=0}^{\ell-1}T^j\ker A$ and $\Theta'=\bigcap_{j=0}^{\ell-1}(T^t)^{-j}\ker B$; Lemma 4 bounds their codimension by $m\ell$, and Corollaries 1 and 2 conclude that for $t\ge t_0=\dim\Theta/m$ the feasible parameter pairs number at most $p^{t_0}$.

Load-bearing premise

Lemma 3's 'no solution' branch assumes that when $\alpha^t-\beta^t T$ lies outside the row space of $A$, the non-linear contribution $\beta^t T B^t f(Ax)$ can never cancel the leftover linear term, and the paper states no condition that rules out such cancellations.

Editorial extensions

If this is right

  • For any $f$, the extension $F$ is a bijection and its inverse costs one evaluation of $f$: $G(y)=T^{-1}y-B^t f(A T^{-1}y)$; this holds in every characteristic.
  • To test whether $F(x+\alpha)-F(x)=\beta$ is solvable, check the membership $T^{-1}\beta-\alpha\in\operatorname{rowsp}B$; when it holds and $\alpha\notin\ker A$, solve $f(u+A\alpha)-f(u)=R_B^t(T^{-1}\beta-\alpha)$ instead.
  • For the linear-form equation, the role of the row space of $A$ is symmetric: when $\alpha^t-\beta^t T\in\operatorname{rowsp}A$, solutions correspond to $a\cdot u-b\cdot f(u)=0$ with $a=R_A^t(\alpha-T^t\beta)$ and $b=\beta^t T B^t$.
  • After $t\ge t_0$ compositions, at most $p^{t_0}$ parameter pairs $(\alpha,\beta)$ keep the difference or linear-form equation feasible; when the relevant kernel intersection is trivial, only the zero pair survives, so enough rounds trivialize the equations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural next step would be to run a computational census over small fields and random $A,B,T,f$, comparing all parameter pairs that actually satisfy the linear-form equation with Lemma 3's predicted set; this would measure how often the omitted cancellation occurs.
  • The missing cancellation condition can be stated precisely: the linear-form equation has solutions whenever the linear remainder $(\alpha^t-\beta^t T)x$ intersects $-\beta^t T B^t f(Ax)$ over $x$; Lemma 3 only considers the case where that intersection is empty.
  • The stabilization threshold $t_0$ gives a round-count target for cipher designers: once the number of rounds exceeds the codimension bound, the set of differential or linear parameter pairs has size at most $p^{t_0}$, so attacks needing a rich parameter space should lose their purchase.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper introduces a class of bijective functions F(x)=T(x+B^t f(Ax)) over finite fields, where A and B are orthogonal matrices with AB^t=0. It studies two families of equations, F(x+α)−F(x)=β and α·x−β·F(x)=0, and claims a complete reduction of solvability to the corresponding equations for the smaller function f, given by Lemmas 2 and 3. For compositions of extensions, Corollaries 1 and 2 assert that the set of feasible parameter pairs (α,β) stabilizes to size at most p^{t_0} after sufficiently many iterations. The motivation is cryptographic, with examples showing that Feistel networks and FOX fit the framework.

Significance. The framework is clean and the bijectivity lemma (Lemma 1) is correct, as are the examples connecting the construction to known block ciphers. If the stated characterizations were true, they would provide a useful reduction for analyzing such extensions and their compositions. However, the central linear-form characterization (Lemma 3) is false, and the counterexample below is not a degenerate edge case but a plain instance of the paper's own definitions. Because Theorem 2 and Corollary 2 rely on Lemma 3, the main advertised results for linear-form equations are unsupported. The paper also contains a reversed equivalence about im(f)∩ker B^t that compounds the problem.

major comments (3)
  1. [Section 2.2, Lemma 3] Lemma 3 is false as stated. Over GF(3), take n=2, m=1, A=[1,0], B=[0,1], T=I_2, f(u)=u^2+1, α=(1,0)^t, β=(0,1)^t. Then F(x_1,x_2)=(x_1, x_2+f(x_1)). The vector α^t−β^tT=(1,−1) is not in rowsp A=span{(1,0)}. Also im(f)={1,2} and ker B^t={0}, so im(f)∩ker B^t=∅. Yet α·x−β·F(x)=x_1−x_2−f(x_1), and at x=(0,2) this equals 0−2−1≡0 mod 3. Thus a solution exists, contradicting the 'no solution unless' clause. The proof only treats the case where β^tTB^tf(Ax) vanishes and does not rule out cancellation between the linear term (α^t−β^tT)x and the feedback term; the counterexample exhibits exactly such a cancellation.
  2. [Section 2.3, Theorem 2 and Corollary 2] Theorem 2 and Corollary 2 inherit the error from Lemma 3. The recursive reduction of β^tG_ℓ(x)−α^t x=0 in Equation (12) and the bound s_t≤p^{t_0} in Corollary 2 require the one-step linear-form characterization of Lemma 3 as the base case. Since that base case is false, the claimed stabilization of feasible parameter pairs for linear-form equations is unsupported; the proof gives no alternative argument that bypasses Lemma 3.
  3. [Section 2.2, after Lemma 3] The statement that 'the condition im(f)∩ker B^t≠∅ can be restated as 0∉im(f)' is reversed. Because B is full row rank, B^t is injective and ker B^t={0}; hence im(f)∩ker B^t≠∅ is equivalent to 0∈im(f). The reversed condition is used in the interpretation of the lemma and gives the wrong verdict in the counterexample.
minor comments (3)
  1. [Section 2.2, Lemma 3 statement] The lemma statement writes 'αt − Tβt' but the proof uses 'αt − βtT'; the latter is the expression that actually appears in the equation and should be used consistently.
  2. [Section 2.2, Lemma 3 proof] The proof says 'there is non-zero a∈F^m' when writing a^t A=α^t−β^tT, but a=0 is possible when α^t−β^tT=0; this does not change the argument but should be corrected.
  3. [Section 2.2, last paragraph] The sentence 'a simple solution occurs if f(Ax)=0 and α∈T^tβ' mixes row and column conventions; please clarify the intended vector form.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is self-contained linear algebra, with only a passing non-load-bearing self-citation.

full rationale

The paper's central claims are derived directly from the defining equation F(x)=T(x+B^t f(Ax)) by explicit algebraic manipulation. Lemma 2 rewrites F(x+alpha)-F(x)=beta, and Lemma 3 expands alpha·x - beta·F(x); both reductions use linear-algebra identities about row/column spaces and projections stated in the paper itself, not the results being proved. The composition theorems and corollaries then iterate these same rewritings. There are no fitted parameters, no empirical benchmarks, and no prediction that is statistically forced by its own input. The only self-citation, to the authors' prior cycle-structure paper [8], appears as a passing pointer for future work and is not used to justify any load-bearing step. Even though the correctness of Lemma 3's cancellation argument may be questioned by external reviewers, that is a mathematical soundness concern, not a circularity concern: the claim is not equivalent to its inputs by construction. Therefore no significant circularity is present.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper introduces no free parameters and no new entities. It relies on the standard linear algebra framework over finite fields, plus the specific structural assumption that A, B are orthogonal complementary full-rank matrices and T is invertible. The central results follow from these assumptions, but the false Lemma 3 shows the derivation from these assumptions contains an error.

assumptions (3)
  • domain assumption A and B are full-rank matrices with AB^t = 0, representing complementary orthogonal subspaces of F^n.
    This is the structural setup for the linear extension in Equation (1); all results depend on it.
  • domain assumption T is an invertible linear transformation over F.
    Required for F to be a well-defined bijection in Lemma 1 and throughout.
  • standard math Standard linear algebra facts: row space and kernel duality, Fredholm alternative for finite dimensions, canonical right projections for full-rank matrices.
    Used throughout the proofs, particularly in Lemmas 2 and 3 and Theorem 1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Feedback linearly extended discrete functions." pith.science (2026). https://pith.science/paper/KMSWS4XG

@misc{pith2026190809422,
  author       = {Pith},
  title        = {Pith review of: Feedback linearly extended discrete functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KMSWS4XG}},
  note         = {Machine review of arXiv:1908.09422}
}
read the original abstract

We study a new flexible method to extend linearly the graph of a non-linear, and usually not bijective, function so that the resulting extension is a bijection. Our motivation comes from cryptography. Examples from symmetric cryptography are given as how the extension was used implicitly in the construction of some well-known block ciphers. The method heavily relies on ideas brought from linear coding theory and secret sharing. We are interested in the behaviour of the composition of many extensions, and especially the space of parameters that defines a family of equations based on finite differences or linear forms. For any linear extension, we characterize entirely the space of parameters for which such equations are solvable in terms of the space of parameters that render those equations for the corresponding non-linear extended functions solvable. Conditions are derived to assess the solvability of those kind of equations in terms of the number of compositions or iterations. We prove a relation between the number of compositions and the dimensions of vector spaces that appear in our results. The proofs of those properties rely mostly on tools from linear algebra.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    Bose and Dijen K

    Raj C. Bose and Dijen K. Ray-Chaudhuri. On a class of error corr ecting binary group codes. Information and Control , 3(1):68–79, 1960

    work page 1960

  2. [2]

    Differential cryptanalysis of DES-like cry p- tosystems

    Eli Biham and Adi Shamir. Differential cryptanalysis of DES-like cry p- tosystems. Journal of Cryptology , 4(1):3–72, 1991

    work page 1991

  3. [3]

    Boolean functions for cryptography and error c orrecting codes

    Claude Carlet. Boolean functions for cryptography and error c orrecting codes. In Boolean Models and Methods in Mathematics, Computer Scienc e, and Engineering, 257–397. Cambridge University Press, 2010

    work page 2010

  4. [4]

    Vectorial boolean functions for cryptography

    Claude Carlet. Vectorial boolean functions for cryptography. In Boolean Models and Methods in Mathematics, Computer Science, and En gineering, 398–469. Cambridge University Press, 2010

    work page 2010

  5. [5]

    Cours d’alg` ebre

    Roger Godement. Cours d’alg` ebre. Hermann, 3rd edition, 1997. 11

    work page 1997

  6. [6]

    A Primer on Pseudorandom Generators

    Oded Goldreich. A Primer on Pseudorandom Generators . American Math- ematical Society, 2010

    work page 2010

  7. [7]

    Solomon W. Golomb. Shift Register Sequences. World Scientific, 3rd revised edition, 2017

    work page 2017

  8. [8]

    Unicyclic strong per- mutations

    Claude Gravel, Daniel Panario and David Thomson. Unicyclic strong per- mutations. Cryptography and Communications , 11(6):1211–1231, 2019

    work page 2019

Show all 22 references
  1. [9]

    Howard M. Heys. A tutorial on linear and differential cryptanalys is. Cryp- tologia, 26(3):189–221, 2002

    2002

  2. [10]

    A First Course in Coding Theory

    Raymond Hill. A First Course in Coding Theory . Oxford Applied Linguis- tics. Clarendon Press, 1986

    1986

  3. [11]

    On generalized Feistel netwo rks

    Viet Tung Hoang and Phillip Rogaway. On generalized Feistel netwo rks. In Advances in Cryptology - CRYPTO 2010 , 613–630, 2010

    2010

  4. [12]

    Codes correcteurs d’erreurs

    Alexis Hocquenghem. Codes correcteurs d’erreurs. Chiffres, 2(2):147–56, 1959

    1959

  5. [13]

    FOX Specifications Version 1.2, 2005

    Pascal Junod and Serge Vaudenay. FOX Specifications Version 1.2, 2005

    2005

  6. [14]

    Xuejia Lai and James. L. Massey A proposal for a new block enc ryp- tion standard. In Advances in Cryptology, EUROCRYPT ’90 , 389–404. Springer-Verlag, 1991

    1991

  7. [15]

    Finite Fields

    Rudolf Lidl and Harold Niederreiter. Finite Fields . Cambridge University Press, 1997

    1997

  8. [16]

    How to construct pseudora ndom per- mutations from pseudorandom functions

    Michael Luby and Charles Rackoff. How to construct pseudora ndom per- mutations from pseudorandom functions. SIAM Journal on Computing , 17(2):373–386, 1988

    1988

  9. [17]

    Linear cryptanalysis method for DES cipher

    Mitsuru Matsui. Linear cryptanalysis method for DES cipher. In Advances in Cryptology — EUROCRYPT ’93 , 386–397. Springer-Verlag, 1994

    1994

  10. [18]

    McEliece and Dilip V

    Robert J. McEliece and Dilip V. Sarwate. On sharing secrets and R eed- Solomon codes. Communications of the ACM , 24(9):583–584, September 1981

    1981

  11. [19]

    Mullen and Daniel Panario

    Gary L. Mullen and Daniel Panario. Handbook of Finite Fields . Chapman & Hall/CRC, 2013

    2013

  12. [20]

    How to share a secret

    Adi Shamir. How to share a secret. Communications of the ACM , 22(11):612–613, November 1979

    1979

  13. [21]

    Correlation-immunity of non-linear combin ing func- tions for cryptographic applications

    Thomas Siegenthaler. Correlation-immunity of non-linear combin ing func- tions for cryptographic applications. IEEE Transactions on Information Theory, 30:776–780, 1984

    1984

  14. [22]

    Guo-Zhen Xiao and James L. Massey. A spectral characteriza tion of correlation-immune combining functions. IEEE Transactions on Informa- tion Theory, 34(3):569–571, 1988. 12

    1988

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.