Search

Linear codes play a crucial role in various fields of engineering and mathematics, including data storage, communication, cryptography, and combinatorics. Minimal linear codes, a subset of linear codes, are particularly essential for designing effective secret sharing schemes. In this paper, we introduce several classes of minimal binary linear codes by carefully selecting appropriate Boolean functions. These functions belong to a renowned class of Boolean functions, namely, the general Maiorana–McFarland class. We employ a method first proposed by Ding et al. (IEEE Trans Inf Theory 64(10):6536–6545, 2018) to construct minimal codes violating the Ashikhmin–Barg bound (wide minimal codes) by using Krawtchouk polynomials. The lengths, dimensions, and weight distributions of the obtained codes are determined using the Walsh spectrum distribution of the chosen Boolean functions. Our findings demonstrate that a vast majority of the newly constructed codes are wide minimal. Furthermore, our proposed codes exhibit a significantly larger minimum distance, in some cases, compared to some existing similar constructions. Finally, we address this method, based on Krawtchouk polynomials, more generally, and highlight certain generic properties related to it. These general results offer insights into the scope of this approach. [ABSTRACT FROM AUTHOR]

There is a rising demand for low-cost, high-information-capacity optical signal processing. The number of devices is limited of performing different Boolean functions using a single unit. In the current manuscript, six basic logic gates, including OR, XOR, NAND, AND, NOR, and XNOR, are implemented in a single unit utilizing all-optical silicon microring resonator. At first, three microring resonators are used to get the AND, XOR and NOR logic functions. Then, beam combiners are used to get the OR, NAND and XNOR functions from AND, XOR, and NOR functions. In MATLAB, the suggested design is numerically simulated to verify the functions at an operational speed of nearly 260 Gbps. The required pump power for switching is only 1.95 mW for microring resonator based switch which is very less comparatively. Also, some performance parameters like "extinction ratio", "contrast ratio", "amplitude modulation", "on–off ratio", and "quality factor" are evaluated. To design the circuit practically, optimized parameters of the circuits have been selected. The obtained values of "extinction ratio" and "contrast ratio" are 14.97 dB and 19.03 dB, respectively. The value of AM is 0.17 dB which is less than 1 dB. The on–off ratio of the MRR is 35.10 dB which is much higher than expected. [ABSTRACT FROM AUTHOR]

In this paper, we study the value distributions of perfect nonlinear functions, i.e., we investigate the sizes of image and preimage sets. Using purely combinatorial tools, we develop a framework that deals with perfect nonlinear functions in the most general setting, generalizing several results that were achieved under specific constraints. For the particularly interesting elementary abelian case, we derive several new strong conditions and classification results on the value distributions. Moreover, we show that most of the classical constructions of perfect nonlinear functions have very specific value distributions, in the sense that they are almost balanced. Consequently, we completely determine the possible value distributions of vectorial Boolean bent functions with output dimension at most 4. Finally, using the discrete Fourier transform, we show that in some cases value distributions can be used to determine whether a given function is perfect nonlinear, or to decide whether given perfect nonlinear functions are equivalent. [ABSTRACT FROM AUTHOR]

In modern block ciphers, the role of the substitution boxes is to generate ciphertext from the plaintext with high confusion. The immunity to various cryptographic attacks heavily depends on the strength of the S-box. In this article, a new method of obtaining highly nonlinear substitution boxes (S-boxes) is proposed. The subject method utilizes the artificial bee colony optimization technique. To check the immunity of the proposed S-boxes, the analysis of the proposed S-boxes is checked against the key performance indicators (KPIs) for S-boxes. The results obtained from KPIs are highly encouraging and the proposed S-boxes meet all the criteria needed for secure communication and storage of digital content. To rank the proposed S-box and the recently published S-boxes, the technique for order preference by similarity to an ideal solution is discussed for the first time for the S-boxes. [ABSTRACT FROM AUTHOR]

Deutsch–Jozsa problem ( D J n ) showed for the first time that quantum computation can achieve exponential advantages over classical computers, which encouraged and laid the foundation for further research on quantum algorithms. A generalization of Deutsch–Jozsa problem ( D J n k , proposed by Phys Rev A 97:062331, 2018) maintains the exponential advantage when the parameter k is a constant. However, these achieved exponential advantages are just in the case that all outputs are required to be accurate. In contrast, this paper studies classical randomized decision tree complexities of D J n and D J n k . It is proved that the first complexity R 2 (D J n) ≤ 3 in all cases and the second complexity R 2 (D J n k) is constant when k n is constant for n being a large even number. As a result, for these cases, optimal bounded-error quantum algorithms of D J n and D J n k can only slightly accelerate the classical computation. [ABSTRACT FROM AUTHOR]

Most of the approaches published in the literature to construct S-boxes via Cellular Automata (CA) work by either iterating a finite CA for several time steps, or by a one-shot application of the global rule. The main characteristic that brings together these works is that they employ a single CA rule to define the vectorial Boolean function of the S-box. In this work, we explore a different direction for the design of S-boxes that leverages on Orthogonal CA (OCA), i.e. pairs of CA rules giving rise to orthogonal Latin squares. The motivation stands on the facts that an OCA pair already defines a bijective transformation, and moreover the orthogonality property of the resulting Latin squares ensures a minimum amount of diffusion. We exhaustively enumerate all S-boxes generated by OCA pairs of diameter 4 ≤ d ≤ 6 , and measure their nonlinearity. Interestingly, we observe that for d = 4 and d = 5 all S-boxes are linear, despite the underlying CA local rules being nonlinear. The smallest nonlinear S-boxes emerges for d = 6 , but their nonlinearity is still too low to be used in practice. Nonetheless, we unearth an interesting structure of linear OCA S-boxes, proving that their Linear Components Space is itself the image of a linear CA, or equivalently a polynomial code. We finally classify all linear OCA S-boxes in terms of their generator polynomials. [ABSTRACT FROM AUTHOR]

Dynamic linear functions on the boolean hypercube are functions which assign to each bit a positive weight, but the weights change over time. Throughout optimization, these functions maintain the same global optimum, and never have defecting local optima. Nevertheless, it was recently shown [Lengler, Schaller, FOCI 2019] that the (1 + 1) -Evolutionary Algorithm needs exponential time to find or approximate the optimum for some algorithm configurations. In this experimental paper, we study the effect of larger population sizes for dynamic binval, the extreme form of dynamic linear functions. We find that moderately increased population sizes extend the range of efficient algorithm configurations, and that crossover boosts this positive effect substantially. Remarkably, similar to the static setting of monotone functions in [Lengler, Zou, FOGA 2019], the hardest region of optimization for (μ + 1) -EA is not close the optimum, but far away from it. In contrast, for the (μ + 1) -GA, the region around the optimum is the hardest region in all studied cases.Kindly check and confirm the inserted city name is correctly identified.Correct. [ABSTRACT FROM AUTHOR]

Aaronson defined Forrelation (2010) as a measure of correlation between a Boolean function f and the Walsh–Hadamard transform of another function g . In a recent work, we have studied different cryptographically important spectra of Boolean functions through the lens of Forrelation. In this paper, we explore a similar kind of correlation in terms of nega-Hadamard transform. We call it nega-Forrelation and obtain a more efficient sampling strategy for nega-Hadamard transform compared to the existing results. Moreover, we present an efficient sampling strategy for nega-crosscorrelation (and consequently nega-autocorrelation) spectra too, by tweaking the nega-Forrelation technique. Finally, we connect the hidden shift finding algorithm for bent functions (Rötteler, 2010) with the Forrelation algorithm and extend it for the negabent functions. [ABSTRACT FROM AUTHOR]

A Boolean function f on n variables is said to be a bent function if the absolute value of all its Walsh coefficients is 2 n / 2 . Our main result is a new asymptotic lower bound on the number of Boolean bent functions. It is based on a modification of the Maiorana–McFarland family of bent functions and recent progress in the estimation of the number of transversals in latin squares and hypercubes. By-products of our proofs are the asymptotics of the logarithm of the numbers of partitions of the Boolean hypercube into 2-dimensional affine and linear subspaces. [ABSTRACT FROM AUTHOR]

The Patterson–Wiedemann (PW) construction, which is defined for an odd number n of variables with n being the product of two distinct prime numbers p and q, can be interpreted as idempotent functions which are represented by the (d, r)-interleaved sequences formed by all-zero and all-one columns, where r = (2 p - 1) (2 q - 1) and d = (2 n - 1) r . We here study a modified form of the PW construction, which only requires 2 n - 1 (= d r) be a composite number, by relaxing the constraint on the values of d and r. We first elaborate on the case n = 15 and consider the functions corresponding to the (217, 151)-interleaved sequences. Taking into account those satisfying f (α) = f (α 2 k) for all α ∈ F 2 n in this scenario, where k is a fixed divisor of n, we obtain Boolean functions with nonlinearity 16268 exceeding the bent concatenation bound. Then we extend our study for the case n = 11 and obtain Boolean functions with nonlinearity 996 represented by the (89, 23)-interleaved sequences, which equals the best known nonlinearity result. In the process, we show that there is the possibility to exceed the best known nonlinearities using the functions corresponding to those interleaved sequences. [ABSTRACT FROM AUTHOR]

Recently, several interesting constructions of vectorial Boolean functions with the maximum number of bent components (MNBC functions, for short) were proposed. However, many of them have component functions from the completed Maiorana-McFarland class M # . Moreover, no examples of MNBC functions containing component functions provably outside M # are known. In this paper, we classify all MNBC functions in six variables. Based on the analysis of the obtained equivalence classes, we propose several infinite families of MNBC functions with component functions outside the M # class. In particular, two of our new constructions are solutions to the open problem [Bapić et al (eds) Proceedings of the twelfth international workshop on coding and cryptography, 2022, Item 1., p. 9]. [ABSTRACT FROM AUTHOR]

Legal text retrieval serves as a key component in a wide range of legal text processing tasks such as legal question answering, legal case entailment, and statute law retrieval. The performance of legal text retrieval depends, to a large extent, on the representation of text, both query and legal documents. Based on good representations, a legal text retrieval model can effectively match the query to its relevant documents. Because legal documents often contain long articles and only some parts are relevant to queries, it is quite a challenge for existing models to represent such documents. In this paper, we study the use of attentive neural network-based text representation for statute law document retrieval. We propose a general approach using deep neural networks with attention mechanisms. Based on it, we develop two hierarchical architectures with sparse attention to represent long sentences and articles, and we name them Attentive CNN and Paraformer. The methods are evaluated on datasets of different sizes and characteristics in English, Japanese, and Vietnamese. Experimental results show that: (i) Attentive neural methods substantially outperform non-neural methods in terms of retrieval performance across datasets and languages; (ii) Pretrained transformer-based models achieve better accuracy on small datasets at the cost of high computational complexity while lighter weight Attentive CNN achieves better accuracy on large datasets; and (iii) Our proposed Paraformer outperforms state-of-the-art methods on COLIEE dataset, achieving the highest recall and F2 scores in the top-N retrieval task. [ABSTRACT FROM AUTHOR]

We prove that if a Boolean function essentially depends on at least two variables, then it cannot be implemented by a circuit that consists of unreliable gates with at most two inputs each and is self-correcting with respect to at least some faults of an arbitrary number of gates. In view of the previous results, it suffices to establish this fact for linear functions. [ABSTRACT FROM AUTHOR]

The 93 minions of Boolean functions stable under left composition with the clone of self-dual monotone functions are described. As an easy consequence, all (C 1 , C 2) -clonoids of Boolean functions are determined for an arbitrary clone C 1 and for any clone C 2 containing the clone of self-dual monotone functions. [ABSTRACT FROM AUTHOR]

The substitution box (S-box) is the core component of any block cipher that creates confusion in the ciphertext. This research contributes to creating a substitution box based on bent Boolean functions. Bent Boolean functions are constructed using the Maiorana–McFarland method and used as the coordinate functions of the substitution box. They are maximal nonlinear and inherently imbalanced, making them unsuitable for direct use in constructing a confusion component. The imbalance nature of the coordinate Boolean function directly impacts the bijective property of the nonlinear component. To create a bijective confusion component, we focus on mitigating the imbalance of each coordinate Boolean function. The methodology adopted is simple and efficient as compared to other heuristic techniques. By defining an empty matrix and putting bent Boolean functions side by side as matrix elements, we shape the initial 2 n × k sized substitution box, k ∈ (2 ,... , n) . We limit the number of occurrences of each possible outcome of initial 2 n × k substitution box to make a bijective n × n S-box. These small initial S-boxes lay a good foundation for constructing strong subsequent S-boxes. Experimental results based on the generation of 8 × 8 substitution box indicate that the suggested algorithm outperforms other competing heuristic approaches in nonlinearity, while maintaining sufficient performance in the strict avalanche criterion, bit-independence, linear and differential probability properties. The suggested nonlinear component is tested using well-known images from the literature, and the histogram analysis of the confused images demonstrates a high degree of randomness. [ABSTRACT FROM AUTHOR]

Robustness of modern information confidentiality algorithm depends on its individual components. Modern block ciphers highly depend on two components namely confusion and diffusion. These two main characteristics in any modern cipher are achieved by substitution and permutation boxes. In this article, a decision-making algorithm is utilized for the selection of optimum substitution box (S-box), which plays a significant role in the field of information confidentiality. For this purpose, an interval-based Pythagorean fuzzy technique for order of preference by similarity to the ideal solution (IVPF–TOPSIS) method is introduced to get the desired nonlinear confusion component of block cipher namely S-box. In this manner, we performed cryptographic analyses of standard S-boxes namely nonlinearity (NL), strict avalanche criterion (SAC), bit-independent criterion (BIC), absolute indicator (ABI), the sum of square and absolute indicator (SSAI), algebraic degree (AD), algebraic immunity (AI), transparency order (TO), composite algebraic immunity (CAI), robustness (RB), signal to noise ratio (SNR), confusion coefficient of variance (CCV). With these cryptographic characteristics, we have used interval-valued based Pythagorean fuzzy TOPSIS multi-criteria decision-making technique to classify standard S-boxes suitable for construction of modern block ciphers. [ABSTRACT FROM AUTHOR]

In this paper, we study the class of those Boolean functions that are coset leaders of first order Reed-Muller codes. We study their properties and try to better understand their structure (which seems complex), by studying operations on Boolean functions that can provide coset leaders (we show that these operations all provide coset leaders when the operands are coset leaders, and that some can even produce coset leaders without the operands being coset leaders). We characterize those coset leaders that belong to the well known classes of direct sums of monomial Boolean functions and Maiorana-McFarland functions. Since all the functions of Hamming weight at most 2 n - 2 are automatically coset leaders, we are interested in constructing infinite classes of coset leaders having possibly Hamming weight larger than 2 n - 2 . [ABSTRACT FROM AUTHOR]

Bent functions are Boolean functions in even number of variables that have maximal nonlinearity. They have flat Walsh–Hadamard spectrum and are of interest for their applications in algebra, coding theory and cryptography. A bent function is called self-dual if it coincides with its dual bent function. In current work we study the decomposition of the form f 0 , f 1 , ... , f 2 k - 1 of the vector of values of a self-dual bent function, formed by the concatenation of 2 k Boolean functions f j in n - k variables. We treat the cases k = 1 , 2 . Based on a spectral characterization, we introduce a notion of self-dual near-bent function in odd number of variables and prove that there exists a one-to-one correspondence between the notions of self-duality for even and odd number of variables. As a result the characterization for the decomposition f 0 , f 1 is obtained. For the decomposition f = f 0 , f 1 , f 2 , f 3 we prove that if sign vectors of subfunctions f j are linearly dependent, then all these subfunctions are bent. We prove that for n ⩾ 6 the converse does not hold, that is the obtained condition is sufficient only. These results are also generalized for the case of an arbitrary bent function. Three new iterative constructions of self-dual bent functions are proposed. One of them allows to build a class of self-dual bent functions which cannot be decomposed into the concatenation of four bent functions. Based on the constructions a new iterative lower bound on the cardinality of the set of self-dual bent functions is obtained. [ABSTRACT FROM AUTHOR]

A method is given to reduce the problem of finding a nontrivial factorization of a positive integer α , greater than one, to the problem of finding a solution to a system of Boolean equations, that is, a system of equations such that each equation is of the form f = g where f and g are Boolean functions, meaning { 0 , 1 } -valued functions in zero or more Boolean ( { 0 , 1 } -valued) variables. Our system is obtained by applying a sequence of reductions to an initial system of equations of the form { f i (x → , y →) = α i ∣ i ∈ { 0 , ⋯ , 2 n } } where for each i f i (x → , y →) = f i (x 0 , ⋯ , x n , y 0 , ⋯ , y n) gives the coefficient of 2 i in the binary expansion of (x 0 + 2 x 1 + ⋯ + 2 n x n) (y 0 + 2 y 1 + ⋯ + 2 n y n) , α i gives the coefficient of 2 i in the binary expansion of α , and x i and y i are { 0 , 1 } -valued variables. That is, the initial system represents a binary multiplier whose output bits have been set equal to the bits of α . It is shown that each Boolean function in our reduced system, that is, each Boolean function (g - h) mod 2 = 0 ⟺ g = h 1 ⟺ g ≠ h such that g = h is an equation in the reduced system, can be represented by a type of graph called an ordered binary decision diagram (OBDD) with an upper bound on its number of vertices of O log 2 (α / log 2 (α)) ) 3 . Previous work has shown that the initial system has at least one Boolean function with an OBDD representation with number of vertices exponential in log 2 (α) . [ABSTRACT FROM AUTHOR]

In this paper, we study quantum Ordered Binary Decision Diagrams(OBDD ) model; it is a restricted version of read-once quantum branching programs, with respect to "width" complexity. It is known that the maximal gap between deterministic and quantum complexities is exponential. But there are few examples of functions with such a gap. We present a new technique ("reordering") for proving lower bounds and upper bounds for OBDD with an arbitrary order of input variables if we have similar bounds for the natural order. Using this transformation, we construct a total function REQ such that the deterministic OBDD complexity of it is at least 2 Ω (n / log n) , and the quantum OBDD complexity of it is at most O (n 2 / log n) . It is the biggest known gap for explicit functions not representable by OBDD s of a linear width. Another function(shifted equality function) allows us to obtain a gap 2 Ω (n) vs O (n 2) . Moreover, we prove the bounded error quantum and probabilistic OBDD width hierarchies for complexity classes of Boolean functions. Additionally, using "reordering" method we extend a hierarchy for read-k-times Ordered Binary Decision Diagrams ( k - OBDD ) of polynomial width, for k = o (n / log 3 n) . We prove a similar hierarchy for bounded error probabilistic k - OBDD s of polynomial, superpolynomial and subexponential width. The extended abstract of this work was presented on International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8 – 12, 2017 Khadiev and Khadieva (2017) [ABSTRACT FROM AUTHOR]

Boolean functions are mathematical objects used in diverse domains and have been actively researched for several decades already. One domain where Boolean functions play an important role is cryptography. There, the plethora of settings one should consider and cryptographic properties that need to be fulfilled makes the search for new Boolean functions still a very active domain. There are several options to construct appropriate Boolean functions: algebraic constructions, random search, and metaheuristics. In this work, we concentrate on metaheuristic approaches and examine the related works appearing in the last 25 years. To the best of our knowledge, this is the first survey work on this topic. Additionally, we provide a new taxonomy of related works and discuss the results obtained. Finally, we finish this survey with potential future research directions. [ABSTRACT FROM AUTHOR]

The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. In the history of quantum algorithms, the Deutsch algorithm and the Deutsch-Jozsa algorithm play a fundamental role and both are exact one-query quantum algorithms. This leads us to consider the problem: what functions can be computed by exact one-query quantum algorithms? This problem has been addressed in the literature for total Boolean functions and symmetric partial Boolean functions, but is still open for general partial Boolean functions. Thus, in this paper, we continue to characterize the computational power of exact one-query quantum algorithms for general partial Boolean functions. First, we present several necessary and sufficient conditions for a partial Boolean function to be computed by exact one-query quantum algorithms. Second, inspired by these conditions, we discover some new representative functions that can be computed by exact one-query quantum algorithms but have an essential difference from the already known ones. Specially, it is worth pointing out that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions and the quantum algorithm used is essentially the Deutsch-Jozsa algorithm, whereas the functions discovered in this paper are generally asymmetric and new algorithms to compute these functions are required. Thus, this expands the class of functions that can be computed by exact one-query quantum algorithms. [ABSTRACT FROM AUTHOR]

We test the quantumness of IBM's quantum computer IBM Quantum System One in Ehningen, Germany. We generate generalised n-qubit GHZ states and measure Bell inequalities to investigate the n-party entanglement of the GHZ states. The implemented Bell inequalities are derived from non-adaptive measurement-based quantum computation (NMQC), a type of quantum computing that links the successful computation of a non-linear function to the violation of a multipartite Bell-inequality. The goal is to compute a multivariate Boolean function that clearly differentiates non-local correlations from local hidden variables (LHVs). Since it has been shown that LHVs can only compute linear functions, whereas quantum correlations are capable of outputting every possible Boolean function it thus serves as an indicator of multipartite entanglement. Here, we compute various non-linear functions with NMQC on IBM's quantum computer IBM Quantum System One and thereby demonstrate that the presented method can be used to characterize quantum devices. We find a violation for a maximum of seven qubits and compare our results to an existing implementation of NMQC using photons. [ABSTRACT FROM AUTHOR]

In this paper, we study the differential δ -uniform property of two position swapped Exponential Welch Costas (EWC) permutations on Z p - 1 and construct permutations with δ = 4 , 6 for different values of p. We calculate the number of swapped EWC permutations with differential uniformity 6 for primes of the form 4 d + 3 . For primes of the form 4 d + 1 , we obtain a lower bound on the number of swapped EWC permutations with differential uniformity 4. [ABSTRACT FROM AUTHOR]

As a mathematical scaffold for network science, graph theory abstracts complex systems into complex networks. However, graphs ignore the multiplicity of combinatorial relationships in network systems, leading to limitations in graph-based metrics reflecting the importance of nodes. To address the shortcomings of graphs in describing network complexity, this study proposes the use of co-occurrence pattern truth tables to represent the combinations of multiple nodes in a network. Based on this, the concept of positive sensitivity is proposed to measure one aspect of the importance of nodes in a network. In addition, network sensitivity is proposed to depict the robustness of the network. The proposed approach is verified to be workable with Monte Carlo simulations and a real network exemplified by the high-speed rail network, constructed with provincial capitals of China as nodes. The results in comparison with traditional graph theory-based indices show that both the nodes and the network are assessed with reasonable results different from those of the graph-derived metrics. This study focuses on the combinatorial relationships of nodes in networks, providing a new perspective for the analysis of complex networks. [ABSTRACT FROM AUTHOR]

Extended Boolean functions (EBFs) are one of the most important tools in cryptography and spreading sequence design in communication systems. In this paper, we use EBFs to design new sets of spreading sequences for non-orthogonal multiple access (NOMA), which is an emerging technique capable of supporting massive machine-type communications (mMTC) in 5 G and beyond. In this work, first p-ary complementary sequences are constructed using EBFs and then, these sequences are used to design new sets of non-orthogonal spreading sequence sets having very low coherence and peak to average power ratio (PAPR). The proposed spreading sequence sets are capable of supporting a large number of active devices simultaneously. In fact, for a p-ary spreading sequence set, we theoretically achieve an overloading factor of 2p, where p is an odd prime. Specifically, for p = 3 , we achieve an overloading factor of 6, which cannot be achieved through the existing constructions till date. [ABSTRACT FROM AUTHOR]

In this work, we study quantum versions of attribute-based encryption schemes. Attribute-based encryption enables fine-grained access control of encrypted data using authorization policies. The secret key of a user and the ciphertext are dependent upon attributes, and the decryption of a ciphertext is possible only if the set of attributes of the user key matches the attributes of the ciphertext. Most of the existing classical attribute-based schemes are based on the hardness of the bilinear Diffie–Hellman problem, which has been proven to be vulnerable against Shor's algorithm. No efficient quantum attribute-based encryption scheme has been reported till date. In this backdrop, we propose quantum attribute-based encryption schemes exploiting quantum key distribution and quantum error-correcting codes. Attribute-based scheme is a special case of a more general functional encryption scheme whose quantum version we consider next hence giving this work a unifying framework. We present two constructions of quantum functional encryption schemes. The first construction generalizes the traditional notion of functional encryption and can handle multiple functions. The second construction utilizes the quantum query complexities of different Boolean functions. As applications, we present a quantum progressive functional encryption scheme to suitably encrypt an image to be shared among data users with hierarchical relations between them and outline a connection between quantum functional encryption schemes and obfuscated quantum states. In this work, we use weak measurements, which help us to expand our horizon to include encryption schemes in the dishonest model and quantum communication in the presence of an adversary. Our methods are unconditional and do not depend on the known difficulty of problems like lattice-based problems. Finally, we discuss various advantages of our methods and results. [ABSTRACT FROM AUTHOR]

Goldreich's pseudorandom generator is a well-known building block for many theoretical cryptographic constructions from multi-party computation to indistinguishability obfuscation. Its unique efficiency comes from the use of random local functions: each bit of the output is computed by applying some fixed public n-variable Boolean function f to a random public size-n tuple of distinct input bits. The characteristics that a Boolean function f must have to ensure pseudorandomness is a puzzling issue. It has been studied in several works and particularly by Applebaum and Lovett (STOC 2016) who showed that resiliency and algebraic immunity are key parameters in this purpose. In this paper, we propose the first study on Boolean functions that reach together maximal algebraic immunity and high resiliency. (1) We assess the possible consequences of the asymptotic existence of such optimal functions. We show how they allow to build functions reaching all possible algebraic immunity-resiliency trade-offs (respecting the algebraic immunity and Siegenthaler bounds). We provide a new bound on the minimal number of variables n, and thus on the minimal locality, necessary to ensure a secure Goldreich's pseudorandom generator. Our results come with a granularity level depending on the strength of our assumptions, from none to the conjectured asymptotic existence of optimal functions. (2) We extensively analyze the possible existence and the properties of such optimal functions. Our results show two different trends. On the one hand, we were able to show some impossibility results concerning existing families of Boolean functions that are known to be optimal with respect to their algebraic immunity, starting by the promising XOR-MAJ functions. We show that they do not reach optimality and could be beaten by optimal functions if our conjecture is verified. On the other hand, we prove the existence of optimal functions in low number of variables by experimentally exhibiting some of them up to 12 variables. This directly provides better candidates for Goldreich's pseudorandom generator than the existing XOR-MAJ candidates for polynomial stretches from 2 to 6. [ABSTRACT FROM AUTHOR]

Given a convex function Φ : [ 0 , 1 ] → R and the mean E f (X) = a ∈ [ 0 , 1 ] , which Boolean function f maximizes the Φ -stability E [ Φ (T ρ f (X)) ] of f? Here X is a random vector uniformly distributed on the discrete cube { - 1 , 1 } n and T ρ is the Bonami–Beckner operator. Special cases of this problem include the (symmetric and asymmetric) α -stability problems and the "Most Informative Boolean Function" problem. In this paper, we provide several upper bounds for the maximal Φ -stability. When specializing Φ to some particular forms, by these upper bounds, we partially resolve Mossel and O'Donnell's conjecture on α -stability with α > 2 , Li and Médard's conjecture on α -stability with 1 < α < 2 , and Courtade and Kumar's conjecture on the "Most Informative Boolean Function" which corresponds to a conjecture on α -stability with α = 1 . Our proofs are based on discrete Fourier analysis, optimization theory, and improvements of the Friedgut–Kalai–Naor (FKN) theorem. Our improvements of the FKN theorem are sharp or asymptotically sharp for certain cases. [ABSTRACT FROM AUTHOR]

Binary decision diagram (BDD) is used for technology-independent optimization, performed as the first stage in the synthesis of logic circuits in the design of application-specific integrated circuits (ASICs). BDD is an acyclic graph defining a Boolean function or a system of Boolean functions. Each vertex of this graph is associated with the complete or reduced Shannon expansion formula. Binary decision diagrams with mutually inverse subfunctions (cofactors) are considered. We have developed algorithms for finding algebraic representations of cofactors of the same BDD level in the form of a disjunction or conjunction of other inverse or non-inverse cofactors of the same BDD level. The algorithms allow reducing the number of literals by replacing the Shannon expansion formulas of a system of Boolean functions. It is proposed to use the developed algorithms for an additional logic optimization of the constructed BDD representations of systems of Boolean functions. The experimental results of application of the corresponding programs in synthesizing the logic circuits in the design library of custom VLSI CMOS circuits are presented. [ABSTRACT FROM AUTHOR]

The problems of synthesis of combinational circuits of code converters designed to reduce the length of words from a given set of encoded binary words is considered. The encoding assumes that different binary words will be encoded by different binary codes of shorter length. Code converters of this type are designed to reduce the length of binary words transmitted in digital systems over data buses when the bit depth of the transmitted words exceeds the bit depth of the data bus. For example, 18-bit or 17-bit words need to be transmitted over a 16-bit data bus. Each such word can be transmitted in two cycles of operation of a digital system; however, this approach reduces the overall performance of the system. One of the approaches to solve such problems is the development of combinational circuits that convert long binary encoded words into shorter ones. The proposed methods for solving the problem of synthesizing circuits of code converters are based on the compilation and logical minimization of such forms of systems of incompletely specified Boolean functions as disjunctive normal forms (DNFs) and binary decision diagrams called BDD representations. Using BDDs to minimize representations of k-valued functions that depend on Boolean variables is also proposed. Technology-independent logical minimization of functional descriptions of the designed code converters is proposed to be performed by programs for minimizing the systems of Boolean functions in the DNF class and programs for joint minimization of BDD representations of systems of completely specified Boolean functions. Minimization of functional descriptions is aimed at reducing the hardware complexity of combinational circuits in the basis of library elements or FPGA elements implementing code converters of the class in question. [ABSTRACT FROM AUTHOR]

Boolean networks (BNs) are well-studied models of genomic regulation in biology where nodes are genes and their state transition is controlled by Boolean functions. We propose to learn Boolean functions as Boolean formulas in disjunctive normal form (DNFs) by an explainable neural network Mat_DNF and apply it to learning BNs. Directly expressing DNFs as a pair of binary matrices, we learn them using a single layer NN by minimizing a logically inspired non-negative cost function to zero. As a result, every parameter in the network has a clear meaning of representing a conjunction or literal in the learned DNF. Also we can prove that learning DNFs by the proposed approach is equivalent to inferring interpolants in logic between the positive and negative data. We applied our approach to learning three literature-curated BNs and confirmed its effectiveness. We also examine how generalization occurs when learning data is scarce. In doing so, we introduce two new operations that can improve accuracy, or equivalently generalizability for scarce data. The first one is to append a noise vector to the input learning vector. The second one is to continue learning even after learning error becomes zero. The first one is explainable by the second one. These two operations help us choose a learnable DNF, i.e., a root of the cost function, to achieve high generalizability. [ABSTRACT FROM AUTHOR]

When analyzing the security of block ciphers and stream ciphers, the r - t h order nonlinearity of a Boolean function is crucial. They also have a prominent place in coding theory because the r - t h order nonlinearity of Boolean functions is connected to the covering radius of R M (r , m) , i.e., Reed-Muller code. In this study, we determine the lower bound for the higher-order nonlinearity of the two classes of Boolean functions listed below. f α (u) = t r 1 m (α u d) , where d is the Niho exponent constructed by Dobbertin et al. (J. Comb. Theory Ser. A 113:779–798, 2006). g α (u) = t r 1 m (α u d) , where d = 2 p - 2 . For all u ∈ F 2 m , α ∈ F 2 m ∗ and m = 2 p . [ABSTRACT FROM AUTHOR]

This work surveys mathematical aspects of division property, which is a state-of-the-art technique in cryptanalysis of symmetric-key algorithms, such as authenticated encryption, block ciphers and stream ciphers. It aims to find integral distinguishers and cube attacks, which exploit weaknesses in the algebraic normal forms of the output coordinates of the involved vectorial Boolean functions. Division property can also be used to provide arguments for security of primitives against these attacks. The focus of this work is a formal presentation of the theory behind the division property, including rigorous proofs, which were often omitted in the existing literature. This survey covers the two major variants of division property, namely conventional and perfect division property. In addition, we explore relationships of the technique with classic degree bounds. [ABSTRACT FROM AUTHOR]

A novel image cryptographic scheme is introduced in this paper. The proposed method incorporates two modules: confusion module and diffusion module. A dynamic key, changed for every input image is generated, and employed as a base to produce sub-keys in both confusion and diffusion mechanisms. This dynamics conducted to random-like key-generation, rendered the cryptographic scheme with dynamic encryption structure, and hence only one round is needed to achieve good combination between efficient time-consuming and sufficient security. In the confusion module, pixels' positions are non-linearly first forwardly permuted and then backwardly permuted, without changing their values, aiming to de-correlate the relations among neighboring pixels. In the diffusion module, pixels' values are changed, firstly discrete dynamical system with delay defined by non-linear boolean function is employed, in which each pixel value is non-linearly modified to achieve the mixing effect of pixel value and introduce more the non-linearity property, and then memory reversible two-dimensional cellular automata is performed, in which each pixel value is sequentially modified to further attain high diffusion mechanism. We have conducted the most important experiments to assess the effectiveness of the proposed cryptographic scheme. The obtained results are interesting in terms of security degrees and time-consuming, and point to the advocacy of proposal and its suitability to be a good encryption candidate for constrained environments. [ABSTRACT FROM AUTHOR]

Boolean satisfiability (SAT) is widely used as a solver engine in electronic design automation (EDA). Typically, SAT is used to determine whether one or more groups of variables can be combined to form a true formula. All solutions SAT (AllSAT) is a variant of the SAT problem. In the fields of formal verification and pattern generation, AllSAT is particularly useful because it efficiently enumerates all possible solutions. In this paper, a semi-tensor product (STP) based AllSAT solver is proposed. The solver can solve instances described in both the conjunctive normal form (CNF) and circuit form. The implementation of our method differs from incremental enumeration because we do not add blocking conditions for existing solutions, but rather compute the matrices to obtain all the solutions in one pass. Additionally, the logical matrices support a variety of logic operations. Results from experiments with MCNC benchmarks using CNF-based and circuit-based forms show that our method can accelerate CPU time by 8.1x (238x maximum) and 19.9x (72x maximum), respectively. [ABSTRACT FROM AUTHOR]

The construction and development of new techniques for a nonlinear multivalued Boolean function is one of the important aspects of modern ciphers. These multivalued Boolean functions need to be defined over various algebraic structures which map multiple inputs on multiple outputs. Modern block ciphers are a combination of linear and nonlinear functions which adds diffusion and confusion capabilities. We have offered an innovative system for the construction of the confusion component of block cipher by using recurrent neural networks. Since the confusion component is a multivalued Boolean function, therefore, we need many to many types of recurrent networks with an equal number of inputs and outputs. With this scheme, we have achieved a standard benchmark nonlinear of 112 with balancednesss having low linear and differential probabilities. We evaluated some common and advanced measures for the eminence of randomness and cryptanalytics to observe the efficiency of the proposed methodology. These outcomes validated the generated nonlinear confusion components are effective for block ciphers and have better cryptographic strength in image encryption with a high signal-to-noise ratio in comparison to state-of-the-art techniques. [ABSTRACT FROM AUTHOR]

Boosted by cryptography and coding theory applications and rich connections to objects from geometry and combinatorics, bent functions and related functions developed into a lively research area. In the mid-seventies, Rothaus initially introduced bent functions in the Boolean case, but later, they extended in the p-ary case where p is any prime. Such an extension brought more rich connections to bent functions. In addition to the theory of Fourier transform, handling p-ary bent functions (where p is an odd prime), analyzing their properties and designing them require using the theory of cyclotomic fields. Such a family is classified into weakly regular bent and regular bent. Compared to the Boolean case, the class of p-ary bent functions inherits a much larger variety of properties. For example, it contains the class of dual-bent functions as a proper subclass, which again includes weakly regular bent functions as a proper subclass. Weakly regular bent functions can also be employed in many domains. In particular, they have been widely used in designing good linear codes for several applications (such as secret sharing and two-party computation), association schemes, and strongly regular graphs. More exploration is still needed despite a lot of interest and attention in this topic to increase our knowledge of bent functions and design them. In particular, only a few constructions of weakly regular bent functions have been presented in the literature. Nice construction methods of these functions have been given by Tang et al (IEEE Trans Inf Theory 62(3):1166–1176, 2016). All the known infinite families of weakly regular bent functions belong to a class (denoted by Tang et al. in the previous reference) R F . This paper is devoted to weakly regular bent functions, and its objective is twofold. First, it aims to generate new infinite families of weakly regular bent functions living outside R F and secondly, to exploit the constructed functions to design new families of p-ary linear codes and investigate their use for some standard application after studying this minimality based on their weight distributions. More specifically, we present several classes of weakly regular bent functions obtained from monomial bent functions by modifying the values of some known weakly regular bent functions on some subsets of the finite field F p n (n is a positive integer). Our weakly regular bent functions are of degree either p or p + 1 2 . We also explicitly determine their corresponding dual functions. Finally, we exploit our constructions to derive four new classes of linear codes with three to seven weights. We also show that two of them lead to minimal codes, which are more appropriate for several concrete applications. [ABSTRACT FROM AUTHOR]

Various systematic modifications of vectorial Boolean functions have been used for finding new previously unknown classes of S-boxes with good or even optimal differential uniformity and nonlinearity. In this paper, a new general modification method is given that preserves the bijectivity property of the function in case the inverse of the function admits a linear structure. A previously known construction of such a modification based on bijective Gold functions in odd dimension is a special case of the new method. [ABSTRACT FROM AUTHOR]

In this paper, we investigate when a balanced function can be a derivative of a bent function. We prove that every nonconstant affine function in an even number of variables n is a derivative of (2 n - 1 - 1) ∣ B n - 2 ∣ 2 bent functions, where B n is the set of all bent functions in n variables. Based on this result, we propose a new iterative lower bound for the number of bent functions. We study the property of balanced functions that depend linearly on at least one of their variables to be derivatives of bent functions. We show the connection between this property and the "bent sum decomposition problem". We use this connection to prove that if a balanced quadratic Boolean function is a derivative of a Boolean function, then this function is a derivative of a bent function. [ABSTRACT FROM AUTHOR]

Bent functions are maximally nonlinear Boolean functions. They are important functions introduced by Rothaus and studied firstly by Dillon and next by many researchers for more than four decades. A systematic construction method of bent functions by modifying the support of Rothaus's bent function was given in Su (IEEE Trans Inf Theory 66(5):3277–3291, 2020). In this paper, we give a further study on that construction method. Two more flexible construction methods of bent functions by modifying the support of Rothaus's bent function are given respectively. The newly constructed bent functions contain the result in Su (2020), which is simply a special subclass of the newly constructed bent functions. The dual functions of these bent functions are determined. The methods of constructing self-dual bent functions are given. And the numbers of the newly constructed bent functions are also presented. [ABSTRACT FROM AUTHOR]

In this paper, we present a generalisation of the Phase Kick-Back technique, which is central to some of the classical algorithms in quantum computing. We will begin by recalling the Phase Kick-Back technique to then introduce the new generalised version for f : { 0 , 1 } n → { 0 , 1 } m functions using the eigenvalues of the oracle function U f . After that, we will present a new generalised version of the Deutsch–Jozsa problem and how it can be solved using the previously defined technique. We will also deal with a generalised version of the Bernstein–Vazirani problem and solve it using the generalised Phase Kick-Back. Finally, we show how we can use this technique to obtain an algorithm for Simon's problem that improves the classical one. [ABSTRACT FROM AUTHOR]

In this paper, a dual-gate silicon–germanium heterojunction vertical TFET with germanium as the source material (HJ-VTFET) is proposed for realizing compact logic functions. A single device with both gate terminals is biased independently during 2D simulation to understand fundamental two-input Boolean gates (OR, NAND, AND and NOR). The vital element in attaining various logic functions using double-gate vertical TFET is deploying a gate–source connection with an appropriate choice of silicon body thickness. The OR and NAND gates are realized using n-type and p-type HJ-VTFETs, respectively, by applying an independent voltage at both gates. While the AND and NOR gates are realized using n-type and p-type HJ-VTFETs, respectively, employing the gate–source overlap method. These implementations show that an exclusive feature of TFETs, such as ambipolar conduction with tunneling dependent on gate–source overlapping, can be realized for logic functions. With such a compact implementation with HJ-VTFET, the present work revealed some serious problems, such as a large subthreshold swing (SS), a small ON-state current ( I ON ), and high propagation delay ( τ D ). For AND functionality, in contrast to pure Si-based-VTFET (Si-VTFET), the HJ-VTFET raised I ON / I OFF via 3rd-order magnitude with around 67% improvement in SS. Further, an OR gate is realized with proposed HJ-VTFET and revealed less τ D around 0.012 nS, compared to the other gates realized using HJ-VTFET. [ABSTRACT FROM AUTHOR]

Quantum-dot cellular automata (QCA) is a field coupling nano-technology that has drawn significant attention for its low power consumption, low area overhead, and achieving a high speed over the CMOS technology. Majority Voter (MV) and QCA Inverter (INV) are the primitive logic in QCA for implementing any QCA circuit. The performance and cost of a QCA circuit directly depend on the number of QCA primitives and their interconnections. Their optimization plays a crucial role in optimizing the QCA logic circuit synthesis. None of the previous works considered elitism in GA, all the optimization objectives (MV, INV and Level), and the redundancy elimination approach. These profound issues lead us to propose a new methodology based on Genetic algorithm (GA) for the cost-effective synthesis of the QCA circuit of the multi-output boolean functions with an arbitrary number of inputs. The proposed method reduces the delay and gate count, where the worst-case delay is minimized in terms of the level. This methodology adapts elitism to preserve the best solutions throughout the intermediate generations. Here, MV, INV, and levels are optimized according to their relative cost factor in a QCA circuit. Moreover, new methodologies are proposed to create the initial population, maintain the variations, and eliminate redundant gates. Simulation results endorse the superiority of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the properties of the derivative of a special function, and propose a general approach to estimating a class of trigonometric sums based on the derivative of the special function. Then we apply the approach to three trigonometric sums and get three new estimates. Using the estimate of the first trigonometric sum, we deduce new upper and lower bounds of the arithmetic mean value for a trigonometric sum of Vinogradov. Using the estimate of the second trigonometric sum, we derive a new upper bound on the imbalance properties of Linear Feedback Shift Register subsequences. We also deduce a new lower bound on the nonlinearity of the Carlet–Feng vectorial Boolean function with the estimate of the third trigonometric sum. [ABSTRACT FROM AUTHOR]

We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in Quasi - NP = NTIME [ n (log n) O (1) ] and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes C , by showing that C admits non-trivial satisfiability and/or # SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial # SAT algorithm for a circuit class C . Say that a symmetric Boolean function f(x1,...,xn) is sparse if it outputs 1 on O(1) values of ∑ i x i . We show that for every sparse f, and for all "typical" C , faster # SAT algorithms for C circuits imply lower bounds against the circuit class f ∘ C , which may be stronger than C itself. In particular: # SAT algorithms for nk-size C -circuits running in 2n/nk time (for all k) imply NEXP does not have (f ∘ C) -circuits of polynomial size. # SAT algorithms for 2 n ε -size C -circuits running in 2 n − n ε time (for some ε > 0) imply Quasi-NP does not have (f ∘ C) -circuits of polynomial size. Applying # SAT algorithms from the literature, one immediate corollary of our results is that Quasi-NP does not have EMAJ ∘ ACC0 ∘ THR circuits of polynomial size, where EMAJ is the "exact majority" function, improving previous lower bounds against ACC0 [Williams JACM'14] and ACC0 ∘THR [Williams STOC'14], [Murray-Williams STOC'18]. This is the first nontrivial lower bound against such a circuit class. [ABSTRACT FROM AUTHOR]

We prove that each of the Boolean functions , can be implemented by a logic circuit in each of the bases , , , allowing a complete diagnostic test of length not exceeding (for the first two bases) or not exceeding (for the third basis) relative to one-type stuck-at faults at outputs of gates. We also establish that each of the functions , can be implemented by a logic circuit in the basis allowing a complete diagnostic test of length not exceeding relative to arbitrary stuck-at faults at outputs of gates. [ABSTRACT FROM AUTHOR]

The need for computation speed is ever increasing. A promising solution for this requirement is parallel computing but the degree of parallelism in electronic computers is limited due to the physical and technological barriers. DNA computing proposes a fascinating level of parallelism that can be utilized to overcome this problem. This paper presents a new computational model and the corresponding design methodology using the massive parallelism of DNA computing. We proposed an automatic design algorithm to synthesis the logic functions on the DNA strands with the maximum degree of parallelism. In the proposed model, billions of DNA strands are utilized to compute the elements of the Boolean function concurrently to reach an extraordinary level of parallelism. Experimental and analytic results prove the feasibility and efficiency of the proposed method. Moreover, analyses and results show that a delay of a circuit in this method is independent of the complexity of the function and each Boolean function can be computed with O(1) time complexity. [ABSTRACT FROM AUTHOR]

Boolean functions naturally induce binary sequences of length 2 m and a large number of such orthogonal sequences is required in the design of code-division multiple-access (CDMA) systems. In this paper, Boolean functions are used to construct nonlinear phase orthogonal sequence sets for CDMA communications. For even m, employing carefully designed an m-variable Boolean function with five-valued Walsh spectra, one can get 16 different orthogonal sequence sets with sequence length 2 m . These sequence sets are assigned to a lattice of regular hexagonal cells, and we can ensure the orthogonality of adjacent cells. Moreover, the cross-correlation values between the sequences in a given cell and the sequences in non-neighbouring cells belong to { 0 , ± 2 m 2 , ± 2 m 2 + 1 } . On the other hand, the cardinality of the sequences sets is 2 m - 3 thus implying a trade-off between the quality of communication and the number of users assigned to each cell. This method can be improved so that the number of users is increased to 2 m - 2 in one half of the network while preserving the orthogonality between adjacent cells and the same level of low cross-correlation values to the non-neighbouring cells. [ABSTRACT FROM AUTHOR]