This paper addresses the problem of obtaining new construction methods for cryptographically significant Boolean functions. We show that for each positive integer m, there are infinitely many integers n (both odd and even), such that it is possible to construct n-variable, m-resilient functions having nonlinearity greater than . Also we obtain better results than all published works on the construction of n-variable, m-resilient functions, including cases where the constructed functions have the maximum possible algebraic degree n − m − 1. Next we modify the Patterson-Wiedemann functions to construct balanced Boolean functions on n-variables having nonlinearity strictly greater than for all odd n ≥ 15. In addition, we consider the properties strict avalanche criteria and propagation characteristics which are important for design of S-boxes in block ciphers and construct such functions with very high nonlinearity and algebraic degree.