Ahmed, Taghreed Younes, Ahmed Elsayed, Ashraf
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...

Todo, Yosuke Leander, Gregor Sasaki, Yu
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...

Rychkov, K. L.
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.

Carlet, Claude
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...

Tahmasebi, Masoumeh Faghih Mirzaee, Reza Pishgar Komleh, Seyyed Hossein
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...

Chashkin, Aleksandr V.
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...

albert, no

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...

Voronenko, A. A.
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...

Redkin, Nikolay P.
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 ...

Grabovskaya, S. M. Alekhina, M. A.
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...