pith. sign in

arxiv: 1907.01066 · v1 · pith:2XGAWOANnew · submitted 2019-06-27 · 💻 cs.IT · cs.CR· math.IT

On two-to-one mappings over finite fields

Sihem Mesnager , Longjiang Qu This is my paper

Pith reviewed 2026-05-25 14:21 UTC · model grok-4.3

classification 💻 cs.IT cs.CRmath.IT
keywords two-to-one mappingsfinite fieldsWalsh transformsbent functionsAPN functionssemi-bent functionsDickson polynomialspermutation polynomials
0
0 comments X

The pith

Two-to-one mappings over finite fields are characterized via their Walsh transforms and admit multiple explicit constructions.

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

The paper aims to give a full description of mappings from a finite field to itself where each output value is hit exactly twice or not at all. A reader would care because these mappings serve as building blocks for functions with strong resistance to linear and differential cryptanalysis. The authors achieve this by deriving a condition on the Walsh transforms and by exhibiting constructions in several families of polynomials. They also show how the mappings produce new examples of bent functions and other cryptographic objects. The study covers both general methods and specific polynomial classes such as monomials and Dickson polynomials.

Core claim

Two-to-one mappings over finite fields are those for which the equation f(x) = a has either zero or two solutions for every a in the field. The paper shows that these mappings are precisely those whose Walsh transforms satisfy a certain magnitude condition at every nonzero point. It supplies an AGW-like criterion and other construction methods based on permutation polynomials, linear translators, and APN functions, then applies them to produce bent Boolean functions, vectorial bent functions, semi-bent functions, planar functions, and permutation polynomials.

What carries the argument

The Walsh transform condition that forces the preimage size to be at most two for every value.

Load-bearing premise

The Walsh-transform condition fully captures the two-to-one property for every finite field and every polynomial degree.

What would settle it

An explicit two-to-one polynomial whose Walsh spectrum violates the stated condition at some point would falsify the characterization.

read the original abstract

Two-to-one ($2$-to-$1$) mappings over finite fields play an important role in symmetric cryptography. In particular they allow to design APN functions, bent functions and semi-bent functions. In this paper we provide a systematic study of two-to-one mappings that are defined over finite fields. We characterize such mappings by means of the Walsh transforms. We also present several constructions, including an AGW-like criterion, constructions with the form of $x^rh(x^{(q-1)/d})$, those from permutation polynomials, from linear translators and from APN functions. Then we present $2$-to-$1$ polynomial mappings in classical classes of polynomials: linearized polynomials and monomials, low degree polynomials, Dickson polynomials and Muller-Cohen-Matthews polynomials, etc. Lastly, we show applications of $2$-to-$1$ mappings over finite fields for constructions of bent Boolean and vectorial bent functions, semi-bent functions, planar functions and permutation polynomials. In all those respects, we shall review what is known and provide several new results.

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

0 major / 3 minor

Summary. The paper provides a systematic study of two-to-one (2-to-1) mappings over finite fields. It characterizes such mappings using Walsh transforms, presents constructions including an AGW-like criterion, mappings of the form x^r h(x^{(q-1)/d}), and derivations from permutation polynomials, linear translators, and APN functions. It then examines 2-to-1 polynomials within classical families (linearized polynomials, monomials, low-degree polynomials, Dickson polynomials, Muller-Cohen-Matthews polynomials) and applies the mappings to construct bent Boolean/vectorial bent functions, semi-bent functions, planar functions, and permutation polynomials, while reviewing known results and adding new ones.

Significance. If the Walsh-transform characterization and the listed constructions hold, the paper supplies a coherent toolkit for generating 2-to-1 mappings with direct cryptographic utility (APN, bent, semi-bent, planar functions). The explicit families in standard polynomial classes and the applications section would constitute a useful reference for researchers working on functions over finite fields.

minor comments (3)
  1. [Abstract] The abstract states that the Walsh-transform characterization and constructions hold uniformly over arbitrary finite fields of order q; the manuscript should explicitly state any characteristic or degree restrictions that appear in the proofs of the main theorems.
  2. [Applications] In the applications section, clearly separate the reviewed known constructions from the new results obtained via the 2-to-1 mappings; a short table or enumerated list would improve readability.
  3. Notation for the Walsh transform and the precise definition of a 2-to-1 mapping should be fixed at the first appearance and used consistently thereafter.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our work and the recommendation of minor revision. We are pleased that the systematic study, Walsh-transform characterization, constructions, and applications to bent/semi-bent functions and permutation polynomials are viewed as a useful reference.

Circularity Check

0 steps flagged

No significant circularity; derivations are self-contained characterizations and constructions

full rationale

The paper presents a Walsh-transform characterization of 2-to-1 mappings and explicit constructions (AGW-like criterion, forms like x^r h(x^{(q-1)/d}), derivations from permutation polynomials, linear translators, and APN functions, plus families in classical polynomial classes). These are described as derived from established external objects and applied to bent/semi-bent/planar functions. No quoted step reduces a claimed result to a fitted parameter, self-definition, or load-bearing self-citation chain; the central claims remain independent of the paper's own outputs. The work is a systematic study that reviews known results while adding new ones, with no evidence that any prediction or uniqueness claim collapses by construction to its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the standard algebraic theory of finite fields and the Walsh transform; no free parameters, invented entities, or ad-hoc axioms are visible in the abstract.

axioms (1)
  • standard math Standard properties of finite fields and the Walsh transform over them
    The characterization and constructions presuppose the usual algebraic structure of finite fields of order q and the definition of the Walsh transform.

pith-pipeline@v0.9.0 · 5711 in / 1192 out tokens · 26980 ms · 2026-05-25T14:21:59.706378+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

31 extracted references · 31 canonical work pages · 1 internal anchor

  1. [1]

    Akbary, D

    A. Akbary, D. Ghioca and Q. Wang.: On constructing permut ations of finite fields. Finite Fields and Their Applications 17, pages 51–67, 2011

    work page 2011

  2. [2]

    Berlekamp, H

    E.R. Berlekamp, H. Rumsey, and G. Solomon. On the solutio n of algebraic equations over finite fields. Information And Control. 10(67): 553-564 , 1967

    work page 1967

  3. [3]

    Boolean Models and Methods in Mat hematics, Computer Science, and Engineering

    C. Carlet.: Boolean Functions for Cryptography and Erro r Correcting Codes. In Chapter of the monography “Boolean Models and Methods in Mat hematics, Computer Science, and Engineering" published by Cambridge University Press, Yve s Crama and Peter L. Hammer (eds.), pages 257–397, 2010

    work page 2010

  4. [4]

    Carlet.: Characterizations of the differential unifo rmity of vectorial functions by the Walsh transform

    C. Carlet.: Characterizations of the differential unifo rmity of vectorial functions by the Walsh transform. IEEE Transactions on Information Theory 6 4(9), pages 6443–6453, 2018

    work page 2018

  5. [5]

    Carlet and S

    C. Carlet and S. Mesnager.: On Dillon’s class H of bent fun ctions, Niho bent functions and o-polynomials. J. Comb. Theory, Ser. A 118(8), pages 239 2–2410, 2011

    work page 2011

  6. [6]

    Carlet and S

    C. Carlet and S. Mesnager.: Four decades of research on be nt functions. Journal Designs, Codes and Cryptography, 78(1), pages 5–50, 2016

    work page 2016

  7. [7]

    Charpin and G

    P. Charpin and G. Kyureghyan.: When does G(x) +γTr (H(x)) permute Fpn? Finite Fields and Their Applications 15(5), pages 615–632, 2009. 26

    work page 2009

  8. [8]

    Charpin and G

    P. Charpin and G. M. Kyureghyan.: Monomial functions wit h linear structure and permutation polynomials In Finite Fields: Theory and Appli cations - Fq9 - Contem- porary Mathematics, AMS, number 518, pages. 99-111, 2010

    work page 2010

  9. [9]

    Charpin, S

    P. Charpin, S. Mesnager and S. Sarkar.: Involutions over the Galois field F2n. IEEE Trans. Information Theory 62 (4), pages 2266-2276, 2016

    work page 2016

  10. [10]

    Chen and J

    Y. Chen and J. Polhill.: Paley type group schemes and pla nar Dembowski-Ostrom polynomials Journal Discrete Mathematics, Volume 311, Iss ue 14, pages 1349-1364, 2011

    work page 2011

  11. [11]

    S. D. Cohen and R. W. Matthews.: A class of exceptional po lynomials, Transactions of the American Mathematical Society, Vol. 345, No. 2, pages 897-909, 1994

    work page 1994

  12. [12]

    T. W. Cusick and H. Dobbertin.: Some new three-valued cr osscorrelation functions for binary m-sequences. IEEE Transactions on Information T heory 42(4), pages 1238–1240, 1996

    work page 1996

  13. [13]

    Dembowski and T.G

    P. Dembowski and T.G. Ostrom.: Planes of order n with collineation groups of order n2. In Math. Z. 103, pages 239–258, 1968

    work page 1968

  14. [14]

    Dillon.: Elementary Hadamard difference sets

    J. Dillon.: Elementary Hadamard difference sets. In PhD dissertation, University of Maryland, 1974

    work page 1974

  15. [15]

    R. Lidl, G. L. Mullen and G. Turnwald.: Dickson polynomi als In Longman Scientific Technical, 1993

    work page 1993

  16. [16]

    Dillon and H

    J. Dillon and H. Dobbertin.: New cyclic difference sets w ith singer parameters. Finite fields and their applications 10, pages 342- 389, 2004

    work page 2004

  17. [17]

    Hou.: Permutation polynomials over finite fields–A su rvey of recent advances, Finite Fields Appl

    X. Hou.: Permutation polynomials over finite fields–A su rvey of recent advances, Finite Fields Appl. 32, pages 82-119, 2015

    work page 2015

  18. [18]

    X. Hou, G. L. Mullen, J. A. Sellers and J. L.Yucas.: Rever sed Dickson polynomials over finite fields. Finite Fields Appl. Vol 15, Issue 6, pages 7 48-773, 2009

    work page 2009

  19. [19]

    Kocak, S

    N. Kocak, S. Mesnager and F. Ozbudak.: Bent and semi-ben t functions via linear translators. Proceedings of the fifteenth International Co nference on Cryptography and Coding, Oxford, United Kingdom, IMACC 2015, pages 205-2 24, LNCS, Springer, Heidelberg, 2015

    work page 2015

  20. [20]

    Kyureghyan.: Special mappings of finite fields Finite Fields and Their Applications

    G. Kyureghyan.: Special mappings of finite fields Finite Fields and Their Applications. Character Sums and Polynomials. Series on Computational an d applied mathematics, pages 117-240, 2013. 27

    work page 2013

  21. [21]

    Kyureghyan.: Constructing permutations of finite fie lds via linear translators

    G. Kyureghyan.: Constructing permutations of finite fie lds via linear translators. Journal of Combinatorial Theory Series A. 118(3), pages 105 2–1061, 2011

    work page 2011

  22. [22]

    Kyureghyan and A

    G. Kyureghyan and A. Pott.: Some theorems on planar mapp ings. Arithmetic of finite fields, 117-122, Lecture Notes in Comput. Sci., 5130, S pringer, Berlin, 2008

    work page 2008

  23. [23]

    R. L. McFarland.: A family of noncyclic difference sets. Journal of Combinatorial Theory, Series A, No. 15, pages 1–10, 1973

    work page 1973

  24. [24]

    Mesnager.: Bent functions: fundamentals and result s

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

    work page 2016

  25. [25]

    Maschietti.: Difference sets and hyperovals

    A. Maschietti.: Difference sets and hyperovals. Des. Co des Cryptgr. 14 (1998) 89–98

    work page 1998

  26. [26]

    Mullen, D

    G.L. Mullen, D. Panario.: Handbook of Finite Fields, Ta ylor Francis, Boca Raton, 2013

    work page 2013

  27. [27]

    Pott.: Almost perfect and planar functions, Designs , Codes and Cryptography, Vol

    A. Pott.: Almost perfect and planar functions, Designs , Codes and Cryptography, Vol. 78(1), pages, 41-195, 2016

    work page 2016

  28. [28]

    Rothaus.: On "bent" functions

    O.S. Rothaus.: On "bent" functions. Journal of Combina torial Theory, Serie A Vol. 20, pages 300–305, 1976

    work page 1976

  29. [29]

    Williams

    K.S. Williams. Note on Cubics over GF(2n) and GF(3n)∗ . Journal of Number Theory. 7: 361-365, 1975

    work page 1975

  30. [30]

    Permutation polynomials on F_q induced from bijective Redei functions on subgroups of the multiplicative group of F_q

    M.E. Zieve.: Permutation polynomials on Fq induced from bijective Rédei functions on subgroups of the multiplicative group of Fq, arXiv:1310.0776, 2013

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  31. [31]

    Villa, On APN functions L1(x3)+L2(x9) with linearL1 andL2, Cryptogr

    I. Villa, On APN functions L1(x3)+L2(x9) with linearL1 andL2, Cryptogr. Commun., Vol. 11, pp. 3–20, 2019. 28

    work page 2019