In the past twenty years, there were only a few constructions for Boolean functions with nonlinearity exceeding the quadratic bound 2n-1-2(n-1)/2 when n is odd (we shall call them Boolean functions with very high nonlinearity). The first basic construction was by Patterson and Wiedemann in 1983, which produced unbalanced function with very high nonlinearity. But for cryptographic applications, we need balanced Boolean functions. Therefore in 1993, Seberry, Zhang and Zheng proposed a secondary construction for balanced functions with very high nonlinearity by taking the direct sum of a modified bent function with the Patterson-Wiedemann function. Later in 2000, Sarkar and Maitra constructed such functions by taking the direct sum of a bent function with a modified Patterson-Wiedemann function. In this paper, we propose a new secondary construction for balanced Boolean functions with very high nonlinearity by recursively composing balanced functions with very high nonlinearity with quadratic functions. This is the first construction for balanced function with very high nonlinearity not based on the direct sum approach. Our construction also have other desirable properties like high algebraic degree and large linear span.

Binary sequences with two-level periodic autocorrelation correspond directly to cyclic (v, k, λ)-designs. When v = 4t-1, k = 2t -1 and λ = t-1, for some positive integer t, the sequence (or design) is called a cyclic Hadamard sequence (or design). For all known examples, v is either a prime number, a product of twin primes, or one less than a power of 2. Except when v = 2k-1, all known examples are based on quadratic residues (using the Legendre symbol when v is prime, and the Jacobi symbol when v = p(p+2) where both p and p+2 are prime); or sextic residues (when v is a prime of the form 4a2 + 27). However, when v = 2k-1, many constructions are now known, including m-sequences (corresponding to Singer difference sets), quadratic and sextic residue sequences (when 2k-1 is prime), GMW sequences and their generalizations (when k is composite), certain term-by-term sums of three and of five m-sequences and more general sums of trace terms, several constructions based on hyper-ovals in finite geometries (found by Segre, by Glynn, and by Maschietti), and the result of performing the Welch-Gong transformation on some of the foregoing.