The improved Levin’s algorithm for constrained probabilistic pseudo-Boolean functions

The problem of finding “highly probable” approximations of Boolean functions consists in generating a list of all linear Boolean functions that agree with a given Boolean function in at least a specified number of binary sets. If a Boolean function is given by its truth table, the most well-known algorithm for solving this problem is the Fast Hadamard Transform. However, this method is not optimal in terms of complexity, even among deterministic algorithms. If the Boolean function is given by an oracle and depends on hundreds or thousands of variables, the application of deterministic algorithms for finding its linear approximations becomes practically infeasible. In this case, polynomial probabilistic algorithms are used, such as the Goldreich–Levin algorithm and its modifications. One of the fastest among them currently is the improved Levin’s algorithm. In the language of coding theory, this algorithm performs list decoding of the Hadamard code, which involves the value vectors of all n-variable linear Boolean functions. This paper presents a generalization of the improved Levin’s algorithm to the case of constrained probabilistic pseudo-Boolean functions. The main result is a theorem establishing a lower bound on the probability that each sought approximation appears in a random list generated by the proposed algorithm. The consideration of such functions is necessary to extend the applicability of the improved Levin’s algorithm (in place of the original Goldreich–Levin algorithm) within the well-known framework for proving the security of stream ciphers. In particular, the results of this paper enable a more efficient reduction of problems in proofs of pseudo-randomness for certain well-known keystream generators, assuming high computational complexity of decoding random linear block codes or solving random systems of nonlinear Boolean equations. The obtained results can also be used for finding linear approximations of encryption transformations of block ciphers, which is important for constructing linear attacks against them.