Generalization of Matsui’s Algorithm 1 to linear hull for key-alternating block ciphers

We consider linear approximations of an iterated block cipher in the presence of several strong linear approximation trails. While the effect of such trails in Matsui’s Algorithm 2, also called the linear hull effect, has been previously studied by a number of authors, their effect on Matsui’s Algorithm 1 has not been investigated until now. The goal of this paper is to fill this gap and examine how to generalize Matsui’s Algorithm 1 to work also on linear hulls. We restrict to key-alternating ciphers and develop a mathematical framework for this kind of attacks. The complexity of the attack increases with the number of linear trails that have significant contribution to the correlation. We show how to reduce the number of trails and thus the complexity using related keys. Further, we illustrate our theory by experimental results on a reduced round version of the block cipher PRESENT.     

Connections Between Single-Level and Bilevel Multiobjective Optimization

The relationship between bilevel optimization and multiobjective optimization has been studied by several authors, and there have been repeated attempts to establish a link between the two. We unify the results from the literature and generalize them for bilevel multiobjective optimization. We formulate sufficient conditions for an arbitrary binary relation to guarantee equality between the efficient set produced by the relation and the set of optimal solutions to a bilevel problem. In addition, we present specially structured bilevel multiobjective optimization problems motivated by real-life applications and an accompanying binary relation permitting their reduction to single-level multiobjective optimization problems.     

On the exceptional set in Goldbach’s problem in short intervals

Let 1/5 < θ ≤ 1. We prove that there exists a positive constant δ such that the number of even integers in the interval [X, X + X ^θ] which are not a sum of two primes is 《 X ^θ−δ. The proof uses the circle method, a sieve method, exponential sum estimates and zero-density estimates for L-functions. Current address: Department of Mathematics, 20014 University of Turku, Finland. Author’s address: Department of Mathematics, University of London, Royal Holloway, Egham, Surrey TW20 0EX, UK