The propagation criterion for monotone Boolean functions with least vector support sets consisting of one or two vectors is studied. We obtain necessary and sufficient conditions for the validity of ...the propagation criterion for a vector in terms of the Hamming weights of vectors in least vector support set depending on whether these vectors share some nonzero components with the given vector. We find the cardinality of the set of vectors satisfying the propagation criterion for such functions.
This paper aims to construct optimal Z-complementary code set (ZCCS) with non-power-of-two (NPT) lengths to enable interference-free multicarrier code-division multiple access (MC-CDMA) systems. The ...existing ZCCSs with NPT lengths, which are constructed from generalized Boolean functions (GBFs), are sub-optimal only with respect to the set size upper bound. For the first time in the literature, we advocate the use of pseudo-Boolean functions (PBFs) (each of which transforms a number of binary variables to a real number as a natural generalization of GBF) for direct constructions of optimal ZCCSs with NPT lengths.
Cryptographic Boolean functions play an important role in the design of symmetric ciphers. Many cryptographic criteria such as balancedness, nonlinearity, correlation immunity and transparency order ...are connected with the Walsh support of a Boolean function. However, we still know little about the possible structure of the Walsh supports of Boolean functions. In 2005, Carlet and Mesnager studied the Walsh supports of Boolean functions and constructed a class of n-variable Boolean functions whose Walsh support is F2n∖{0}, for n≥10. For n≤6, it can be verified using the computer that there is no Boolean function with the Walsh Support F2n∖{0}. However, concerning the values of n=7,8,9, it has been an open problem for many years. In this paper, we construct two classes of balanced Boolean functions with the maximum possible Walsh support F2n∖{0}, and partially solve this problem. The first class of functions are of odd variables with n≥9, and the second class of functions are constructed based on the Maiorana–McFarland bent functions, which are of even variables with n≥8. As a result, the above open problem has been settled for n=8,9, and the only unsolved case is n=7.
In this paper, we show that every (2
n-1 + 1)-vertex
induced subgraph of the n-dimensional cube graph has maximum
degree at least
n
.
This is the best possible result, and it improves a logarithmic ...lower bound
shown by Chung, Füredi, Graham and Seymour in 1988. As a direct consequence, we
prove that the sensitivity and degree of a boolean function are polynomially
related, solving an outstanding foundational problem in theoretical computer
science, the Sensitivity Conjecture of Nisan and Szegedy.
As the only nonlinear module, S-Box (substitution box) is widely used in stream cipher, hash function, and so on. However, there exist some weaknesses in existing S-Boxes, such as fixed point, ...reverse fixed point and short iteration period rings. Furthermore, the S-Boxes in AES and SM4.0 were fixed, which makes them vulnerable to attack. To address these weaknesses, first, a non-degenerate 2D chaotic map (2D-NDCM) with ergodicity in phase space was constructed. Second, based on 2D-NDCM, the seed S-Boxes with high nonlinearity were constructed in batches by affine transformation and Boolean function, and then three possible weaknesses were eliminated to obtain strong keyed S-Boxes. Statistical analysis demonstrated the effectiveness and practicability of the proposed S-Box batch generating algorithm.
<inline-formula> <tex-math notation="LaTeX">Z </tex-math></inline-formula>-complementary code set (ZCCS), an extension of perfect CCs, refers to a set of 2-D matrices having zero correlation zone ...properties. ZCCS can be used in various multi-channel systems to support, for example, quasi-synchronous interference-free multicarrier code-division multiple access communication and optimal channel estimation in multiple-input multiple-output systems. Traditional constructions of ZCCS heavily rely on a series of sequence operations which may not be feasible for rapid hardware generation particularly for long ZCCSs. In this paper, we propose a direct construction of ZCCS using the second-order Reed-Muller codes with efficient graphical representation. Our proposed construction, valid for any number of isolated vertices present in the graph, is capable of generating optimal ZCCS meeting the set size upper bound.
In this paper, we consider the spectra of Boolean functions with respect to the nega-Hadamard transform. Based on the properties of the nega-Hadamard transform and the solutions of the Diophantine ...equations, we investigate all possibilities of the nega-Hadamard transform of Boolean functions with exactly two distinct nega-Hadamard coefficients.
Boolean functions play an important role in symmetric ciphers. One of important open problems on Boolean functions is determining the maximum possible resiliency order of n-variable Boolean functions ...with optimal algebraic immunity. In this letter, we search Boolean functions in the rotation symmetric class, and determine the maximum possible resiliency order of 9-variable Boolean functions with optimal algebraic immunity. Moreover, the maximum possible nonlinearity of 9-variable rotation symmetric Boolean functions with optimal algebraic immunity-resiliency trade-off is determined to be 224.
Minimal Binary Linear Codes Ding, Cunsheng; Heng, Ziling; Zhou, Zhengchun
IEEE transactions on information theory,
10/2018, Letnik:
64, Številka:
10
Journal Article
Recenzirano
In addition to their applications in data communication and storage, linear codes also have nice applications in combinatorics and cryptography. Minimal linear codes, a special type of linear codes, ...are preferred in secret sharing. In this paper, a necessary and sufficient condition for a binary linear code to be minimal is derived. This condition enables us to obtain three infinite families of minimal binary linear codes with <inline-formula> <tex-math notation="LaTeX">w_{\min }/w_{\max } \leq 1/2 </tex-math></inline-formula> from a generic construction, where <inline-formula> <tex-math notation="LaTeX">w_{\min } </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">w_{\max } </tex-math></inline-formula>, respectively, denote the minimum and maximum nonzero weights in a code. The weight distributions of all these minimal binary linear codes are also determined.
We prove the covering radius of the third-order Reed-Muller code RM(3, 7) is 20, which was previously known to be between 20 and 23 (inclusive). The covering radius of RM(3, 7) is the maximum ...third-order nonlinearity among all 7-variable Boolean functions. It was known that there exist 7-variable Boolean functions with third-order nonlinearity 20. We prove the third-order nonlinearity cannot achieve 21. According to the classification of the quotient space of RM(6, 6)/RM(3, 6), we classify all 7-variable Boolean functions into 66 types. Firstly, we prove 62 types (among 66) cannot have third-order nonlinearity 21; Secondly, we prove that any function in the remaining 4 types can be transformed into a type (6,10) function, if its third-order nonlinearity is 21; Finally, we transform type (6, 10) functions into a specific form, and prove the functions in that form cannot achieve the third-order nonlinearity 21 (with the assistance of computers). By the way, we prove that the affine transformation group over any finite field can be generated by two elements.
PDF
