Published in Quantum Information Processing
This paper introduces a novel algorithm to synthesize a low-cost reversible circuits for any Boolean function with n inputs represented as a Positive Polarity Reed–Muller expansion. The proposed algorithm applies a predefined rules to reorder the terms in the function to minimize the multi-calculation of common parts of the Boolean function to decr...
Published in Journal of Cryptology
In this paper, we introduce a new type of attack, called nonlinear invariant attack. As application examples, we present new attacks that are able to distinguish the full versions of the (tweakable) block ciphers Scream, iScream and Midori64 in a weak-key setting. Those attacks require only a handful of plaintext–ciphertext pairs and have minimal c...
Published in Journal of Applied and Industrial Mathematics
Using Khrapchenko’s method, we obtain the exact lower bound of 40 for the complexity in the class of π-schemes of a linear Boolean function depending substantially on 6 variables. We give a simplified proof of several lower bounds for the complexity of linear Boolean functions which are previously obtained on the basis of the same method.
Published in Designs, Codes and Cryptography
In this paper, we summarize the results obtained recently in three papers on differentially uniform functions in characteristic 2, and presented at the workshop WCC 2017 in Saint-Petersburg, and we give new results on these functions. Firstly, we recall the recent connection between almost perfect nonlinear (APN) power functions and the two notions...
Published in Journal of Computational Electronics
Quantum-dot cellular automata (QCA) circuits are not based on transistors. Therefore, novel concepts and methodologies are required to be able to design Boolean functions in a systematic manner. Wire crossing is a problematic challenge in this technology, imposing considerable cost, complexity, and noise sensitivity. On the other hand, QCA circuits...
Published in Discrete Mathematics and Applications
The average-case complexity of computation of underdetermined functions by straight-line programs with conditional stop over the basis of all at most two-place Boolean functions is considered. Correct order estimates of the average-case complexity of functions with maximum average-case complexity among all underdetermined functions are derived depe...
Let X n be a memoryless uniform Bernoulli source and Y n be the output of it through a binary symmetric channel. Courtade and Kumar conjectured that the Boolean function f : { 0 , 1 } n → { 0 , 1 } that maximizes the mutual information I ( f ( X n ) / Y n ) is a dictator function, i.e., f ( x n ) = x i for some i. We propose a clustering problem, w...
Published in Computational Mathematics and Modeling
The following problem is considered: specify a Boolean function of n variables such that every bilinear (polylinear) function is reduced, on a certain number of tuples of the specified function, to a unique bilinear (polylinear) function that is identical with the specified function on these tuples. We show that this is feasible for bilinear functi...
Published in Discrete Mathematics and Applications
When investigating the complexity of implementing Boolean functions, it is usually assumed that the basis inwhich the schemes are constructed and the measure of the complexity of the schemes are known. For them, the Shannon function is introduced, which associates with each Boolean function the least complexity of implementing this function in the ...
Published in Lobachevskii Journal of Mathematics
The implementation of Boolean functions by non-branching programs with a conditional stop operator is considered in an arbitrary complete finite basis. We assume that conditional stop operators of the program are absolutely reliable while all computational operators are prone to the output one-type constant faults of either type 0 or type 1. An upp...
