A New Class of Feebly One-Way Permutations
by
Carmelo Interlando
Department of Mathematics & Statistics, San Diego State University, San Diego, CA, USA
Coauthors: Michele Elia

Trapdoor one-way functions (OWF) are one of the main building blocks of public-key cryptographic systems. Without them, the latter are rendered insecure. Informally, a trapdoor OWF is a function f: X -> Y that is “easy” to compute, but for “essentially all” y in Y , it is “computationally infeasible” to find x in X such that f(x)=y, unless one possesses extra information known as trapdoor information. Rigorous definitions for the notion of one-wayness have been provided, however no function has ever been proved to satisfy any of them. Practical systems use functions that are "believed" to be one-way. This argument shows the necessity to have mathematically rigorous proofs that certain “candidate” functions are (or not) OWF. In principle, such proofs can be achieved via complexity of Boolean functions. Here, the function f is regarded as a map from {0, 1}^n to {0, 1}^m and we define the complexity of f as the size of the smallest circuit (in terms of the number of gates) that realizes it. Having this definition in mind, in this talk we will present a family of linear functions that satisfy a weaker notion of one-wayness, namely, “feebly one-way” functions.

PDF

Date received: July 9, 2007