Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-090 | 3rd December 2000 00:00

Candidate One-Way Functions Based on Expander Graphs


Authors: Oded Goldreich
Publication: 4th December 2000 09:05
Downloads: 1416


We suggest a candidate one-way function using combinatorial
constructs such as expander graphs. These graphs are used to
determine a sequence of small overlapping subsets of input bits,
to which a hard-wired random predicate is applied.
Thus, the function is extremely easy to evaluate:
all that is needed is to take multiple projections of the
input bits, and to use these as entries to a look-up table.
It is feasible for the adversary to scan the look-up table,
but we believe it would be infeasible to find an input that fits a given
sequence of values obtained for these overlapping projections.

The conjectured difficulty of inverting the suggested function
does not seem to follow from any well-known assumption.
Instead, we propose the study of the complexity of inverting
this function as an interesting open problem,
with the hope that further research will provide evidence to our
belief that the inversion task is intractable.

ISSN 1433-8092 | Imprint