Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
From Indifferentiability to Constructive Cryptography (and Back) Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Fast Pseudorandom Functions Based on Expander Graphs

Authors : Benny Applebaum, Pavel Raykov

Published in: Theory of Cryptography

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We present direct constructions of pseudorandom function (PRF) families based on Goldreich’s one-way function. Roughly speaking, we assume that non-trivial local mappings \(f:\{0,1\}^n\rightarrow \{0,1\}^m\) whose input-output dependencies graph form an expander are hard to invert. We show that this one-wayness assumption yields PRFs with relatively low complexity. This includes weak PRFs which can be computed in linear time of O(n) on a RAM machine with \(O(\log n)\) word size, or by a depth-3 circuit with unbounded fan-in AND and OR gates (AC0 circuit), and standard PRFs that can be computed by a quasilinear size circuit or by a constant-depth circuit with unbounded fan-in AND, OR and Majority gates (TC0).
Our proofs are based on a new search-to-decision reduction for expander-based functions. This extends a previous reduction of the first author (STOC 2012) which was applicable for the special case of random local functions. Additionally, we present a new family of highly efficient hash functions whose output on exponentially many inputs jointly forms (with high probability) a good expander graph. These hash functions are based on the techniques of Miles and Viola (Crypto 2012). Although some of our reductions provide only relatively weak security guarantees, we believe that they yield novel approach for constructing PRFs, and therefore enrich the study of pseudorandomness.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter From Indifferentiability to Constructive Cryptography (and Back)
next chapter 3-Message Zero Knowledge Against Human Ignorance
Appendix
Available only for authorised users
Footnotes
1
A weak PRF is a relaxation of a PRF which is indistinguishable from a random function for an adversary whose queries are chosen uniformly at random.
 
2
In fact, it seems better to allocate a larger fraction of the inputs to the Majority part. See [AL15].
 
3
In Sect. 2 we provide a more general assumption which allows the hypergraph to be non-uniform, and is parameterized by an expansion parameter, by a predicate family \(\mathcal {P}\) and by a concrete bound on the security of the function in terms of the (circuit) size of the adversary and its success probability. The above assumption is given here in a simplified form for ease of presentation.
 
4
Formally, Assumption 1 implies that for a random hypergraph G, the function \(f_{G,P}\) is one-way (since such a hypergraph is likely to be expanding). Then, we can apply the result of [App13].
 
5
When analyzing parallel-complexity it is common to restrict the attention for the case where the key is fixed, cf. [NR95, NR97, NRR00, LW09, BMR10, MV12, ABG+14].
 
6
Technically, this requires an extension of our assumption to the case of non-uniform hypergraphs, and the ability to analyze the function with respect to new predicates (obtained by restricting some of the inputs of the original predicate).
 
7
We do not use general transformations from weak PRFs to standard PRFs (e.g., [NR97]) since they make a linear number of calls to the underlying weak PRF and therefore incur at least a quadratic overhead in the size of the resulting circuit.
 
8
An analogous use of public randomness appears in the seminal Goldreich-Levin theorem [GL89] which can be viewed as search-to-decision reduction for the keyed function \(f_k(x)=(g(x),\langle x,k \rangle )\).
 
9
It is not hard to show that if M by itself is a PRF then security holds for \(F_3\). The hope is to get somewhat weaker form of hiding, ideally, one which can be satisfied by some concrete and highly-efficient mapping M such as the one proposed here.
 
10
In the terminology of learning theory this means that a random function from the family is hard to weakly-predict over the uniform distribution.
 
11
Here and through the paper, we implicitly assume that for all \(i\in [m]\) the arity of the i-th predicate \(P_i\) matches the cardinality of the i-th hyperedge \(S_i\) of G.
 
12
The constants (1 / 3, 2 / 3) in the definition are somewhat arbitrary and it seems that any constants bounded away from 0 and 1 will do.
 
13
The choice of the last bit unpredictability is without loss of generality since we can permute the order of the bits of \(f_{G,P}\) (see [App13]).
 
14
Specifically, sample a random index \(\tau \in [n]\), and for every sub-hypergraph \(H'_{i,j}\) and hyperedge \(S\in H'_{i,j}\) swap the node \(\phi _i^j(\ell ^*)\) with the node \(\tau \), except for the first entry in the last hyperedge of \(H_{i,j}\) which \(\phi _i^j(\ell ^*)\) is replaced by j.
 
15
The construction can be easily generalized to handle non-uniform hypergraphs and/or different predicates d-ary predicates for each output.
 
Literature
[ABG+14]
Akavia, A., Bogdanov, A., Guo, S., Kamath, A., Rosen, A.: Candidate weak pseudorandom functions in AC\(^{0}\) MOD\(_{2}\). In: Naor, M. (ed.) Innovations in Theoretical Computer Science, ITCS 2014, Princeton, NJ, USA, 12–14 January 2014, pp. 251–260. ACM (2014)
[ABR12]
[ABW10]
Applebaum, B., Barak, B., Wigderson, A.: Public-key cryptography from different assumptions. In: Schulman, L.J. (ed.) Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5–8 June 2010, pp. 171–180. ACM (2010)
[AHI05]
Alekhnovich, M., Hirsch, E.A., Itsykson, D.: Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. J. Autom. Reasoning 35(1–3), 51–72 (2005)MathSciNetMATH
[AKS83]
Ajtai, M., Komlós, J., Szemerédi, E.: An o(n log n) sorting network. In: Johnson, D.S., Fagin, R., Fredman, M.L., Harel, D., Karp, R.M., Lynch, N.A., Papadimitriou, C.H., Rivest, R.L., Ruzzo, W.L., Seiferas, J.I. (eds.) Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, Massachusetts, USA, 25–27 April 1983, pp. 1–9. ACM (1983)
[AL15]
Applebaum, B., Lovett, S.: Algebraic attacks against random local functions, their countermeasures. In: Electronic Colloquium on Computational Complexity (ECCC), STOC 2016, vol. 22, p. 172 (2015, to appear)
[Ale03]
Alekhnovich, M.: More on average case vs approximation complexity. In: 44th Symposium on Foundations of Computer Science (FOCS 2003), Cambridge, MA, USA, Proceedings, 11–14 October 2003, pp. 298–307. IEEE Computer Society (2003)
[App13]
Applebaum, B.: Pseudorandom generators with long stretch, low locality from random local one-way functions. SIAM J. Comput. 42(5), 2008–2037 (2013). Preliminary version in STOC 2012MathSciNetMATHCrossRef
[App14]
Applebaum, B.: Bootstrapping obfuscators via fast pseudorandom functions. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 162–172. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-45608-8_​9
[App15]
Applebaum, B.: Cryptographic hardness of random local functions - survey. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 22, p. 27 (2015)
[AR16]
Applebaum, B., Raykov, P.: Fast pseudorandom functions based on expander graphs. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 23, p. 82 (2016). Full version of this paper
[BFKL93]
Blum, A., Furst, M., Kearns, M., Lipton, R.J.: Cryptographic primitives based on hard learning problems. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 278–291. Springer, Heidelberg (1994). doi:10.​1007/​3-540-48329-2_​24
[BH08]
[BH15]
[BMR10]
Boneh, D., Montgomery, H.W., Raghunathan, A.: Algebraic pseudorandom functions with improved efficiency from the augmented cascade. In: Al-Shaer, E., Keromytis, A.D., Shmatikov, V. (eds.) Proceedings of the 17th ACM Conference on Computer and Communications Security, CCS 2010, Chicago, Illinois, USA, 4–8 October 2010, pp. 131–140. ACM (2010)
[BPR12]
[BQ12]
[BR13]
[CEMT14]
Cook, J., Etesami, O., Miller, R., Trevisan, L.: On the one-way function candidate proposed by Goldreich. ACM Trans. Comput. Theor. 6(3), 1401–1435 (2014)MathSciNetCrossRef
[CGH+85]
Chor, B., Goldreich, O., Håstad, J., Friedman, J., Rudich, S., Smolensky, R.: The bit extraction problem of t-resilient functions (preliminary version). In: 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21–23 October 1985, pp. 396–407. IEEE Computer Society (1985)
[DI05]
Damgård, I., Ishai, Y.: Constant-round multiparty computation using a black-box pseudorandom generator. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 378–394. Springer, Heidelberg (2005). doi:10.​1007/​11535218_​23 CrossRef
[DLS14]
Daniely, A., Linial, N., Shalev-Shwartz, S.: From average case complexity to improper learning complexity. In: Shmoys, D.B. (ed.) Symposium on Theory of Computing, STOC 2014, New York, NY, USA, 31 May – 03 June 2014, pp. 441–448. ACM (2014)
[FPV15]
Feldman, V., Perkins, W., Vempala, S.: On the complexity of random satisfiability problems with planted solutions. In: Servedio, R.A., Rubinfeld, R. (eds.) Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, 14–17 June 2015, pp. 77–86. ACM (2015)
[GGM86]
[GL89]
Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: Johnson, D.S. (ed.) Proceedings of the 21st Annual ACM Symposium on Theory of Computing, Seattle, Washigton, USA, 14–17 May 1989, pp. 25–32. ACM (1989)
[Gol00]
Goldreich, O.: Candidate one-way functions based on expander graphs. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 7, no. 90 (2000)
[Gow96]
[GVW12]
Gorbunov, S., Vaikuntanathan, V., Wee, H.: Functional encryption with bounded collusions via multi-party computation. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 162–179. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-32009-5_​11 CrossRef
[GvzGPS00]
Gao, S., von Zur Gathen, J., Panario, D., Shoup, V.: Algorithms for exponentiation in finite fields. J. Symb. Comput. 29(6), 879–889 (2000)MathSciNetMATHCrossRef
[HILL99]
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999). Preliminary versions in STOC 1989 and STOC 1990MathSciNetMATHCrossRef
[HMMR05]
[IKOS08]
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: Dwork, C. (ed.) Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17–20, 2008, pp. 433–442. ACM (2008)
[Kha93]
Kharitonov, M.: Cryptographic hardness of distribution-specific learning. In: Kosaraju, S.R., Johnson, D.S., Aggarwal, A. (eds.) Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, San Diego, CA, USA, 16–18 May 1993, pp. 372–381. ACM (1993)
[KS09]
Klivans, A.R., Sherstov, A.A.: Cryptographic hardness for learning intersections of halfspaces. J. Comput. Syst. Sci. 75(1), 2–12 (2009)MathSciNetMATHCrossRef
[LF80]
[LMN93]
[LW09]
Lewko, A.B., Waters, B.: Efficient pseudorandom functions from the decisional linear assumption and weaker variants. In: Al-Shaer, E., Jha, S., Keromytis, A.D. (eds.) Proceedings of the 2009 ACM Conference on Computer and Communications Security, CCS 2009, Chicago, Illinois, USA, 9–13 November 2009, pp. 112–120. ACM (2009)
[MP75]
[MST03]
Mossel, E., Shpilka, A., Trevisan, L.: On e-biased generators in NC0. In: 44th Symposium on Foundations of Computer Science (FOCS 2003), Cambridge, MA, USA, Proceedings, 11–14 October 2003, pp. 136–145. IEEE Computer Society (2003)
[MV12]
Miles, E., Viola, E.: Substitution-permutation networks, pseudorandom functions, and natural proofs. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 68–85. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-32009-5_​5 CrossRef
[NN93]
Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput. 22(4), 838–856 (1993)MathSciNetMATHCrossRef
[NR95]
Naor, M., Reingold, O.: Synthesizers and their application to the parallel construction of psuedo-random functions. In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, 23–25 October 1995, pp. 170–181. IEEE Computer Society (1995)
[NR97]
Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. In: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, Miami Beach, Florida, USA, 19–22 October 1997, pp. 458–467. IEEE Computer Society (1997)
[NRR00]
Naor, M., Reingold, O., Rosen, A.: Pseudo-random functions and factoring (extended abstract). In: Yao, F.F., Luks, E.M. (eds.) Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, Portland, OR, USA, 21–23 May 2000, pp. 11–20. ACM (2000)
[OW14]
O’Donnell, R., Witmer, D., Goldreich’s, P.R.G.: Evidence for near-optimal polynomial stretch. In: IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11–13, 2014, pp. 1–12. IEEE (2014)
[PF79]
[PW88]
Pitt, L., Warmuth, M.K.: Reductions among prediction problems on the difficulty of predicting automata. In: Proceedings: Third Annual Structure in Complexity Theory Conference, Georgetown University, Washington, D.C., USA, 14–17 June 1988, pp. 60–69. IEEE Computer Society (1988)
[RR97]
[Tzu09]
Tzur, Y.: Notions of weak pseudorandomness and \({\rm GF}(2^n)\)-polynomials. Master’s thesis, Weizmann Institute of Science (2009)
[Val84]
Valiant, L.G.: A theory of the learnable. In: DeMillo, R.A. (ed.) Proceedings of the 16th Annual ACM Symposium on Theory of Computing, Washington, DC, USA, 30 April–2 May1984, pp. 436–445. ACM (1984)
[Weg87]
Wegener, I.: The Complexity of Boolean Functions. Teubner/Wiley, Stuttgart (1987)MATH
[Yao82]
Yao, A.C.: Theory and applications of trapdoor functions (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3–5 November 1982, pp. 80–91. IEEE Computer Society (1982)
Metadata
Title
Fast Pseudorandom Functions Based on Expander Graphs
Authors
Benny Applebaum
Pavel Raykov
Copyright Year
2016
Publisher
Springer Berlin Heidelberg
Book
Theory of Cryptography

Print ISBN: 978-3-662-53640-7

Electronic ISBN: 978-3-662-53641-4

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-662-53641-4_2

Premium Partner

    Image Credits