Couceiro, Miguel Mercuriali, Pierre Péchoux, Romain Saffidine, Abdallah

In this document, we consider a median-based calculus to represent monotone Boolean functions efficiently. We study an equa-tional specification of median forms and extend it from the domain of monotone Boolean functions to the domain of polynomial functions over distributive lattices. This specification is sound and complete. We illustrate its use...

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

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

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

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

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

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

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

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.

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