AbstractIn designing cryptographic Boolean functions, it is challenging to achieve at the same time the desirable features of algebraic immunity, balancedness, nonlinearity, and algebraic degree for necessary resistance against algebraic attack, correlation attack, Berlekamp–Massey attack, etc. This paper constructs balanced rotation symmetric Boolean functions on n variables where n=2p and p is an odd prime. We prove the construction has an optimal algebraic immunity and is of high nonlinearity. We check that, at least for those primes p which are not of the form of a power of two plus one, the algebraic degree of the construction achieves in fact the upper bound n−1.

AbstractWe revisit the problem of basing pseudorandom generators on regular one-way functions, and present the following constructions:•For any known-regular one-way function (on n-bit inputs) that is known to be ε-hard to invert, we give a neat (and tighter) proof for the folklore construction of pseudorandom generator of seed length Θ(n) by making a single call to the underlying one-way function.•For any unknown-regular one-way function with known ε-hardness, we give a new construction with seed length Θ(n) and O(n/log(1/ε)) calls. Here the number of calls is also optimal by matching the lower bounds of Holenstein and Sinha (2012) [6]. Both constructions require the knowledge about ε, but the dependency can be removed while keeping nearly the same parameters. In the latter case, we get a construction of pseudo-random generator from any unknown-regular one-way function using seed length O˜(n) and O˜(n/logn) calls, where O˜ omits a factor that can be made arbitrarily close to constant (e.g. logloglogn or even less). This improves the randomized iterate approach by Haitner et al. (2006) [4] which requires seed length O(n⋅logn) and O(n/logn) calls.