Cryptology ePrint Archive: Report 2000/063

Candidate One-Way Functions Based on Expander Graphs

Oded Goldreich

Abstract: 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.

Category / Keywords: foundations / One-Way Functions, Expander Graphs

Date: received 3 Dec 2000

Contact author: oded at wisdom weizmann ac il

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20001203:202312 (All versions of this report)

Short URL: ia.cr/2000/063

Discussion forum: Show discussion | Start new discussion