Linearization of nonlinear filter generators and its application to cryptanalysis of stream ciphers

Nonlinear filter generators are commonly used as keystream generators in stream ciphers. A nonlinear filter generator utilizes a nonlinear filtering function to combine the outputs of a linear feedback shift register (LFSR) to improve the linear complexity of keystream sequences. However, the LFSR-based stream ciphers are still potentially vulnerable to algebraic attacks that recover the key from some keystream bits. Although the known algebraic attacks only require polynomial time complexity of computations, all have their own constraints. This paper uses the linearization of nonlinear filter generators to cryptanalyze LFSR-based stream ciphers. Such a method works for any nonlinear filter generators. Viewing a nonlinear filter generator as a Boolean network that evolves as an automaton through Boolean functions, we first give its linearization representation. Compared to the linearization representation in Limniotis et al. (2008), this representation requires lower spatial complexity of computations in most cases. Based on the representation, the key recoverability is analyzed via the observability of Boolean networks. An algorithm for key recovery is given as well. Compared to the exhaustive search to recover the key, using this linearization representation requires lower time complexity of computations, though it leads to exponential time complexity.     

Linear hulls with correlation zero and linear cryptanalysis of block ciphers

Linear cryptanalysis, along with differential cryptanalysis, is an important tool to evaluate the security of block ciphers. This work introduces a novel extension of linear cryptanalysis: zero-correlation linear cryptanalysis, a technique applicable to many block cipher constructions. It is based on linear approximations with a correlation value of exactly zero. For a permutation on n bits, an algorithm of complexity 2 ^n-1 is proposed for the exact evaluation of correlation. Non-trivial zero-correlation linear approximations are demonstrated for various block cipher structures including AES, balanced Feistel networks, Skipjack, CLEFIA, and CAST256. As an example, using the zero-correlation linear cryptanalysis, a key-recovery attack is shown on 6 rounds of AES-192 and AES-256 as well as 13 rounds of CLEFIA-256.     

Interior and exterior functions of positive Boolean functions

The interior and exterior functions of a Boolean function f were introduced in Makino and Ibaraki (Discrete Appl. Math. 69 (1996) 209–231), as stability (or robustness) measures of the f. In this paper, we investigate the complexity of two problems -INTERIOR and -EXTERIOR, introduced therein. We first answer the question about the complexity of -INTERIOR left open in Makino and Ibaraki (Discrete Appl. Math. 69 (1996) 209–231); it has no polynomial total time algorithm even if is bounded by a constant, unless P=NP. However, for positive h-term DNF functions with h bounded by a constant, problems -INTERIOR and -EXTERIOR can be solved in (input) polynomial time and polynomial delay, respectively. Furthermore, for positive k-DNF functions, -INTERIOR for two cases in which k=1, and and k are both bounded by a constant, can be solved in polynomial delay and in polynomial time, respectively.     

Generic results in classes of ultradifferentiable functions

Let E be a Denjoy–Carleman class of ultradifferentiable functions of Beurling type on the real line that strictly contains another class F of Roumieu type. We show that the set S of functions in E that are nowhere in the class F   is large in the topological sense (it is residual), in the measure theoretic sense (it is prevalent), and that S∪{0}$S\cup \{0\}$ contains an infinite dimensional linear subspace (it is lineable). Consequences for the Gevrey classes are given. Similar results are also obtained for classes of ultradifferentiable functions defined imposing conditions on the Fourier–Laplace transform of the function.     

Binary terms in polynomial representations of Boolean functions

Polynomial representations of Boolean functions by binary terms are considered. The construction of terms involves variables and residual functions. Special cases of such representations are the decomposition of a function with respect to variables, Zhegalkin polynomials, and representations of functions as sums of conjunctions of residual functions.     

Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem

Recently, the first author introduced some cryptographic functions closely related to the Diffie-Hellman problem called P-Diffie-Hellman functions. We show that the existence of a low-degree polynomial representing a P-Diffie-Hellman function on a large set would lead to an efficient algorithm for solving the Diffie-Hellman problem. Motivated by this result we prove lower bounds on the degree of such interpolation polynomials. Analogously, we introduce a class of functions related to the discrete logarithm and show similar reduction and interpolation results.     

Exclusive and essential sets of implicates of Boolean functions

In this paper we study relationships between CNF representations of a given Boolean function f and certain sets of implicates of f. We introduce two definitions of sets of implicates which are both based on the properties of resolution. The first type of sets, called exclusive sets of implicates, is shown to have a functional property useful for decompositions. The second type of sets, called essential sets of implicates, is proved to possess an orthogonality property, which implies that every CNF representation and every essential set must intersect. The latter property then leads to an interesting question, to which we give an affirmative answer for some special subclasses of Horn Boolean functions.     

Complexity and depth of formulas for symmetric Boolean functions

A new approach for implementation of the counting function for a Boolean set is proposed. The approach is based on approximate calculation of sums. Using this approach, new upper bounds for the size and depth of symmetric functions over the basis B₂ of all dyadic functions and over the standard basis B₀ = {∧, ∨,^- } were non-constructively obtained. In particular, the depth of multiplication of n-bit binary numbers is asymptotically estimated from above by 4.02 log₂n relative to the basis B₂ and by 5.14log₂n relative to the basis B₀.     

Incomparable integrals and approximate calculation of monotone Boolean functions

The number of incomparable k-dimensional intervals in the Boolean n-cube is estimated. The result is used to estimate the complexity of approximate computation of an arbitrary monotone Boolean function of n variables.     

Noise sensitivity of Boolean functions and applications to percolation

It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the configuration with an arbitrary small percent of random errors gives almost no prediction whether the event occurs. On the other hand, weighted majority functions are shown to be noise-stable. Several necessary and sufficient conditions for noise sensitivity and stability are given. Consider, for example, bond percolation on ann+1 byn grid. A configuration is a function that assigns to every edge the value 0 or 1. Let ω be a random configuration, selected according to the uniform measure. A crossing is a path that joins the left and right sides of the rectangle, and consists entirely of edges ℓ with ω(ℓ)=1. By duality, the probability for having a crossing is 1/2. Fix an ɛ ∈ (0, 1). For each edge ℓ, let ω′(ℓ)=ω(ℓ) with probability 1 − ɛ, and ω′(ℓ)=1 − ω(ℓ) with probability ɛ, independently of the other edges. Letp(τ) be the probability for having a crossing in ω, conditioned on ω′ = τ. Then for alln sufficiently large,P{τ : |p(τ) − 1/2| > ɛ}<ɛ.     

Laced Boolean functions and subset sum problems in finite fields

In this paper, we investigate some algebraic and combinatorial properties of a special Boolean function on n variables, defined using weighted sums in the residue ring modulo the least prime p≥n. We also give further evidence relating to a question raised by Shparlinski regarding this function, by computing accurately the Boolean sensitivity, thus settling the question for prime number values p=n. Finally, we propose a generalization of these functions, which we call laced functions, and compute the weight of one such, for every value of n.     

Boolean algebras of lattice uniformities and decompositions of modular functions

We study decomposition theorems for modular functions on lattices and the relationship between such decompositions and lattice properties of a suitable system of uniformities. We give a purely topological characterization for the validity of a decomposition theorem of a certain type and examine when this topological condition is satisfied, namely when a system of lattice uniformities is a Boolean algebra consisting of permutable uniformities.      

Composition of Post classes and normal forms of Boolean functions

The class composition C°K of Boolean clones, being the set of composite functions f(g₁,…,g_n) with f∈C, g₁,…,g_n∈K, is investigated. This composition C°K is either the join C∨K in the Post Lattice or it is not a clone, and all pairs of clones C,K are classified accordingly.Factorizations of the clone Ω of all Boolean functions as a composition of minimal clones are described and seen to correspond to normal form representations of Boolean functions. The median normal form, arising from the factorization of Ω with the clone SM of self-dual monotone functions as the leftmost composition factor, is compared in terms of complexity with the well-known DNF, CNF, and Zhegalkin (Reed-Muller) polynomial representations, and it is shown to provide a more efficient normal form representation.     

Diagnostic tests for local coalescences of variables in Boolean functions

The article studies diagnostic tests for local k -fold coalescences of variables in Boolean functions f( [(x)\tilde]ⁿ )( 1 ￡ k ￡ n,  1 ￡ t ￡ 2^2k ) f\left( {{{\tilde{x}}^n}} \right)\left( {1 \leq k \leq n,\;1 \leq t \leq {2^{{2^k}}}} \right) . Upper and lower bounds are proved for the Shannon function of the length of the diagnostic test for local k -fold coalescences generated by the system of functions F_t^k \Phi_t^k . The Shannon function of the length of a complete diagnostic test for local k -fold coalescences behaves asymptotically as 2 ^k (n − k + 1) for n → ∞, k → ∞.