pith. sign in

arxiv: 2506.05374 · v3 · submitted 2025-05-30 · 💻 cs.CR · cs.IT· math.IT

A New Representation of Binary Sequences by means of Boolean Functions

S.D. Cardell , A. F\'uster-Sabater , V. Requena , M. Beltr\'a This is my paper

Pith reviewed 2026-05-19 13:19 UTC · model grok-4.3

classification 💻 cs.CR cs.ITmath.IT
keywords Boolean functionsbinary sequencesreverse-ANFalgebraic normal formgeneralized self-shrinking sequencescryptographyperiodicitybijection
0
0 comments X

The pith

A bijection connects Boolean functions to binary sequences of period a power of two and yields a reverse-ANF representation for studying their properties.

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

The paper introduces a bijection between the set of Boolean functions and the set of binary sequences whose periods are powers of two. This correspondence lets properties of each object be examined through the other. From the algebraic normal form the authors derive a reverse-ANF representation of sequences. They then apply the new tools to generalized self-shrinking sequences and examine relations among the different representations.

Core claim

The paper establishes a bijection between Boolean functions on n variables and binary sequences of period 2^n. It defines the reverse-ANF as a sequence representation obtained directly from the algebraic normal form of the corresponding Boolean function. Using this framework the authors analyze generalized self-shrinking sequences and compare the new representation with existing ones for Boolean functions and sequences.

What carries the argument

The bijection between Boolean functions and period-2^n binary sequences together with the reverse-ANF representation derived from the algebraic normal form.

If this is right

  • Properties of Boolean functions such as linearity can be read off from the corresponding periodic sequence.
  • Generalized self-shrinking sequences admit a Boolean-function description that clarifies their periodicity and complexity.
  • The reverse-ANF supplies an alternative computational route to sequence attributes previously studied only via the direct algebraic normal form.
  • Relations between multiple representations of the same Boolean function or sequence become visible through the new mapping.

Where Pith is reading between the lines

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

  • Designers of stream ciphers could construct new sequences by starting from Boolean functions known to possess desired correlation or nonlinearity properties.
  • The mapping may supply fresh invariants for distinguishing families of pseudorandom sequences that share the same period.
  • Similar bijections might be sought for sequences whose periods are not powers of two, extending the reach of the technique.

Load-bearing premise

The bijection and reverse-ANF reveal cryptographically relevant properties such as linearity and correlation that are not already captured by standard representations.

What would settle it

If the reverse-ANF applied to a generalized self-shrinking sequence produces exactly the same linearity and correlation measures already obtained from the ordinary algebraic normal form, the claim of new insight would be refuted.

read the original abstract

Boolean functions and binary sequences are main tools used in cryptography. In this work, we introduce a new bijection between the set of Boolean functions and the set of binary sequences with period a power of two. We establish a connection between them which allows us to study some properties of Boolean functions through binary sequences and vice versa. Then, we define a new representation of sequences, based on Boolean functions and derived from the algebraic normal form, named reverse-ANF. Next, we study the relation between such a representation and other representations of Boolean functions as well as between such a representation and the binary sequences. Finally, we analyse the generalized self-shrinking sequences in terms of Boolean functions and some of their properties using the different representations.

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

3 major / 2 minor

Summary. The paper claims to introduce a new bijection between the set of Boolean functions on n variables and the set of binary sequences with period 2^n, derived from the standard truth-table correspondence. It defines a 'reverse-ANF' representation obtained from the algebraic normal form (ANF), studies relations between this representation and other Boolean function representations as well as binary sequences, and applies the framework to analyze properties of generalized self-shrinking sequences, including linearity, correlation, and complexity.

Significance. If the claimed bijection and reverse-ANF yield non-redundant insights into cryptographic properties of sequences that are not already accessible via standard ANF or linear complexity measures, the work could strengthen connections between Boolean function theory and sequence design in stream ciphers. However, the manuscript provides no machine-checked proofs, reproducible code, or falsifiable predictions that would elevate its impact beyond a definitional contribution.

major comments (3)
  1. [§2] §2 (Definition of the bijection): The mapping from Boolean functions to periodic sequences of period 2^n via truth tables is the standard identification already used in the literature on Boolean functions and de Bruijn sequences; the paper must explicitly state what makes this bijection 'new' and demonstrate that it enables property transfers (e.g., algebraic degree to linear complexity) not already available from the direct ANF-to-sequence correspondence.
  2. [§3] §3 (Reverse-ANF definition): If reverse-ANF amounts to a reordering or bit-reversal of monomials in the ANF (as suggested by the derivation from ANF), then any claimed advantage for studying correlation or nonlinearity of generalized self-shrinking sequences is already captured by existing ANF analysis; the manuscript should provide a concrete example where reverse-ANF reveals a property invisible from standard ANF or the sequence's linear complexity profile.
  3. [§5] §5 (Application to generalized self-shrinking sequences): The analysis of cryptographic properties (linearity, correlation, complexity) via the new representations lacks quantitative comparison against baseline methods; without such a comparison or a theorem showing strict improvement, the central claim that the framework 'allows us to study some properties ... in ways not already captured' remains unsubstantiated.
minor comments (2)
  1. [Abstract] The abstract and introduction should include a brief comparison table or explicit statement distinguishing the proposed reverse-ANF from the standard ANF and from other known representations such as the Walsh-Hadamard transform.
  2. [§2] Notation for the period-2^n sequences and the indexing of truth tables should be clarified to avoid ambiguity when n varies; consider adding a small example for n=2 or n=3 with explicit truth table, ANF, and reverse-ANF.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and valuable comments on our manuscript. We address each of the major comments below, indicating the revisions we plan to make.

read point-by-point responses

  1. Referee: [§2] §2 (Definition of the bijection): The mapping from Boolean functions to periodic sequences of period 2^n via truth tables is the standard identification already used in the literature on Boolean functions and de Bruijn sequences; the paper must explicitly state what makes this bijection 'new' and demonstrate that it enables property transfers (e.g., algebraic degree to linear complexity) not already available from the direct ANF-to-sequence correspondence.

    Authors: We agree that the underlying truth-table mapping is standard in the literature. The novelty in our work lies in the specific construction of the bijection that naturally leads to the reverse-ANF representation, enabling a bidirectional study of properties between Boolean functions and sequences. In the revised manuscript, we will explicitly clarify the distinguishing aspects of this bijection and provide a concrete demonstration of property transfer, for example showing how the algebraic degree influences the linear complexity in generalized self-shrinking sequences through this mapping. revision: yes

  2. Referee: [§3] §3 (Reverse-ANF definition): If reverse-ANF amounts to a reordering or bit-reversal of monomials in the ANF (as suggested by the derivation from ANF), then any claimed advantage for studying correlation or nonlinearity of generalized self-shrinking sequences is already captured by existing ANF analysis; the manuscript should provide a concrete example where reverse-ANF reveals a property invisible from standard ANF or the sequence's linear complexity profile.

    Authors: We appreciate this observation. While reverse-ANF is derived from the ANF, it is not merely a reordering but a representation that reinterprets the coefficients in the context of sequence periodicity. To substantiate the claimed advantages, we will include in the revision a specific example with a generalized self-shrinking sequence where the reverse-ANF highlights a correlation property that is not directly evident from the standard ANF or linear complexity profile. revision: yes

  3. Referee: [§5] §5 (Application to generalized self-shrinking sequences): The analysis of cryptographic properties (linearity, correlation, complexity) via the new representations lacks quantitative comparison against baseline methods; without such a comparison or a theorem showing strict improvement, the central claim that the framework 'allows us to study some properties ... in ways not already captured' remains unsubstantiated.

    Authors: We acknowledge that the current analysis would benefit from quantitative comparisons. We will revise Section 5 to include comparisons with baseline approaches, such as direct application of ANF and standard linear complexity measures, to better demonstrate the added value of our framework in analyzing the properties of generalized self-shrinking sequences. revision: yes

Circularity Check

0 steps flagged

No significant circularity; bijection and reverse-ANF are presented as definitional mappings without reducing to self-referential inputs or self-citations.

full rationale

The paper introduces a bijection between Boolean functions and period-2^k binary sequences by mapping each function to the periodic repetition of its truth table, then defines reverse-ANF as a representation derived from the algebraic normal form. No equations in the provided text equate a claimed property (linearity, correlation, or complexity of generalized self-shrinking sequences) back to fitted parameters or prior self-citations by construction. The connection between representations is stated as a direct consequence of the truth-table identification, which is self-contained and does not rely on load-bearing self-citations or uniqueness theorems imported from the authors' prior work. The analysis of cryptographic properties is framed as an application of the new representations rather than a derivation that collapses to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities; all such items remain unknown.

pith-pipeline@v0.9.0 · 5665 in / 1057 out tokens · 17970 ms · 2026-05-19T13:19:49.255583+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages

  1. [1]

    In: Encyclopedia of Mathematics and Its Applications

    Crama, Y., Hammer, P.L.: Boolean functions: Theory, algorithms, and appli- cations. In: Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge (2011) 30

    work page 2011

  2. [2]

    In: Crama, Y., Hammer, P.L

    Krause, M., Wegener, I.: Circuit complexity. In: Crama, Y., Hammer, P.L. (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pp. 506–530. Cambridge University Press, Cambridge (2010)

    work page 2010

  3. [3]

    Addison Wesley Publishing Co., MA (1994)

    Papadimitriou, C.H.: Computational Complexity. Addison Wesley Publishing Co., MA (1994)

    work page 1994

  4. [4]

    North-Holland, Amsterdam (1988)

    MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes, 6th edn. North-Holland, Amsterdam (1988)

    work page 1988

  5. [5]

    Cambridge University Press, Cambridge (2021)

    Carlet, C.: Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, Cambridge (2021)

    work page 2021

  6. [6]

    University of California Press, California (1987)

    Ragin, C.C.: The Comparative Method: Moving Beyond Qualitative and Quanti- tative Strategies. University of California Press, California (1987). http://www. jstor.org/stable/10.1525/j.ctt1pnx57

    work page doi:10.1525/j.ctt1pnx57 1987

  7. [7]

    Nature 407, 630–633 (2000) https://doi.org/10.1038/35036586

    Feldman, J.: Minimization of boolean complexity in human concept learning. Nature 407, 630–633 (2000) https://doi.org/10.1038/35036586

    work page doi:10.1038/35036586 2000

  8. [8]

    Annals of Operations Research 148, 203–225 (2006)

    Bonates, T., Hammer, P.L.: Logical analysisof data: From combinatorial opti- mization to medical applications. Annals of Operations Research 148, 203–225 (2006)

    work page 2006

  9. [9]

    Bioinformatics18(4), 555–565 (2002) https://doi.org/10

    Shmulevich, I., Zhang, W.: Binary analysis and optimization-based normalization of gene expression data . Bioinformatics18(4), 555–565 (2002) https://doi.org/10. 1093/bioinformatics/18.4.555 https://academic.oup.com/bioinformatics/article- pdf/18/4/555/669285/180555.pdf

    work page 2002

  10. [10]

    In: Canteaut, A., Viswanathan, K

    Braeken, A., Nikov, V., Nikova, S., Preneel, B.: On Boolean functions with gener- alized cryptographic properties. In: Canteaut, A., Viswanathan, K. (eds.) Progress in Cryptology – INDOCRYPT 2004. Lecture Notes in Computer Science, vol. 3348, pp. 120–135. Springer, Berlin (2004)

    work page 2004

  11. [11]

    In: Quisquater, J.J., Vandewalle, J

    Meier, W., Staffelbach, O.: Nonlinearity criteria for cryptographic functions. In: Quisquater, J.J., Vandewalle, J. (eds.) Advances in Cryptology – EURO- CRYPT’89. Lecture Notes in Computer Science, vol. 434, pp. 549–562. Springer, Berlin (1990)

    work page 1990

  12. [12]

    McAllister

    Adams, C.M.: Constructing symmetric ciphers using the CAST design procedure. Designs, Codes and Cryptography12, 283–316 (1997) https://doi.org/10.1023/A: 1008229029587

    work page doi:10.1023/a: 1997

  13. [13]

    IEEE Transactions on Information Theory 51(1), 339–348 (2005) https://doi

    Gupta, K.C., Sarkar, P.: Improved construction of nonlinear resilient S-boxes. IEEE Transactions on Information Theory 51(1), 339–348 (2005) https://doi. org/10.1109/TIT.2004.839524 31

    work page doi:10.1109/tit.2004.839524 2005

  14. [14]

    In: Davies, D.W

    Nyberg, K.: Perfect nonlinear S-boxes. In: Davies, D.W. (ed.) Advances in Cryp- tology – EUROCRYPT’91. Lecture Notes in Computer Science, vol. 547, pp. 378–386. Springer, Berlin (1991)

    work page 1991

  15. [15]

    In: 2011 International Conference for Internet Technology and Secured Transactions, pp

    Al Shehhi, M.A., Baek, J., Yeun, C.Y.: The use of boolean functions in stream ciphers. In: 2011 International Conference for Internet Technology and Secured Transactions, pp. 29–33 (2011)

    work page 2011

  16. [16]

    In: 2007 IEEE International Symposium on Information Theory, pp

    Wei, Y., Hu, Y.: Maximum autocorrelation analysis of nonlinear combining func- tions in stream ciphers. In: 2007 IEEE International Symposium on Information Theory, pp. 176–180 (2007). https://doi.org/10.1109/ISIT.2007.4557083

    work page doi:10.1109/isit.2007.4557083 2007

  17. [17]

    In: Bellare, M

    Zhang, M., Chan, A.: Maximum correlation analysis of nonlinear s-boxes in stream ciphers. In: Bellare, M. (ed.) Advances in Cryptology — CRYPTO 2000, pp. 501–514. Springer, Berlin, Heidelberg (2000)

    work page 2000

  18. [18]

    Lecture Notes in Computer Science, vol

    Rueppel, R.A.: Linear Complexity and Random Sequences. Lecture Notes in Computer Science, vol. 219, pp. 167–188. Springer, - (1986)

    work page 1986

  19. [19]

    IEEE Transactions on Information Theory 33(1), 124–131 (1987) https://doi.org/10.1109/TIT.1987.1057268

    Rueppel, R.A., Staffelbach, O.J.: Products of linear recurring sequences with maximum complexity. IEEE Transactions on Information Theory 33(1), 124–131 (1987) https://doi.org/10.1109/TIT.1987.1057268

    work page doi:10.1109/tit.1987.1057268 1987

  20. [20]

    Procedia Computer Science 29, 2013–2023 (2014) https://doi.org/10.1016/ j.procs.2014.05.185

    F´ uster-Sabater, A.: Computation of filtering functions for cryptographic applica- tions. Procedia Computer Science 29, 2013–2023 (2014) https://doi.org/10.1016/ j.procs.2014.05.185

    work page 2013

  21. [21]

    Aegean Park Press, Laguna Hill, California (1982)

    Golomb, S.W.: Shift Register-Sequences. Aegean Park Press, Laguna Hill, California (1982)

    work page 1982

  22. [22]

    In: Zhou, J., Yung, M., Han, Y

    Chowdhury, S., Maitra, S.: Efficient software implementation of lfsr and boolean function and its application in nonlinear combiner model. In: Zhou, J., Yung, M., Han, Y. (eds.) Applied Cryptography and Network Security, pp. 387–402. Springer, Berlin, Heidelberg (2003)

    work page 2003

  23. [23]

    In: 2017 Annual Conference on New Trends in Information & Communications Technology Applications (NTICT), pp

    Sadkhan, S.B., Reza, D.M.: Investigation of the best structure for the nonlinear combining function. In: 2017 Annual Conference on New Trends in Information & Communications Technology Applications (NTICT), pp. 180–185 (2017). https: //doi.org/10.1109/NTICT.2017.7976126

    work page doi:10.1109/ntict.2017.7976126 2017

  24. [24]

    IEEE Transactions on Information Theory30(5), 776–780 (1984) https://doi.org/10.1109/TIT.1984.1056949

    Siegenthaler, T.: Correlation-immunity of nonlinear combining functions for cryp- tographic applications. IEEE Transactions on Information Theory30(5), 776–780 (1984) https://doi.org/10.1109/TIT.1984.1056949

    work page doi:10.1109/tit.1984.1056949 1984

  25. [25]

    Diploma thesis, Institut f¨ ur Mathematics, Universit¨ at Z¨ urich, Z¨ urich, Switzerland (2008) 32

    Wagner, U.: Detection and exploitation of small correlations in stream ciphers. Diploma thesis, Institut f¨ ur Mathematics, Universit¨ at Z¨ urich, Z¨ urich, Switzerland (2008) 32

    work page 2008

  26. [26]

    Complexity 2019, 1–13 (2019) https://doi.org/10.1155/2019/2108014

    Cardell, S.D., F´ uster-Sabater, A.: Binomial representation of cryptographic binary sequences and its relation to cellular automata. Complexity 2019, 1–13 (2019) https://doi.org/10.1155/2019/2108014

    work page doi:10.1155/2019/2108014 2019

  27. [27]

    Mathematics (8), 1–26 (2020) https://doi

    Cardell, S.D., Climent, J.-J., F´ uster-Sabater, A., Requena, V.: Representations of generalized self-shrunken sequences. Mathematics (8), 1–26 (2020) https://doi. org/10.3390/math8061006

    work page doi:10.3390/math8061006 2020

  28. [28]

    In: Helleseth, T., Jedwab, J

    Pirsic, G., Winterhof, A.: Boolean functions derived from pseudorandom binary sequences. In: Helleseth, T., Jedwab, J. (eds.) Sequences and Their Applications – SETA 2012, pp. 101–109. Springer, Berlin, Heidelberg (2012)

    work page 2012

  29. [29]

    Logic Journal of the IGPL 30(6), 993–1004 (2022) https://doi.org/10.1093/jigpal/jzac008

    Cardell, S.D., F´ uster-Sabater, A., Or´ ue, A.B., Requena, V.: Randomness study of the concatenation of generalized sequences. Logic Journal of the IGPL 30(6), 993–1004 (2022) https://doi.org/10.1093/jigpal/jzac008

    work page doi:10.1093/jigpal/jzac008 2022

  30. [30]

    IEEE Transactions on Information Theory 50(4), 714–719 (2004) https://doi.org/10.1109/TIT.2004

    Hu, Y., Xiao, G.: Generalized self-shrinking generator. IEEE Transactions on Information Theory 50(4), 714–719 (2004) https://doi.org/10.1109/TIT.2004. 825256

    work page doi:10.1109/tit.2004 2004

  31. [31]

    Journal of Universal Computer Science 4(8), 705–717 (1998)

    Olej´ ar, D., Stanek, M.: On cryptographic properties of random boolean functions. Journal of Universal Computer Science 4(8), 705–717 (1998)

    work page 1998

  32. [32]

    Lecture Notes in Computer Science 1746, 35–44 (1999)

    Pasalic, E., Johansson, T.: Further results on the relation between nonlinearity and resiliency for boolean functions. Lecture Notes in Computer Science 1746, 35–44 (1999)

    work page 1999

  33. [33]

    theory of m¨ obius functions

    Rota, G.C.: On the foundations of combinatorial theory i. theory of m¨ obius functions. Probability Theory and Related Fields 2(4), 340–368 (1964)

    work page 1964

  34. [34]

    International Journal of Computer Mathematics 88(7), 1398–1416 (2011)

    Pieprzyk, J., Wang, H., Zhang, X.M.: M¨ obius transforms, coincident boolean func- tions and non-coincidence property of boolean functions. International Journal of Computer Mathematics 88(7), 1398–1416 (2011)

    work page 2011

  35. [35]

    Mathematics 10(5), 794–816 (2022) https://doi.org/10.3390/math10050794

    F´ uster-Sabater, A., Requena, V., Cardell, S.D.: An efficient algorithm to compute the linear complexity of binary sequences. Mathematics 10(5), 794–816 (2022) https://doi.org/10.3390/math10050794

    work page doi:10.3390/math10050794 2022

  36. [36]

    In: Groen, D., Mulatier, C., Paszynski, M., Krzhizhanovskaya, V.V., Dongarra, J.J., Sloot, P.M.A

    F´ uster-Sabater, A., Requena, V., Cardell, S.D.: A Hadamard Matrix-Based Algo- rithm to Evaluate the Strength of Binary Sequences. In: Groen, D., Mulatier, C., Paszynski, M., Krzhizhanovskaya, V.V., Dongarra, J.J., Sloot, P.M.A. (eds.) Computational Science – ICCS 2022, pp. 139–145. Springer, - (2022). https: //doi.org/10.1007/978-3-031-08754-7 19

    work page doi:10.1007/978-3-031-08754-7 2022

  37. [37]

    In: ISITA/ISSSTA 2010 - 2010 International Sympo- sium on Information Theory and Its Applications, pp

    Climent, J.-J., Garc´ ıa, F.J., Requena, V.: Computing the degree of a boolean function from its support. In: ISITA/ISSSTA 2010 - 2010 International Sympo- sium on Information Theory and Its Applications, pp. 123–128 (2010). https: 33 //doi.org/10.1109/ISITA.2010.5649426

    work page doi:10.1109/isita.2010.5649426 2010

  38. [38]

    RACSAM 114(79) (2020) https://doi.org/10.1007/ s13398-020-00807-5

    F´ uster-Sabater, A., Cardell, S.D.: Linear complexity of generalized sequences by comparison of pn-sequences. RACSAM 114(79) (2020) https://doi.org/10.1007/ s13398-020-00807-5

    work page 2020

  39. [39]

    IEEE Transactions on Information Theory 45(6), 2073–2077 (1999) https://doi.org/10

    Blackburn, S.R.: The linear complexity of the self-shrinking generator. IEEE Transactions on Information Theory 45(6), 2073–2077 (1999) https://doi.org/10. 1109/18.782139

    work page 2073

  40. [40]

    Journal of Combinatorial Theory, Series A 76, 55–82 (1996) 34

    Blackburn, S.R., Etzion, T., Paterson, K.G.: Permutation polynomials, de bruijn sequences and linear complexity. Journal of Combinatorial Theory, Series A 76, 55–82 (1996) 34

    work page 1996