zbMATH — the first resource for mathematics

Candidate one-way functions based on expander graphs. (English) Zbl 1306.94056
Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 76-87 (2011).
Summary: 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.
For the entire collection see [Zbl 1220.68005].

94A60 Cryptography
05C75 Structural characterization of families of graphs
05C90 Applications of graph theory
Full Text: DOI
[1] Applebaum, B., Barak, B., Wigderson, A.: Public-key cryptography from different assumptions. In: 42nd STOC, pp. 171–180 (2010) · Zbl 1293.94052 · doi:10.1145/1806689.1806715
[2] Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC0. SICOMP 36(4), 845–888 (2006) · Zbl 1126.94014 · doi:10.1137/S0097539705446950
[3] Alekhnovich, M., Ben-Sasson, E., Razborov, A., Wigderson, A.: Pseudorandom Generators in Propositional Proof Complexity. In: 41st FOCS, pp. 43–53 (2000) · Zbl 1096.03070 · doi:10.1109/SFCS.2000.892064
[4] Alon, N.: Eigenvalues, Geometric Expanders, Sorting in Rounds, and Ramsey Theory. Combinatorica 6, 207–219 (1986) · Zbl 0625.05026 · doi:10.1007/BF02579382
[5] Alon, N., Milman, V.D.: \(\lambda\) 1, Isoperimetric Inequalities for Graphs and Superconcentrators. J. Combinatorial Theory, Ser. B 38, 73–88 (1985) · Zbl 0549.05051 · doi:10.1016/0095-8956(85)90092-9
[6] Bogdanov, A., Qiao, Y.: On the Security of Goldreich’s One-Way Function. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol. 5687, pp. 392–405. Springer, Heidelberg (2009) · Zbl 1255.94053 · doi:10.1007/978-3-642-03685-9_30
[7] Cook, J., Etesami, O., Miller, R., Trevisan, L.: Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 521–538. Springer, Heidelberg (2009) · Zbl 1213.94092 · doi:10.1007/978-3-642-00457-5_31
[8] Gaber, O., Galil, Z.: Explicit Constructions of Linear Size Superconcentrators. JCSS 22, 407–420 (1981) · Zbl 0487.05045
[9] Goldreich, O., Goldwasser, S., Micali, S.: How to Construct Random Functions. JACM 33(4), 792–807 (1986) · Zbl 0596.65002 · doi:10.1145/6490.6503
[10] Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan Graphs. Combinatorica 8, 261–277 (1988) · Zbl 0661.05035 · doi:10.1007/BF02126799
[11] Nisan, N., Wigderson, A.: Hardness vs Randomness. JCSS 49(2), 149–167 (1994) · Zbl 0821.68057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.