Analysis on Boolean function in a restricted (biased) domain
2019IEEE_Flip.pdf (444.8Kb)Abstract
distributed. However, in the case of some stream ciphers, a keystream bit is generated by using a nonlinear Boolean function with inputs from a restricted domain. At Eurocrypt 2016, one such stream cipher (FLIP) has been proposed, where a Boolean function on n variables was exploited with inputs of weight n only. Recently, Carlet et al. studied several 2 properties of such functions and obtained certain bounds on linear approximations of direct sum in the restricted domain. In this paper, we observe that for a direct sum like f = f1 + f2 , the inputs to each sub-function f1, f2 do not follow a uniform distribution in the restricted domain. In this regard, we study the properties of Boolean functions by considering a general probability distribution on the inputs. We further obtain several bounds related to the biases of direct sums. Finally, we obtain a lower bound on the bias of the nonlinear filter function of FLIP. Our results provide a general framework to study security parameters of ciphers over restricted domain.
Description
This is a substantially revised and extended version of the paper [7] that appeared in the proceedings of Indocrypt 2018. This version includes additional results in Sections II-A III-A, III-B, III-C, III-D. Some results of [7] have been abridged and one may refer to [7] for other details. This paper has more than 50% new contributions over the conference version [7].
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.Collections
Related items
Showing items related by title, author, creator and subject.
-
Cryptographic Boolean functions with biased inputs
(2015-07-31);While performing cryptanalysis, it is of interest to approximate a Boolean function in n variables f : Fn → F2 by affine functions. Usually, it is assumed that all the input vectors to a Boolean function are equiprobable ... -
Applications of probabilistic combiners on linear feedback shift register sequences
(Monterey, California: Naval Postgraduate School, 2016-12);Cryptography forms the backbone of modern secure communication. Many different methods are available for encrypting and decrypting data, each with advantages and disadvantages. If communicating parties require speed of ... -
The Fourier Entropy-Influence Conjecture Holds for a Log-Density 1 Class of Cryptographic Boolean Functions
(2014-01-25);We consider the Fourier Entropy-Infl uence (FEI) conjecture in the context of cryptographic Boolean functions. We show that the FEI con jecture is true for the functions satisfying the strict avalanche criterion, ...
