Abstract
Symmetric Boolean functions play a key role in stream ciphers. Symmetric constructions provide core components in cryptographic applications. In this chapter, four meta symmetric clustering schemes (combination, crossing, variant and rotation) are organized in a hierarchy for n variables of 0–1 vectors in measuring phase spaces. Local counting properties in a cluster and global counting properties in a given level are formulated. From selected symmetric clusters, a number of various symmetric Boolean functions are formulated. Counting properties on symmetric clusters, vectors in selected clusters and special symmetric Boolean functions are listed. Four sets of symmetric Boolean functions are compared. Properties of symmetric clusters and Boolean functions are discussed. Main results are expressed in theorems and tables. Among four meta schemes, the variant scheme presents novel properties approximately with \(O\left( n^2/4\right) \) clusters on a 2D phase space different from other schemes: combinatorial \(O\left( n\right) \), crossing \(O\left( n/2\right) \) and rotation \(O\left( 2^n/n\right) \) on 1D measuring phase spaces, respectively. The variant pseudorandom number generator is a similar approach on RC4 and HC128 stream ciphers using word-oriented 0–1 vectors. Further advanced researches and explorations on relevant optimal configurations are required.
This work was supported by the Key Project on Electric Information and Next Generation IT Technology of Yunnan (2018ZI002), NSF of China (61362014), Yunnan Advanced Overseas Scholar Project.
You have full access to this open access chapter, Download chapter PDF
Similar content being viewed by others
Keywords
1 Introduction
Symmetric Boolean functions [5] have being widely used as components of different cryptosystems [25] (e.g. in stream ciphers, block ciphers or hash functions). In combinatorial mathematics [10], a symmetric Boolean function is a Boolean function whose value does not depend on the permutation of its input bits [4], i.e. it depends only on the number of ones in the input on n variables of 0–1 vectors [21]. A total of \(2^{n}\) vectors are composed of a vector space or a phase space for the construction [19]. For a specific symmetric Boolean function, it is necessary to have invariant properties undertaken a special group of permutations [18]. For example, rotation symmetric Boolean functions are invariant under the circular translation of indices. In addition to rotation symmetric properties, multiple invariants (combination, crossing, reflection, translation) may be composed of various symmetric subgroups of permutations [10, 22]. Various combinatorial counting schemes are explored [34,35,36].
1.1 Symmetric Functions—Combinatorial Invariant
From a combinatorial viewpoint, symmetric Boolean functions are a combinatorial invariant that links to the number of one elements \(p, 0\le p \le n\) in a vector [35]. In combinatorics, this type of function has being linked to binomial coefficients, and normally, there are \(n+1\) partitions to distinct the parameter of a measuring phase space into various clusters [30]. Symmetric Boolean functions are characterized [36] by the fact that their outputs only depend on the p numbers of their inputs. The usefulness of symmetric functions in a cryptographic context has being widely explored which possess good cryptographic properties [6, 7].
1.2 Crossing Number - Topological Invariant
A zero-crossing [23] describes a point where the sign of a mathematical function changes (e.g. from positive to negative), represented by a crossing of the axis (zero value) in the graph of the function. It is a commonly used term in electronics, mathematics, sound and image processing.
From a measuring viewpoint, a 0–1 vector with n bits can be expressed as a circular ring that has a fixed crossing number \(q, 0\le q \le \lfloor \frac{n}{2} \rfloor \) distinguished a number of derivative changes on either 0–1 or 1–0, respectively. This type of derivative invariant is widely used in crypto-analysis for many years. In NIST random data testing packages [1], binary derivative [3] and Runs tests [2] play an important role to measure the randomness of a binary sequence formed by a pseudorandom number generator for use in cipher systems. From an analytic viewpoint, this parameter is a topological invariant and different from a combinatorial invariant to provide another type of partition capacities to organize a set of clusters in a measuring phase space.
1.3 Rotation Symmetric Functions - Geometric Invariant
In combinatorial mathematics, rotation symmetric properties are widely explored from early stage of abstract group theories and symmetric group constructions [10, 22] as a geometric invariant. Filiol and Fontaine [12] were initially explored on balanced Boolean functions with a good correlation immunity. Pieprzyk and Qu [26] were applied in crypto-applications to use Rotation Symmetric Boolean Functions (RSBF) as components in the rounds of a hashing algorithm.
Extensive R&D activities on RSBF are continuous for last decades, a list of advanced works explored, such as degree and non-linearity [6], optimal algebraic immunity [7], bent and semi-bent functions [8, 33], non-linearity of resilient, non-linear Boolean functions [20, 28], balanced Boolean functions [12, 16], non-linear balanced Boolean functions [31], weights and non-linearity [11], immune combining functions [32], count and cryptographic properties [13, 29], etc.
1.4 Trinomial Coefficients
It is a natural approach [10, 18, 19] to apply binomial coefficients to partition a measuring phase space on 0–1 vector sets. However, when parameters increase more than three, a generalization [34,35,36] using multinomial coefficients may not provide a general solution on further refined partitions, if the processed phase space is composed of 0–1 vectors. It is convenient for us to use a trinomial expression to show this fact.
Let \(n = n_{1} + n_{2} + n_{3}, 0 < n,\)
collecting all possible trinomial coefficients, we have
From Eq. 1, it is interesting to notice that trinomial coefficients provide further segments to partition three-valued 0–2 vectors. Due to this reason, extensions using multinomial coefficients may not be directly relevant to binary-valued 0–1 vector sets. Refined identity equations of combinatorics are required [14, 15].
1.5 Variant Symmetric Schemes - Variant Invariants
Various schemes to use multiple invariants to partition special phase spaces have being explored in binary image analysis and processing for many years. In 1990s, Zheng [39, 40] proposed conjugate classifications to apply seven invariants in a hierarchy to partition the kernels of four regular plane lattices on \(n=\{4,5,7,9\}\) cases for 2D binary images. For n-tuple 0–1 vectors, variant logic frameworks [41, 42] are proposed in 2010s, various applications are explored, such as 3D visual method [37], variant Pseudorandom Number Generator (PRNG) [38, 43], computational simulation on quantum interactions [44,45,46,47] and non-coding DNA analysis [48,49,50].
1.6 Organization of the Chapter
In this chapter, an algebraic equation of variant trinomial will be proposed as a kernel structure to arrange a hierarchical phase space. This extension provides a general framework of multiple symmetric operations to support three numeric numbers: combinatorial, crossing and variant in a hierarchy. Three meta clusters of measuring phase spaces are identified by the three invariants: \(\{n,p,q\}\) and their combinations. Refined levels can be compared with the rotation symmetric scheme under \(n=\{1,2,3,4,5\}\) conditions. Similarities and differences among the four schemes are explored.
In Sect. 2, symbols and local counting properties of symmetric clusters in measuring spaces are defined, algebraic equations are formulated and two important projections are discussed. In Sect. 3, variant symmetric clusters and their elementary equation are proposed. In Sect. 4, four number sets of symmetric clusters are explored from a global viewpoint. In Sect. 5, symmetric Boolean functions of selected clusters are constructed and both algebraic and approximate numeric properties are discussed. In Sect. 6, cryptographic properties of symmetric Boolean functions in a hierarchy are discussed and special properties on the variant scheme are stressed. Section 7 is the conclusion of the chapter. Main results of the chapter are expressed in a list of theorems and corollaries in Sects. 2–5, respectively.
2 Symmetric Clusters in Measuring Phase Spaces
In this section, basic symbols, primary definitions and algebraic formulas are defined for different clusters in their measuring phase spaces.
2.1 Basic Symbols
Main symbols in this chapter are listed in Table 1.
2.2 Primary Definitions
Definition 1
(x an n-tuple vector on 0–1 variables) Let x be a 0–1 vector with n length.
e.g. \(x=110010, n=6\).
Definition 2
(I index for a vector x) For a vector x, let I or I(x) be an index:
e.g. \(x=110010, I(x) = 2^5 + 2^4 + 2 =32+16+2 = 50\).
Definition 3
(\(\varOmega (n)\) a full set of n-tuple 0–1 vectors) Let \(\varOmega (n)\) be a vector space or a phase space of all n-tuple 0–1 vectors,
Definition 4
Let \(f_{\varOmega }(n)\) denote a number of vectors in \(\varOmega (n)\).
Lemma 1
\(f_{\varOmega }(n)\) is equal to \(2^n\).
Proof
For a vector \(x\in B_{2}^{n}\) from \(0\ldots 0\) to \(1\ldots 1\), its index I can cover a full region of \(0\le I < 2^{n}\), so \(\varOmega (n)\) contains \(2^n\) distinct vectors and \(f_{\varOmega }(n)=2^n\).
Definition 5
(Measuring Phase Space) If a phase space can be organized by various invariants, then it is a measuring phase space and its dimension is determined by a number of active invariants.
Corollary 1
For any \(n>0\), \(\varOmega (n)\) is a measuring phase space in zero dimension.
Proof
For any \(n>0\), \(\varOmega (n)\) is composed of one cluster of vectors as a single point.
Definition 6
(R rotation operator) Let R(x; r) be a rotation operator on a vector x rotation \(-n< r <n\) positions:
e.g. \(x=110010, \{R(x;r)\}_{r=0}^{5} = \{110010,100101,001011,010110,101100,011001\}\) with six distinct vectors.
Lemma 2
(Maximal cyclic structure) Initially from any vector x under a rotation operator, at most n distinct vectors will be distinguished under the rotation operator.
Proof
From any x, a set of \(\{R(x;r)\}_{r=0}^{n-1}\) with n vectors can be generated. If the listed set of n vector sequences contains more than one cycle, then the number of distinct vectors will be less than n.
For example, \(x=110110, \{R(x;r)\}_{r=0}^{5} = \{110110,101101,011011,110110,101101,011011\}\) with only a set of three distinct vectors: \(\{110110,101101,011011\}\).
Definition 7
(F reflection operator) Let F(x) be a reflect operator,
Lemma 3
(A pair of reflections) For any vector x, only two results are distinguished under F(x) operation: (1) \(F(x)=x\); (2) \(F(x)\ne x\).
Proof
(1) If \(F(x)=x\), then the values of the vector x are distributed as a central symmetric form; (2) if \(F(x)\ne x\), then the vector x does not have a symmetric distribution.
For example, \(x=110010,F(x)=010011\); \(y=110011,F(y)=110011\).
Definition 8
(p number of one elements) Let p or p(x) be a number of one elements in x,
For example, \(x=110010,p(x)=3\); \(y=110011,p(y)=4\).
Definition 9
(q number of cyclic crossings) Let q or q(x) be a number of cyclic crossings either 0–1 or 1–0 in a vector x,
For example, \(x=110010,q(x)=2\); \(y=110011,q(y)=1\).
2.3 Counting Properties on Rotation Clusters
Definition 10
(G(m, n) m-th rotation symmetric cluster) Let G(m, n) be an m-th rotation symmetric cluster of vectors, \(G(m,n)=\varOmega (n|m) \subset \varOmega (n)\) in \(\varOmega (n)\), and let a total number of rotation symmetric clusters be \(C_G(n)\), \(1\le m \le C_G(n)\),
Corollary 2
A set of \(\{G(m,n)\}_{m=1}^{C_G(n)}\) is composed of a measuring phase space in one dimension.
Proof
Using the parameter m, \(\{G(m,n)\}_{m=1}^{C_G(n)}\) can be listed in a linear order.
Lemma 4
By Burnside’s lemma, \(\phi \) being Euler’s phi-function,
Proof
A brief proof of this lemma can be found in [29].
Definition 11
Let \(f_G(m,n)\) denote a number of vectors in the m-th cluster G(m, n).
Corollary 3
For any \(f_G(m,n)\), \(1\le f_G(m,n) \le n\).
Proof
Due to Lemma 2, each \(f_G(m,n)\le n\) in general; for two special vectors in \(\{0\ldots 0, 1\ldots 1\}\), we have \(f_G(m,n)=1\).
Corollary 4
Collecting all possible rotation clusters, the total number of vectors is equal to \(f_{\varOmega }(n)\)
Proof
From Lemma 4 and Corollary 3, it contains a full set of \(2^n\) vectors in \(\varOmega (n)\).
Lemma 5
For a given n, \(C_G(n)\) has an approximate number,
Proof
Using Corollaries 3 and 4, each distinct cluster contains at most n vectors; it is a natural to have such an approximate number in enumeration.
It is convenient to list defined rotation parameters in Table 2 for \(n=4\) condition.
2.4 Counting Properties on Measuring Phase Spaces
For any vector \(x \in \varOmega (n)\), three measuring parameters \(\{n,p,q\}\) are represented as three invariants. Three measurements transfer a phase space into a set of measuring phase spaces in a hierarchy.
Definition 12
(L(p, n) combinatorial cluster) Let L(p, n) be a combinatorial cluster of vectors in \(\varOmega (n), L(p,n)=\varOmega (n|p) \subset \varOmega (n)\). Two parameters \(\{n,p\}\) partition the phase space \(\varOmega (n)\) to form a set of clusters \(\{L(p,n)\}\) in a measuring phase space.
Corollary 5
A set of \(\{L(p,n)\}_{p=0}^{n}\) is composed of a measuring phase space in one dimension.
Proof
The parameter p is the active invariant to arrange the phase space in a linear order.
Definition 13
Let \(C_L(n)\) be a number of clusters in \(\forall p,\{L(p,n)\}\).
Lemma 6
For a given n,
Proof
Using Definition 12, \(0\le p \le n\) and for any p, \(L(p,n) \ne \emptyset \), the parameter p partitions the whole set \(\varOmega (n)\) into \(n+1\) distinct subsets as clusters.
Definition 14
(\(f_L(p,n)\) combinatorial number) Let \(f_L(p,n)\) be a combinatorial number of vectors in a cluster L(p, n).
Lemma 7
For a pair of \(\{n,p\}\) parameters,
Proof
Using Definition 12, this number is equal to a binomial coefficient selected p elements from n positions.
It is convenient to list defined measuring parameters in Table 3 for \(n=4\) condition.
Definition 15
(E(q, n) crossing cluster of vectors) Let E(q, n) be a crossing cluster of vectors in \(\varOmega (n)\), \(E(q,n)=\varOmega (n|q) \subset \varOmega (n)\). Two parameters \(\{n,q\}\) partition the phase space \(\varOmega (n)\) to form a set of clusters \(\{E(q,n)\}\) in a measuring phase space.
Corollary 6
A set of \(\{E(q,n)\}_{q=0}^{\lfloor n/2 \rfloor }\) is composed of a measuring phase space in one dimension.
Proof
The parameter q is the active invariant to arrange the phase space in a linear order.
Definition 16
Let \(C_E(n)\) be a number of crossing clusters in \(\forall q, \{E(q,n)\} \).
Lemma 8
For a given \(n>0\),
Proof
According to Definition 15 and each \(E(q,n)\ne \emptyset , 0\le q\le \lfloor \frac{n}{2} \rfloor \), the parameter q partitions the whole set \(\varOmega (n)\) into \(\lfloor \frac{n}{2} \rfloor +1\) distinct subsets as clusters.
Definition 17
(\(f_E(q,n)\) number of vectors) Let \(f_E(q,n)\) be a number of vectors in a cluster E(q, n).
Lemma 9
For a pair of \(\{n,q\}\) parameters,
Proof
Two cases can be distinguished: Case 1: \(q=0\); Case 2: \(1\le q \le \lfloor \frac{n}{2} \rfloor \).
Case 1: All n values are either 1 or 0, \(2*\left( {\begin{array}{c}n\\ 0\end{array}}\right) =2\).
Case 2: For a given q, 2q crossing positions are composed of a pair of a 0–1 crossing then a 1–0 crossing repeatedly for q times in a vector and this configuration has a total of \(\left( {\begin{array}{c}n\\ 2q\end{array}}\right) \) vectors included, and the same pair of positions can be exchanged as a pair of 1–0 and 0–1 crossings with the same number of different vectors, so a total of \(2*\left( {\begin{array}{c}n\\ 2q\end{array}}\right) \) vectors are involved in each q selection.
It is convenient to list above defined measuring parameters in Table 4 for \(n=4\) condition.
3 Variant Symmetric Clusters
Definition 18
(V(q, p, n) variant cluster) Let V(q, p, n) be a variant cluster of vectors in \(\varOmega (n)\), \(V(q,p,n) = \varOmega (n|p,q) \subset \varOmega (n)\). Three parameters \(\{n,p,q\}\) partition the phase space \(\varOmega (n)\) to form a set of clusters \(\{V(q,p,n)\}\) in a measuring phase space.
Corollary 7
A set of \(\{V(q,p,n)\}_{\forall q, p}\) is composed of a measuring phase space on two dimensions.
Proof
Both invariants q and p are two active invariants to arrange the phase space on a 2D plane lattice.
Lemma 10
Both \(\{L(p,n)\}\) combinatorial clusters and \(\{E(q,n)\}\) crossing clusters can be generated from special subsets of \(\{V(q,p,n)\}\) variant clusters.
Proof
For a given p, L(p, n) can be determined by
For a given q, E(q, n) can be determined by
Applying this set of partitions, three sets of relevant clusters can be identified.
For example, \(n=4\), all 16 vectors in the vector space, three sets of clusters can be distinguished as six clusters \(\{V(q,p,n)\}\), five clusters for \(\{L(p,n)\}\) and three clusters for \(\{E(q,n)\}\) shown in Table 5, respectively.
Definition 19
Let \(C_V(n)\) be a number of non-trivial variant clusters in \(\forall q,p, \{V(q,p,n)\} \).
In general condition for any given \(n > 1\), three sets of variant clusters could be shown in Fig. 1.
Theorem 1
For a given n, \(C_V(n)\) satisfies Eq. 20
Proof
From Fig. 1 for a given n, a triangular shape for non-trivial variant clusters is composed of two parts: a triangular area and two \(q=0\) points. The triangular area has \((n-1)\) length and \(\lfloor n/2 \rfloor \) high. If \(n\equiv 0 \text { mod 2}\), the triangular area is a regular triangle contained \(n^2/4\) clusters, so the total number of this triangular shape contains \(n^2/4 + 2\) clusters. For an odd valued n, a triangular area has additional \(\lfloor n/2 \rfloor \) clusters side on a regular triangle with \(\lfloor n/2 \rfloor ^2\) clusters, so the total number of clusters is \(\lfloor n/2 \rfloor ^2+\lfloor n/2 \rfloor + 2= (n^2 -1)/4 + 2\).
3.1 Variant Trinomial Coefficients – Elementary Equation
Definition 20
Let \(f_V(q,p,n)\) or f(q, p, n) \(0\le p \le n, 0\le q \le \lfloor \frac{n}{2} \rfloor \) denote an enumeration function for a number of 0–1 vectors in a variant cluster.
It is convenient to list relevant measuring parameters in Table 6 for \(n=4\) conditions.
Definition 21
For two initial and end clusters \(p=\{0,n\},q=0\), let two cases be \(f(0,0,n)=f(0,n,n)=1\). For other cases, each cluster \(0< p< n, 0< q \le \lfloor \frac{n}{2} \rfloor \) contains a subgroup of vectors under a given condition. A variant trinomial coefficient for a number of vectors in a cluster is defined as an elementary equation in Equation 21,
Applying variant trinomial coefficients in Eq. 21, there is no difficult to process more complicated cases in enumeration. Global arrangements on their triangular shapes are convenient to be arranged by p measures in vertical direction. Two cases \(n=\{4,5\}\) are shown in Table 7.
In a general condition for any given \(n > 1\), three sets of various numbers can be shown in Fig. 2.
3.2 Combinatorial Projection on Variant Clusters
From an algebraic viewpoint, the following theorems and corollaries are established for a general condition to meet any \(n\ge 1\) cases.
Lemma 11
If \(f_L(p,n)=\sum _{q=1}^{p} f(q,p,n), 0<p<n\), then the projection function \(f_L(p,n)\) is a binomial coefficient and
Proof
For a fixed \(p, 0< p <n\), all possible \(\{f(q,p,n)\}\) are collected to form the following combinatorial identities: [14, 15, 21],
For a complete sequence of binomial coefficients, it is necessary to include both initial and end clusters. Further Theorem 2 can be established.
Theorem 2
For any given \(n>0\), a set of projection function \(\{f_L(p,n)\}_{p=0}^{n}\) is composed of the same sequence of binomial coefficients
Proof
For \(0<p<n\) condition, the equation has been determined by Lemma 11 and two end clusters \(p=\{0,n\},\left( {\begin{array}{c}n\\ 0\end{array}}\right) =\left( {\begin{array}{c}n\\ n\end{array}}\right) =1\) are determined by Definition 21.
Corollary 8
The sum of all possible \(\{f_L(p,n)\}_{p=0}^{n}\) is equal to \(f_{\varOmega }(n)\),
Proof
Collecting all possible numbers in Theorem 2, we have
3.3 Crossing Projection on Variant Clusters
Lemma 12
If \(f_E(q,N)=\sum _{p=q}^{n-q} f(q,p,n), 1\le q \le \lfloor \frac{n}{2} \rfloor \), then the enumeration function \(f_E(q,n)\) is a double of a binomial coefficient
Proof
For a fixed q, collecting all possible \(\{f(q,p,n)\}_{p=q}^{n-q}\), the following combinatorial identities [14, 15, 21] are deduced:
Theorem 3
For any given \(n>0\) under the listed condition, a set of projection function \(\{f_E(q,n)\}_{0\le q \le \lfloor \frac{n}{2} \rfloor }\) are composed of the subsequence of binomial coefficients,
Proof
For \(1\le q \le \lfloor n/2 \rfloor \) condition, equations are determined by Lemma 12 and for the initial subgroup, we have \(q=0, f_E(0,n)=\left( {\begin{array}{c}n\\ 0\end{array}}\right) +\left( {\begin{array}{c}n\\ n\end{array}}\right) =2\left( {\begin{array}{c}n\\ 0\end{array}}\right) \).
Corollary 9
For \(n\equiv 0\mod 2,0\le q \le n/2\), there are a pair of symmetric functions
Proof
Under \(n\equiv 0\mod 2\) condition,
Corollary 10
For \(n\equiv 0\mod 4, q =n/4\), \(f_E(n/4,n)\) has the maximal value
Proof
Under \(n\equiv 0\,\mod 4\) condition,
Corollary 11
The sum of all possible \(\{f_E(q,n)\}_{0\le q \le \lfloor \frac{n}{2} \rfloor }\) is equal to \(f_{\varOmega }(n)\),
Proof
Collecting all possible numbers, we have the following equations:
3.4 Relationships of Four Symmetric Clusters
Theorem 4
For any \(n>0\), the sum of all possible functions on \(\{f(q,p,n\}_{\forall p, \forall q}\) or \(\{f_E(q,n)\}_{0\le q \le \lfloor \frac{n}{2} \rfloor }\) or \(\{f_L(p,n)\}_{p=0}^{n}\) or \(\{f_G(m,n)\}, 1\le m \le C_G(n)\) is equal to \(f_{\varOmega }(n)\)
Proof
From the results of Corollaries 4, 8 and 11, four schemes provide various partitions to the same set of vectors on \(\varOmega (n)\) completely.
Corollary 12
Numbers of four symmetric clusters can be expressed by
Proof
Due to Lemmas 4, 6, 8 and Theorem 1, four equations for numbers of various symmetric clusters are listed.
In convenient for comparison, their values on \(1\le n \le 16\) are listed in Table 8, respectively.
Checking real clusters in four schemes, the following corollaries can be provided.
Corollary 13
When \(n=\{1,2,3\}\), three cluster schemes \(C_L(n), C_V(n), C_G(n)\) provide the same partitions of clusters.
Proof
Checking the three schemes, we have \(C_L(1)=C_V(1)=C_G(1)=2\), \(C_L(2)=C_V(2)=C_G(2)=3\), \(C_L(3)=C_V(3)=C_G(3)=4\). Relevant cluster contains the same set of vectors.
Corollary 14
When \(n=\{1,2,3,4,5\}\), two cluster schemes \(C_V(n), C_G(n)\) provide the same partitions of clusters.
Proof
Due to Corollary 13, we need to check \(n=\{4,5\}\) cases. For the two schemes, we have \((C_L(4)=5)\ne (C_V(4)=C_G(4)=6)\), \((C_L(5)=6)\ne (C_V(5)=C_G(5)=8)\). Relevant cluster contains the same set of vectors.
Corollary 15
When \(n\ge 6\), four cluster schemes \(C_E(n), C_L(n), C_V(n), C_G(n)\) provide different partitions on their clusters.
Proof
Due to Corollaries 13 and 14, we need to check \(n=\{6,\cdots \}\) cases. For the four schemes, \(C_E(6)=4, C_L(6)=7, C_V(6)=11, C_G(6)=14\). Only a few clusters can contain the same set of vectors.
Corollary 16
When \(n\ge 6\), three cluster schemes: combinatorial, crossing and variant \(\{C_E(n),C_L(n),C_V(n)\}\) may contain more symmetric properties than rotation clusters on \(C_G(n)\).
Proof
Considering a special case on \(\{n=6,p=3,q=2\}\), \(V(2,3,6)=\{001101, 011010, 110100, 101001, 010011,100110,011001,110010,100101,001011,010110,101100\}\); this cluster contains two cycles: \(\{001101, 011010, 110100, 101001, 010011,100110\}\) and \(\{011001,110010,100101,001011,010110,101100\}\) with six vectors, respectively. Both cycles have rotation symmetries only without reflection symmetries. It is possible to use reflection symmetric operators to distinct two relative cycles to form a pure rotation symmetric structure. However, other clusters may contain more cycles such as L(3, 6) with four cycles and E(2, 6) with six cycles, respectively. It is necessary to apply other symmetric operators different from rotation for further separations.
4 Four Number Sets of Symmetric Clusters
4.1 Four Approximates on Numbers of Clusters
Using the four numeric equations, relevant approximates can be expressed as follows.
Lemma 13
Four approximates can be expressed as
Proof
Using the four equations, the following approximates can be expressed:
4.2 Four Approximates on Numbers of Vectors
Definition 22
Let \(f_X(n), X\in \{L,E,V,G\}\) denote an approximate number of vectors in X cluster.
Lemma 14
Four approximates can be expressed as
Proof
Since all clusters partition the same phase space \(\varOmega (n)\) with \(2^n\) vectors, their approximates for vectors in a cluster can be evaluated,
It is convenient to list approximate numbers on clusters, vectors and dimension of measuring phase spaces in Table 9.
5 Symmetric Boolean Functions for Selected Clusters
5.1 Four Numbers on Symmetric Boolean Functions
Definition 23
Let \(SF_X(n)\) denote a number of Symmetric Boolean Functions (SBF) in \(\{X(.)\}, X\in \{E,L,V,G\}\).
Theorem 5
(Four types of symmetric Boolean functions) Total numbers of four types of symmetric Boolean functions \(SF_X(n), X\in \{E,L,V,G\}\) are
Proof
For any selected cluster, there are two selections for its symmetric Boolean functions.
5.2 Four Numbers of Balanced Symmetric Clusters
Definition 24
Let \(SF_{Xb}(n)\) be a maximal number of balanced \(SBF_X\) in \(\{X(.)\}, X\in \{L,V,G\}\), \(n=0\) mod 2.
Definition 25
Let \(SF_{Eb}(n)\) be a maximal number of balanced \(SBF_E\) in \(\exists q, \{E(q,n)\}\), \(n=0\) mod 4.
Lemma 15
Four selected numbers \(\{C_{Xb}(n)\}, X\in \{E,L,V,G\}\) for balanced symmetric clusters are
Proof
From Corollary 10 for Eb groups \(n \equiv 0 \mod 4\) cases, \(q = n/4\) provides a cluster with a maximal number of vectors in a balanced condition and other cases cannot satisfy balanced conditions; for Lb groups \(n \equiv 0 \mod 2\) cases, \(p = n/2\) provides a cluster with a maximal number of vectors in a balanced condition; for Vb groups \(n \equiv 0 \mod 2\) cases, \(p = n/2, 1\le q \le n/2\), there are n / 2 clusters involved in a balanced condition; for Gb groups \(n \equiv 0 \mod 2\) cases, \(p = n/2\), a total of rotation symmetric clusters \(O\left( \frac{1}{n}\left( {\begin{array}{c}n\\ n/2\end{array}}\right) \right) \) could be involved in a balanced condition.
5.3 Four Numbers of Balanced Symmetric Boolean Functions
Theorem 6
(Four balanced SYMMETRIC Boolean functions) Total numbers of four balanced symmetric Boolean functions \(\{SF_Xb(n)\}, X\in \{E,L,V,G\}\) are
Proof
Each number of clusters in a selected scheme has been determined in Lemma 15. For any selected cluster in the scheme, there are two selections to form relevant symmetric Boolean functions.
In convenient for comparison, four types of \(SBF_{Xb}\) numbers on \(2\le n \le 20\) are listed in Table 10, respectively.
6 Cryptographic Properties of Symmetric Boolean Functions in Hierarchy
Boolean functions are of great importance in the design of random number generators for stream ciphers [25] that are widely used in modern network environment.
Due to cryptographically secure consideration, the sequence produced by the random number generator must satisfy the various properties [6, 8]: the longer period, the period complexity and good statistical distributions. There exists a huge theoretical knowledge of such combining generators [25].
A symmetric Boolean function must fulfil different necessary criteria to yield a cryptographically secure scheme, at least to resist known attacks [11]. In this direction, various measuring parameters play an important role such as balanced, support set, hamming weight, hamming distance, balanced function, non-linearity, correlation immunity, etc. [6, 8].
In relation to balanced properties, when n is even, the functions of highest non-linearity are the bent functions, and it is well known that the bent functions cannot be the balanced functions [28, 33]. From a structural viewpoint, the balanced functions having the highest possible non-linearity need to be considered. However, finding such functions is a very difficult problem [29, 31, 33]. When n is odd, exhibiting functions of the highest non-linearity is a hard problem in itself. Among the available candidates, balanced ones exist [16, 33].
To explore optimal functions in rotation symmetric Boolean function sets, many researchers are faced extremely difficulties on computational complexity even for \(n>10\) symmetric Boolean functions [29]. Exponentially increasing complexity makes a complex exhaustive search be quickly impossible. Compared with both variant and rotation schemes listed in Table 10, it is interesting to notice that the variant scheme takes a numeric complexity on \(n=20\) as same as the rotation symmetric scheme on \(n=10\). Much faster computation on optimal functions could be feasibly explored.
From a meta analytic viewpoint, measuring phase spaces provide multiple levels of construction in a hierarchy linked to various symmetric Boolean functions. They support an n tuple 0–1 vector construction as a word-based 0–1 vector to satisfy various design and analysis purposes. The variant PRNG construction [38, 43] is a similar approach to RC4 and HC128 stream ciphers [25] in their meta phase spaces using the word-oriented vector structure with the higher speed and efficiency. Measuring phase spaces could support advanced cryptographic applications on the direction.
Due to significant differences between measuring phase spaces proposed and algebraic normal forms classically formulated, in addition to initial balanced symmetric properties discussed in the chapter, other advanced comparison mechanisms need to be established for all interesting cryptographic properties to satisfy practical and optimal requirements for stream ciphers. Further detailed researches and explorations are required.
7 Conclusion
Symmetric clusters in a hierarchy provide the additional information to organize various symmetric Boolean functions into hierarchical constructions as multiple meta levels of structures efficiently. The variant symmetric functions proposed in this chapter provide a meta construction on a 2D measuring phase space to contribute richer capacities compared with the three classical schemes (combinatorial, crossing and rotation) on 1D measuring phase spaces.
From a measuring viewpoint, three schemes (combinatorial, variant and rotation) in Tables 8, 9 and 10 have similar values in \(n=\{1,2,3\}\) and \(\{4,5\}\) or different values in \(n\ge 6\) conditions. The variant scheme provides a 2D intermediate structure different from other two schemes in 1D structure. From an approximate viewpoint, both combinatorial and rotation schemes are shown in stronger similar properties. Their approximate number of clusters and number of vectors in a cluster can be exchanged in Table 9. From an abstract system viewpoint, this pair of exchangeable measurements may provide approximate symmetric properties for both combinatorial and rotation schemes.
From a clustering viewpoint, the most important results are summarized in Theorem 4 to show that the four symmetric cluster schemes are different partition schemes on the same 0–1 vector set.
From a balanced analysis viewpoint, the key results of balanced symmetric Boolean functions are summarized in Theorem 6 and Table 10. This set of results provides a basic measurement to illustrate relevant computational difficulties to explore further optimal properties in balanced symmetric conditions. Different from other three schemes (combinatorial, crossing and rotation) in either very simpler or extremely complex associated with n increasing, balanced variant symmetric Boolean functions present very interesting patterns to support even \(n\ge 20\) cases for future explorations.
Many advanced properties are existed to use a meta hierarchical construction to manage relevant measuring phase spaces into multilevels of a hierarchical structure. Various measuring parameters can be used as control parameters in detailed cases. Refined design and analysis can be performed under this meta hierarchy to provide powerful models and tools on design and optimization for future generations of stream ciphers.
References
E.B. Barker, A Statistical test suite for random and pseudorandom number generators for cryptographic applications, ITLB NIST (2000)
J.V. Bradley, Distribution-free statistical tests (Prentice-Hall 1968)
J. Carroll, The binary derivative test: noise filter, crypto aid, and random-number seed selector. Simulation 53(3), 129–135 (1989)
P.J. Cameron, Combinatorics: Topics, Techniques, Algorithms (Cambridge University Press, Cambridge, 1994)
A. Canteaut, M. Videau, Symmetric boolean functions. IEEE Trans. Inf. Theory 51(8), 2791–2811 (2005)
C. Carlet, On the degree, nonlinearity, algebraic thickness and nonormality of boolean function, with developments on symmetric functions. IEEE Trans. Inf. Theory 50(9), 2178–2185 (2004)
C. Carlet, K. Feng, An infinite class of balanced functions with optimal algebraic immunity, good immunity for fast algebraic attacks and good nonlinearity, in ASIACRYPT ed. by J. Pieprzyk, LNCS, vol. 5350 (Springer 2008), pp. 425–440
C. Carlet, G. Gao, W. Liu, A secondary construction and a transformation on rotation symmetric functions, and their action on bent and semi-bent functions. J. Comb. Theory, Ser. A, 127, 161–175 (2014)
F.N. Castro, L.A. Medina, Linear recurrences and asymptotic behavior of exponential sums of symmetric boolean functions. Electron. J. Combin. 18(2), P8 (2011)
J.R. Chen. Combinatorial Mathematics (Harbin Institute of Technology Press, 2012) (in Chinese)
T.W. Cusick, P. St\(\check{a}\)nic\(\check{a}\). Fast Evaluation, weights and nonlinearity of rotation-symmetric functions. Discrete Mathe. 258(1-3), 289–301 (2002)
E. Filiol, C. Fontaine. Highly nonlinear balanced Boolean functions with a good correlation immunity, in Eurocrypt 1998, number 1403 in Lecture Notes in Computer Science, vol. 475488 (Springer-Verlag, 1998)
S.J. Fu, C. Li, L.J. Qu, On the number of rotation symmetric boolean functions. Sci. China Inf. Sci. 53(3), 537–545 (2010)
H.W. Gould, Some generalizations of vandermonde’s convolution. Am. Math. Mon. 63(2), 84–91 (1956)
H.W. Gould. Combinatorial Identities (Morganton, 1972)
Y.M. Guo, G.P. Gao, Y.Q. Zhao. Recent results on balanced symmetric boolean functions, available: http://eprint.iacr.org/2012/093 (2012)
G. Gao, X. Zhang, W. Liu, C. Carlet, Constructions of quadratic and cubic rotation symmetric bent functions. IEEE Trans. Inf. Theory 58(7), 4908–4913 (2012)
M. Hall, Combinatorial Theory, 2nd edn. (Blaisdell, 1986)
L.K. Hua,Loo-Keng Hua Selected Papers (Springer, 1982)
S. Kavut, S. Maitra, M.D. Ycel, Search for boolean functions with excellent profiles in the rotation symmetric class. IEEE Trans. Inf. Theory 53(5), 1743–1751 (2007)
D.E. Knuth. The Art of Computer Programming, vol. 1, 3rd edn. (Addison-Wesley, 1998)
D.E. Knuth, The Art of Computer Programming, A: Combinatorial Algorithms, Part 1, vol. 4 (Addison-Wesley, 2011)
B. Logan Jr., Information in the zero crossings of bandpass signals. Bell Syst. Tech. J. 56, 487–510 (1977)
Q. Meng, L. Chen, F. Fu, On homogeneous rotation symmetric bent functions. Discr. Appl. Math. 158(10), 1111–1117 (2010)
G. Paul, S. Maitra. RC4 Stream Cipher and Its Variants (CRC Press, 2012)
J. Pieprzyk, C.X. Qu, Fast hashing and rotation-symmetric functions. J. Universal Comput. Sci. 5(1), 20–31 (1999)
L. Qu, C. Li, K. Feng, A note on symmetric boolean functions with maximum algebraic immunity in odd number of variables. IEEE Trans. IT-53, 2908–2910 (2007)
Sarkar, P., Maitra, S, Construction of nonlinear Boolean functions with important cryptographic properties, in Advances in Cryptology EUROCRYPT 2000, vol. 1807 in LNCS (Springer Verlag, 2000), pp. 485–506
P. St\(\check{a}\)nic\(\check{a}\), S. Maitra, Rotation symmetric boolean functions - count and cryptographic properties, Discr. Appl. Math. 156, 1567–1580 (2008)
R.P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd edn. (Cambridge University Press, 1997)
W. Su, X.H. Tang, A. Pott, A note on a conjecture for balanced elementary symmetric boolean functions. IEEE Trans. Inf. Theory 59(1), 665–671 (2013)
S.H. Su, X.H. Tang, Construction of rotation symmetric boolean functions with optimal algebraic immunity and high nonlinearity. Des. Codes Cryptography 71(2), 183–199 (2014)
S.H. Su, X.H. Tang, On the systematic constructions of rotation symmetric bent functions with any possible algebraic degrees. IACR Cryptology ePrint Archive 2015, 451 (2015)
G.Z. Tu, Combinatorial Enumeration Methods & Applications (Science Press, 1981) (in Chinese)
A. Tucker, Applied Combinatorics (Wiley, 2007)
J.H. van Lint, R.M. Wilson, A Course in Combinatorics, 2nd edn. (Cambridge University Press, 2001)
H. Wang, J. Zheng, 3D Visual Method of Variant Logic Construction for Random Sequence. Australian Information Warfare and Security, pp. 16–27 (2013)
W.Z. Yang, J. Zheng, Variant pseudo-random number generator, Hakin9 extra. Timing Attack 06(13), 28–31 (2012)
Z.J. Zheng, A. Maeder, The conjugate classification of the kernel form of the hexagonal grid, in Modern Geometric Computing for Visualization (Springer-Verlag, 1992) pp. 73–89. http://springerlink.fh-diploma.de/chapter/10.1007/978-4-431-68207-3_5 e-version
Z.J. Zheng. Conjugate Transformation of Regular Plan Lattices for Binary Images, Ph.D. Thesis, Monash University, 1994
J.Z.J. Zheng, C.H.H. Zheng, A framework to express variant and invariant functional spaces for binary logic, Frontiers of Electrical and Electronic Engineering in China, 5(2), 163–172, Higher Educational Press and Springer-Verlag, 2010. http://springerlink.fh-diploma.de/article/10.1007%2Fs11460-010-0011-4, https://doi.org/10.1007/s11460-010-0011-4
J.Z.J. Zheng, C.H.H. Zheng, T.L. Kunii, A framework of variant logic construction for cellular automata, Cellular Automata - Innovative Modeling for Science and Engineering, ed by A. Salcido (InTech Press, 2011). http://www.intechopen.com/books/cellular-automata-innovative-modelling-for-science-and-engineering/a-framework-of-variant-logic-construction-for-cellular-automata, https://doi.org/10.5772/15400
J. Zheng, Novel pseudo-random number generation using variant logic framework, in 2nd International Cyber Resilience Conference, pp. 100–104, 2011. http://igneous.scis.ecu.edu.au/proceedings/2011/icr/zheng.pdf
J. Zheng, C. Zheng, Variant simulation system using quaternion structure. J. Modern Opt. Taylor & Francis Press 59(5), 484–492 (2012)
J. Zheng, C. Zheng, T.L. Kunii, From conditional probability measurements to global matrix representations on variant construction, in Advanced Topics in Measurements (InTech Press, 2012), pp. 339–370
J. Zheng, C. Zheng, T.L. Kunii. From Local Interactive Measurements to Global Matrix Representations on Variant Construction, in Advanced Topics in Measurements (InTech Press, 2012), pp. 371–400
J. Zheng, C. Zheng, T.L. Kunii, Interactive maps on variant phase space, in Emerging Application of Cellular Automata (InTech Press, 2013), pp. 113–196
J. Zheng, W. Zhang, J. Luo, W. Zhou, R. Shen, Variant map system to simulate complex properties of DNA interactions using binary sequences. Adv. Pure Math. 3(7A), 5–24 (2013)
J. Zheng, J. Luo, W. Zhou, Pseudo DNA sequence generation of non-coding distributions using variant maps on cellular automata. Appl. Math. 5(1), 153–174 (2014)
J. Zheng, W. Zhang, J. Luo, W. Zhou, V. Liesaputra, Variant map construction to detect symmetric properties of genomes on 2D distributions. J. Data Mining Genomics Proteomics 5, 150 (2014). https://doi.org/10.4172/2153-0602.1000150
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2019 The Author(s)
About this chapter
Cite this chapter
Zheng, J. (2019). Symmetric Clusters in Hierarchy with Cryptographic Properties. In: Zheng, J. (eds) Variant Construction from Theoretical Foundation to Applications. Springer, Singapore. https://doi.org/10.1007/978-981-13-2282-2_5
Download citation
DOI: https://doi.org/10.1007/978-981-13-2282-2_5
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-13-2281-5
Online ISBN: 978-981-13-2282-2
eBook Packages: EngineeringEngineering (R0)