{"id":"55dc17a9-7b61-4ca2-b510-73dbaef0b4c8","arxiv_id":"1908.09422","paper_version":5,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper gives linear-algebraic conditions for solving difference and linear-form equations over feedback-based bijective extensions of non-linear functions, claiming exact parameter-space characterizations and bounds under composition.","lead":"This paper introduces a linear algebraic framework for turning arbitrary non-linear functions into bijections, and analyzes when difference and linear equations for the resulting maps are solvable. The authors claim to fully characterize the solvable parameter spaces, and to show the spaces shrink as rounds are composed, with applications to block cipher cryptanalysis.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3 is false: the linear term and the nonlinear feedback term can cancel, so the promised complete linear-form characterization does not hold.","rationale":"The reader's weakest assumption identifies exactly the same weak point, and I verified the counterexample by hand. The arithmetic uses the paper's own standard-form A and B, so no hidden assumption is needed. This is not a disagreement with cryptographic convention; it is an internal refutation of Lemma 3. The finite-difference results (Lemma 2, Theorem 1, Corollary 1) do not appear affected, but the abstract promises a complete characterization for both equation families, and the linear-form half is load-bearing for Theorem 2 and Corollary 2. Since those claims rest on a false lemma, the central claim as stated is unsupported. I also note the manuscript itself contains a contradictory restatement of the im(f)∩ker B^t condition, consistent with the lemma being uncareful. The reader's REJECT verdict is appropriate, so I recommend no change.","tokens_in":10385,"tokens_out":10593,"duration_ms":93559,"concrete_test":"Run an exhaustive check over GF(3)^2: with A=[1,0], B=[0,1], T=I, f(u)=u^2+1, α=(1,0), β=(0,1), compute F(x)=T(x+B^t f(Ax)) for all x and list the solutions to α·x−β·F(x)=0. If x=(0,2) is in the list while α^t−β^tT∉rowsp A and im(f)∩ker B^t=∅, then Lemma 3's first clause is refuted. Repeating the check over all functions f:GF(3)→GF(3) would confirm the failure is not peculiar to this one f.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 3 is the load-bearing step for the paper's linear-form characterization. Its first clause claims that if α^t−β^tT ∉ rowsp A, then α·x−β·F(x)=0 has no solution unless im(f)∩ker B^t≠∅. The proof only examines the case where the feedback term β^tTB^t f(Ax) vanishes; it does not rule out cancellation between that term and (α^t−β^tT)x. The following counterexample uses the paper's own definitions. Over GF(3), set m=1, n=2, A=[1,0], B=[0,1], T=I, f(u)=u^2+1, α=(1,0), β=(0,1). Then α^t−β^tT=(1,−1)∉rowsp A=span{(1,0)}, and im(f)={1,2} is disjoint from ker B^t={0}. Yet F(x1,x2)=(x1,x2+f(x1)), and α·x−β·F(x)=x1−x2−f(x1); at x=(0,2) this is 0−2−1≡0 mod 3, so a solution exists. Thus Lemma 3's no-solution clause is false. Theorem 2 and Corollary 2 reduce linear-form equations for composed extensions to Lemma 3, so the claimed parameter-space stabilization for linear forms is unsupported. The paper's restatement that im(f)∩ker B^t≠∅ is equivalent to 0∉im(f) is also reversed.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10624,"tokens_out":9818,"duration_ms":78907,"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":[{"comment":"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.","section":"Section 2.2, Lemma 3"},{"comment":"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.","section":"Section 2.3, Theorem 2 and Corollary 2"},{"comment":"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.","section":"Section 2.2, after Lemma 3"}],"minor_comments":[{"comment":"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.","section":"Section 2.2, Lemma 3 statement"},{"comment":"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.","section":"Section 2.2, Lemma 3 proof"},{"comment":"The sentence 'a simple solution occurs if f(Ax)=0 and α∈T^tβ' mixes row and column conventions; please clarify the intended vector form.","section":"Section 2.2, last paragraph"}],"recommendation":"reject","confidential_remarks":"The counterexample to Lemma 3 is decisive and uses only the paper's own definitions in the simplest nontrivial case. Combined with the reversed equivalence about im(f)∩ker B^t, the linear-form results do not appear repairable by local edits; the advertised complete characterization is false. The finite-difference part (Lemma 2) and the bijectivity lemma remain of some interest, but the paper's central claim fails."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read on 1908.09422. The headline is that the finite-difference half is in decent shape, but the linear-form half is not: Lemma 3 is false, and the linear-form results should not be trusted.\n\nThe framework is nice. Defining F(x)=T(x+B^t f(Ax)) and proving it is a bijection (Lemma 1) is clean, and the examples showing Feistel, FOX, and generalized Feistel as instances are genuinely informative. Lemma 2 on finite differences appears correct: the parameter condition T^{-1}β−α∈rowsp B is natural, and the reduction to f(u+a)−f(u)=b looks right. Corollary 1's bound, conditional on Lemma 4, is a plausible result.\n\nThe problem is Lemma 3. It claims that if α^t−β^tT∉rowsp A, then α·x−β·F(x)=0 has no solution unless im(f)∩ker B^t≠∅. The proof only handles the case where the feedback term β^tTB^t f(Ax) is zero; it never excludes cancellation with the linear term. Cancellation really can happen. Over GF(3), take m=1, n=2, A=[1,0], B=[0,1], T=I, f(u)=u^2+1, α=(1,0), β=(0,1). Then α^t−β^tT=(1,2) is outside rowsp A, im(f)={1,2} is disjoint from ker B^t={0}, but x=(0,2) gives F(x)=(0,0), so α·x−β·F(x)=0. That is a direct counterexample to the lemma. Since Theorem 2 and Corollary 2 rely on the same reduction, the claimed complete characterization for linear forms is unsupported. There is also a small but telling slip right after Lemma 3: im(f)∩ker B^t≠∅ is equivalent to 0∈im(f), not 0∉im(f), because ker B^t={0}.\n\nWho gets value: cryptographers interested in generalized Feistel networks and differential properties might use the finite-difference part and the framework. The linear-form claims should be ignored until the lemma is repaired or the scope is narrowed.\n\nMy recommendation: reject as-is, but send to peer review rather than desk reject. A referee can pin down the exact condition under which the linear-form equations are reducible, and the finite-difference results are worth preserving. If the authors replace Lemma 3 with a valid statement, the paper could become a reasonable contribution.","headline":"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.","tokens_in":11208,"tokens_out":9177,"would_cite":false,"duration_ms":76481,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["12E20","15A03","15B10","39A06","39A12","94A60","94B05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["vector spaces over finite fields","finite dimensional Fredholm alternative theorem","feedback shift register","block cipher","differential cryptanalysis","linear cryptanalysis","pseudo-randomness","linear extension of functions"],"falsifier":"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.","tokens_in":10103,"feed_emoji":"🔐","tokens_out":14211,"duration_ms":128205,"temperature":0.7,"pith_summary":"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.","feed_headline":"Feedback turns any nonlinear map into a bijection","feed_subtitle":"Over finite fields, difference and linear equations reduce to the small function's equations and stabilize after enough rounds.","key_machinery":"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}$.","core_discovery":"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}$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces differential cryptanalysis, the attack motivating the finite-difference equation $F(x+\\alpha)-F(x)=\\beta$ central to Lemma 2 and Theorem 1.","marker":"[2]"},{"why":"Introduces linear cryptanalysis, the attack motivating the linear-form equation $\\alpha\\cdot x-\\beta\\cdot F(x)=0$ central to Lemma 3 and Theorem 2.","marker":"[17]"},{"why":"Supplies the finite-dimensional Fredholm alternative and the row-space/kernel identities on which the parameter reductions rely.","marker":"[5]"},{"why":"Shows how orthogonal matrices $A$ and $B$ with $AB^t=0$ arise from linear coding theory, the main source of construction instances.","marker":"[10]"},{"why":"Defines the generalized Feistel network taxonomy in which Examples 1, 3, and 4 place the extension as a uniform template.","marker":"[11]"},{"why":"Specifies the FOX block cipher used as Example 2 of an implicit linear extension.","marker":"[13]"},{"why":"Provides the Lai-Massey construction underlying IDEA NXT/FOX, cited for the FOX example.","marker":"[14]"},{"why":"Establishes the four-round composition result for Feistel networks that motivates the paper's analysis of compositions of extensions.","marker":"[16]"}],"fun_headline_variants":["Nonlinear maps become bijections via feedback","Feedback extension yields explicit inverse and exact reduction","Difference equations reduce to small map's equations","Feedback compositions stabilize after finite rounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Nonlinear maps become bijections via feedback","Feedback extension yields explicit inverse and exact reduction","Difference equations reduce to small map's equations","Feedback compositions stabilize after finite rounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00059,"raw_usage":{"total_tokens":2829,"prompt_tokens":1064,"completion_tokens":1765,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":680,"completion_tokens_details":{"reasoning_tokens":1711}},"tokens_in":680,"tokens_out":1765,"duration_ms":15326,"temperature":1.0,"reasoning_tokens":1711,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:11:54.234465+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Differential cryptanalysis of DES-like cry p- tosystems","cited_arxiv_id":null,"evidence_quote":"Introduces differential cryptanalysis, the attack motivating the finite-difference equation $F(x+\\alpha)-F(x)=\\beta$ central to Lemma 2 and Theorem 1."},{"cited_title":"Linear cryptanalysis method for DES cipher","cited_arxiv_id":null,"evidence_quote":"Introduces linear cryptanalysis, the attack motivating the linear-form equation $\\alpha\\cdot x-\\beta\\cdot F(x)=0$ central to Lemma 3 and Theorem 2."},{"cited_title":"Cours d’alg` ebre","cited_arxiv_id":null,"evidence_quote":"Supplies the finite-dimensional Fredholm alternative and the row-space/kernel identities on which the parameter reductions rely."},{"cited_title":"A First Course in Coding Theory","cited_arxiv_id":null,"evidence_quote":"Shows how orthogonal matrices $A$ and $B$ with $AB^t=0$ arise from linear coding theory, the main source of construction instances."},{"cited_title":"On generalized Feistel netwo rks","cited_arxiv_id":null,"evidence_quote":"Defines the generalized Feistel network taxonomy in which Examples 1, 3, and 4 place the extension as a uniform template."},{"cited_title":"FOX Specifications Version 1.2, 2005","cited_arxiv_id":null,"evidence_quote":"Specifies the FOX block cipher used as Example 2 of an implicit linear extension."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Lai-Massey construction underlying IDEA NXT/FOX, cited for the FOX example."},{"cited_title":"How to construct pseudora ndom per- mutations from pseudorandom functions","cited_arxiv_id":null,"evidence_quote":"Establishes the four-round composition result for Feistel networks that motivates the paper's analysis of compositions of extensions."}],"review_version":1}