Toward a Theory of One-Way Functions via Gate Complexity of Boolean Functions.

One of the most important properties of a cryptographic system is a proof of its security. There are two types of security: information (or theoretical) security and computational (or practical) security. The focus of this work is on provable computational security via gate (or circuit) complexity of Boolean functions. The computational security of public-key cryptographic systems depends fundamentally on trapdoor one-way functions. However, the existence of such functions has yet to be proved. Informally speaking, a trapdoor one-way function is an efficiently-computable function such that there are no efficient algorithms for inverting it unless some extra information, known as trapdoor information, is available. It is important to realize that the so-called 'trapdoor one-way functions' used in modern cryptographic systems (to perform financial transactions over the internet, for example) are good candidates, at best. There is no formal proof that these candidates are de facto trapdoor one-way functions. For example, security proofs for one of the most widely used public-key cryptographic systems, namely, the RSA, are based on the unproven assumption that large numbers cannot be factored efficiently. Therefore, it is not safe to base the security of large economic systems on such assumptions. Thus, from a cryptographical point of view, the crucial problem in gate complexity theory is to prove nontrivial lower bounds on the complexity of breaking practical cryptographic systems, for example, one-way functions. In this work we argue that the theory of circuit complexity of Boolean functions provides the mathematical background to achieve provable computational security. Among computational models, the circuit model has an especially simple definition and may be more amenable to combinatorial analysis. The gate complexity of permutations of GF(2ⁿ) and of linear and quadratic Boolean functions is studied by deriving bounds on the number of modulo-two additions and multiplications necessary to realize them.