CS Paper Radar

On cryptographically non-linear all-or-nothing transforms

Anantajeet Devaraj, Navid Nasr Esfahani

cs.CR ·submitted 2026-11-12 17:00 UTC · v1
unusual

Abstract

An unconditionally secure $(t, s, v)$-all-or-nothing transform (AONT) is a bijection from $s$ input elements to $s$ output elements over an alphabet of size $v$, such that given any $s - t$ output elements, no information can be obtained about any $t$ input elements. While linear AONTs have been extensively studied, comparatively little is known about the existence of non-linear AONTs. In this paper, we investigate unconditionally secure cryptographically non-linear $(t, s, v)$-AONTs, distinguishing between non-additivity, non-affinity, and cryptographic non-linearity. To achieve this, we first present a computational method for enumerating general AONTs focusing on the case $(t, 3, 3)$-AONTs for $t = 1 and 2$, establishing the existence of non-additive AONTs. We then introduce a general construction of non-additive AONTs from linear ones using coordinate-wise symbol permutations. We measure the non-linearity of the AONT instances generated from this construction, using differential $Δ_F$-uniformity and Walsh magnitude. Finally, we establish theoretical conditions under which $Δ_F$-uniformity is reduced and present statistical results examining the non-linearity of AONTs obtained through our construction.

Closest papers

Nearest neighbours by meaning across the whole index.

Multi-sequences with large linear and error linear complexity from function fields

cs.IT ·2026-09-15 ·Xubin Hu, Shu Liu, Liming Ma, Chaoping Xing
theory similarity 0.58
Abstract · 21 pages

The linear complexity and the error linear complexity of multi-sequences are measures for security in stream ciphers. In this manuscript, we present a general framework for constructing periodic multi-sequences via function fields. We prove that the constructed multi-sequences possess both large linear complexity and large error linear complexity. We apply this framework of constructing multi-sequences to various maximal function fields and we obtain many new multi-sequences with various lengths and dimensions. As a byproduct, we adopt this idea and produce many new quasi-cyclic algebraic geometric codes as well.

0.38

A generalization of the map $χ$

cs.IT ·2026-09-17 ·Xiutao Feng, Qiang Wang, Jingyi Yu, Anpeng Zhang
similarity 0.57
Abstract · added a few remarks

The mapping $ χ_n:\mathbb{F}_2^n \to \mathbb{F}_2^n$ defined by $y=χ_n(x)$ with $y_i = x_i + x_{i+1}x_{i+2} + x_{i+2}$, where the indices are computed modulo $n$, has been widely studied for its application in lightweight cryptography. In this paper, we generalize this mapping and completely characterize all these shift-invariant permutations of the form $y_i=x_{i+u}+x_{i+v}(x_{i+w}+a_i)$, where $0\le u, v, w<n$ and $a_i\in \mathbb{F}_2$, $1\le i\le n$. We also determine their compositional inverses explicitly.

0.37

Algorithms for Sampling Self-Orthogonal and Totally Self-Orthogonal Codes in Odd Characteristic

cs.IT ·2026-10-06 ·Martin R. Albrecht, Benjamin Benčina, Russell W. F. Lai
position similarity 0.57
Abstract

We give an algorithm that samples uniformly random linear codes of any hull dimension and type over finite fields of odd characteristic, implying the first algorithm for sampling uniformly random self-orthogonal codes of any rate, including self-dual codes. Our algorithm is a re-visitation of the algorithm given by Albrecht, Benčina and Lai (EC'25), using the mass formulae proven by Li, Shi and Ling (IEEE Trans. Inf. Theory 71(1)). This allows us to instantiate code-based cryptographic schemes that rely on the hardness of Permutation Code Equivalence (PCE) on `random' self-dual codes for security and that were previously unable to sample them. Building on the observation by Bardet, Otmani and Saeed-Taha (ISIT'19) that Euclidean orthogonality is insufficient when considering PCE over finite extension fields due to non-trivial Galois automorphisms, we study the behaviour of what we call total orthogonality, that is orthogonality with respect to all induced Galois geometries simultaneously. We characterise total orthogonality of vectors and codes, and give an algorithm that samples linear codes with a total hull of a prescribed dimension; a subcode that acts as the hull in all Galois geometries of the ambient space. The algorithm incurs a rate decrease by a factor equal to the extension degree, however, we argue why this may be necessary in the context of PCE and explore how it limits the practicality of our algorithm. We consider the notion of Galois type of a linear code when Galois hulls are symmetric and show that all linear codes have constant Hermitian type.

0.43

Shift-Invariant Permutations with Polynomial Composition: Construction and Algebraic Structure

cs.IT ·2026-09-25 ·Cheng Lyu, Dabin Zheng, Mu Yuan, Lei Hu
theory similarity 0.55
Abstract

Shift-invariant permutations of $\mathbb F_2^n$ are particularly attractive in symmetric cryptography because of their regularity and implementation efficiency. Constructing such permutations with an explicit algebraic structure remains a challenging problem. In this paper, we study a family of shift-invariant transformations of $\mathbb F_2^n$ constructed from a recursively defined sequence of mappings $\{γ_j\}_{j\ge 0}$ associated with landscapes. First, we prove that, under an explicit dimension condition relating $n$ to the support of the landscape, the sequence $\{γ_j\}_{j\ge 0}$ has the polynomial composition property if and only if the corresponding landscape is quasi-conserved on $\mathbb F_2^n$ with a nonzero special index. Then, we determine the eventual zero or periodic behavior of $\{γ_j\}_{j\ge0}$, including the exact index at which the sequence either first vanishes or becomes periodic, together with the least eventual period, and establish linear independence until the first linear relation occurs. When the polynomial composition property holds, we establish an explicit isomorphism between the group of permutation elements in the monoid generated by these mappings and the unit group of a quotient ring $\mathbb F_2[z]/\langle p(z)\rangle$, where $p(z)$ is a monomial or a binomial determined by the landscape. This framework reduces the tasks of testing bijectivity, computing iterates, and determining compositional inverses and orders of permutation elements to polynomial computations. Finally, we apply the results to mappings represented by binomials and trinomials in the quotient ring, obtaining explicit criteria and formulas, and tabulate more than one hundred representative constructions of shift-invariant permutations, recovering and unifying several previously studied families.

0.07

Rational Identity Testing for Noncommutative Circuits is in Polynomial Space

cs.CC ·2026-09-29 ·V. Arvind, Pushkar S. Joglekar
publishedtheory similarity 0.55
Abstract

The rational identity testing problem, RIT, asks whether an input \emph{rational circuit}, computes the zero element of the free skew field. For rational \emph{formulas} the problem is known to be in deterministic polynomial time. For rational circuits of size $s$ the associated linear pencil has dimension $2^{O(s)}$, and the known algorithms use exponential time and exponential space. We show that RIT for rational circuits over $Q$ and finite fields is in PSPACE. As a consequence, noncommutative PIT for degree unrestricted noncommutative circuits is also in PSPACE. The proof is based on the following three observations Analyzing the Hrubes-Wigderson construction of a linear pencil for an input rational formula, we obtain a succinctly represented linear pencil $A$ of size $2^{O(s)}$ for the input rational \emph{circuit} of size $s$. More precisely, given indices $i$ and $j$ for the linear pencil we can compute $A_{i,j}$ in space polynomial in $s$ and length of $i,j$. This algorithm essentially gives a succinct presentation of the linear pencil $A$ obtained by the reduction. By the recent theorem of Chatterjee, Ghosh, Gurjar, Raj and Thierauf that deciding whether a symbolic matrix $\sum_i A_ix_i$ has full noncommutative rank is in NC. We note that their algorithm is logspace-uniform NC and we use it as a black-box for computing rank of succinctly represented pencil $A$. Finally, we note a folklore simulation: If a problem is solved by a logspace-uniform family of \emph{deterministic} Boolean circuits of polylogarithmic depth, and its input is not written down but is presented by a polylogspace subroutine that returns any requested input bit, then the circuit can be evaluated in polylogarithmic space. Hence, simulating a depth $O(\log^{i}M)$ circuit for succinctly presented inputs of length $M = 2^{Θ(s)}$ yields a polynomial space algorithm.

0.63

Construction of Ternary Minimal Linear Codes with Dimension $n+r$ Via Index Codes and The Access Structures of Their Dual Codes

cs.IT ·2026-11-18 ·Haibo Liu, Qunying Liao
similarity 0.55
Abstract

Recently, minimal linear codes have been extensively studied due to their applications in secret sharing schemes, secure two-party computations, and so on. Constructing minimal linear codes violating the Ashikhmin-Barg condition and then determining their weight distributions have been interesting in coding theory and cryptography. In this paper, we present a general construction of ternary linear codes of dimension $n+r$, where $n$ and $r$ are positive integers, and derive a necessary and sufficient condition for the resulting codes to be minimal. We first specialize the construction using index codes arising from spreads, with three classes of index codes satisfying the minimality condition, we obtain the parameters and weight enumerators of the corresponding minimal codes, and determine the access structures type of the secret-sharing schemes based on their dual codes. By the index codes from Krawtchouk polynomials, we then give a second specialization of the construction, with a class of index codes satisfying the minimality condition, we obtain the parameters of the resulting minimal codes, and determine the access-structure type of the secret-sharing scheme based on each dual code. Several constructed families of minimal codes violate the Ashikhmin-Barg condition.

0.19

Equivalent Non-linear Shift Register Transformations and Espresso

cs.CR ·2026-10-18 ·Anirban Ghatak, Kaushik Sarkar, Anupam Chattopadhyay, Ambrish Awasthi, Indivar Gupta
unusual similarity 0.54
Abstract

The stream cipher Espresso was designed by E. Dubrova and M. Hell as a hardware-efficient candidate for 5G security. It has two components - a 256-bit binary non-linear feedback shift register (NFSR), with 14 feedback taps, and a 20-variable non-linear output function. However, the security of Espresso with regard to several standard cryptanalytic attacks are estimated using an alternate NFSR, which has only two feedback taps. The above analysis is based on the claim that this alternate NFSR is obtained using a transformation algorithm which preserves the output sequence of the original NFSR. This issue has become all the more significant in the light of recent results on hardware performance evaluations, which assume that the stated equivalence holds. This article presents the first successful attempt in settling the above question of Espresso NFSR equivalence. We arrive at our main result by a careful analysis of existing transformation methods relevant to the question. In doing so, we first identify and correct a critical flaw in the proof of a foundational result of E. Dubrova. Next, in the context of Espresso equivalence, we analyze and unify the transformation framework of Dubrova and the one proposed by Yao and Parampalli. Based on our analysis, we have succeeded in transforming the LFSR in an Espresso-equivalent design reported by Yao and Parampalli to the Espresso alternate NFSR. Further, we have obtained a corresponding non-linear output function which achieves output-equivalence with the LFSR design, and hence, with Espresso.

0.25

Linear Self-Symmetries of Inverse-Based S-boxes: Generic Rigidity and Applications

cs.CR ·2026-10-21 ·Zheng Zhang, Na Zhang
similarity 0.54
Abstract

Finite-field inversion is a basic nonlinear building block in the design of S-boxes for symmetric cryptography. In inverse-based S-boxes, finite-field inversion is often combined with linear or affine layers that may preserve or destroy algebraic symmetries of the inverse function. We study how often nontrivial linear self-symmetries remain as the outer invertible linear transformation varies over \(GL_n(\mathbb F_2)\). Using the classification of two-sided linear equivalences of inversion, we reduce the problem to semilinear conjugacy and centralizer estimates. We obtain matching upper and lower bounds for the probability that a nontrivial linear self-symmetry remains, and these bounds determine its leading quadratic exponent. This exponent is governed by the smallest prime divisor of the extension degree. Thus the decay rate depends on the arithmetic of the field extension and not only on its dimension. As cryptographic applications, we provide a practical rigidity criterion, prove that the full AES S-box has no nontrivial linear self-symmetry, and illustrate the broader relevance of the framework through ARIA and Vision.

0.11