Top

Published in:

2018 | OriginalPaper | Chapter

Constrained PRFs for \(\mathrm{NC}^1\) in Traditional Groups

Authors : Nuttapong Attrapadung, Takahiro Matsuda, Ryo Nishimaki, Shota Yamada, Takashi Yamakawa

Published in: Advances in Cryptology – CRYPTO 2018

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

We propose new constrained pseudorandom functions (CPRFs) in traditional groups. Traditional groups mean cyclic and multiplicative groups of prime order that were widely used in the 1980s and 1990s (sometimes called “pairing free” groups). Our main constructions are as follows.

We propose a selectively single-key secure CPRF for circuits with depth \(O(\log n)\) (that is, NC\(^1\) circuits) in traditional groups where n is the input size. It is secure under the L-decisional Diffie-Hellman inversion (L-DDHI) assumption in the group of quadratic residues \(\mathbb {QR}_q\) and the decisional Diffie-Hellman (DDH) assumption in a traditional group of order q in the standard model.
We propose a selectively single-key private bit-fixing CPRF in traditional groups. It is secure under the DDH assumption in any prime-order cyclic group in the standard model.
We propose adaptively single-key secure CPRF for NC\(^1\) and private bit-fixing CPRF in the random oracle model.

To achieve the security in the standard model, we develop a new technique using correlated-input secure hash functions.

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 Yes, There is an Oblivious RAM Lower Bound!

next chapter GGH15 Beyond Permutation Branching Programs: Proofs, Attacks, and Candidates

We note that the role of the constraining function f is “reversed” from the definition by Boneh and Waters [16], in the sense that the evaluation by a constrained key \(\mathsf {sk}_f\) is possible for inputs x with \(f(x) = 1\) in their definition, while it is possible for inputs x for \(f(x) = 0\) in our paper. Our treatment is the same as Brakerski and Vaikuntanathan [15].

A constrained key in which a set of points is hard-wired enables us to compute an output if an input is not in the specified set.

There are left and right constrained keys in which \(v_\ell \) and \(v_r\) are hard-wired, respectively. We can compute outputs by using the left (resp. right) constrained key if the first (resp. last) half of an input is equal to \(v_\ell \) (resp. \(v_r\)).

This is the negation of bit-fixing functions, that is, \(f_c(x)=0\) if there exists an index i such that \(x_i \ne c_i\) (i-th bit of a constraint) and \(c_i \ne *\). It can be seen as a generalization of punctured predicates.

For example, cyclic group \(\mathbb {H}\subset \mathbb {Z}^{*}_q\) of a prime order p such that \(q=2p+1\) where q is also a prime.

In their sub-string match CPRFs, adversaries are not given access to the evaluation oracle, which gives outputs of a CPRF for queried inputs. We call such security no-evaluation security in this paper.

Adversaries commit a function to be embedded in a constrained key at the beginning of the security experiment and have access to the evaluation oracle, which gives outputs of CPRFs for queried inputs.

The L-DDHI assumption in a group \(\mathbb {H}\) of order p [4, 21] says that it is hard to distinguish \((g,g^{\alpha },g^{\alpha ^2},\ldots , g^{\alpha ^L},g^{1/\alpha })\) from \((g,g^{\alpha },g^{\alpha ^2},\ldots , g^{\alpha ^L},g^{z})\) where \(g\overset{\scriptscriptstyle \mathsf {R}}{\leftarrow }\mathbb {H},\alpha ,z \overset{\scriptscriptstyle \mathsf {R}}{\leftarrow }\mathbb {Z}_p\). See the full version [3] for the rigorous definition.

The DDH assumption in a group \(\mathbb {G}\) of order q says that it is hard to distinguish \((g,g^x,g^y,g^{xy})\) from \((g,g^x,g^y,g^z)\) where \(g\overset{\scriptscriptstyle \mathsf {R}}{\leftarrow }\mathbb {G}, x,y,z\overset{\scriptscriptstyle \mathsf {R}}{\leftarrow }\mathbb {Z}_q\).

Adversaries can decide a function for which it makes the key query at any time.

Here, we identify a circuit that computes a function f with f itself.

We can construct a universal circuit U whose depth is only constant times deeper than that of f by the result of Cook and Hoover [20]. It is well known that an \({\mathbf {NC}}^1\) circuit can be represented by a polynomial with polynomial degree (for example, this fact is used for functional encryption for \({\mathbf {NC}}^1\) [31]).

Several works defined similar notions in different names such as related-key security. We use the name “correlated-input security” since we think it is the most suitable name for our usage.

In the formal security definition, the function is parameterized by a public parameter generated by some setup procedure. We ignore the public parameter in the explanation below for simplicity. See Sect. 2.2 for the rigorous security definition for CIHs.

The definition of CIHs in this paper can be seen as a hybrid of correlated-input pseudorandom by Goyal et al. [30] and RKA-PRG by Bellare and Cash [5]. See Sect. 2.2 for the formal definition.

In this paper, a “class of functions” is a set of “sets of functions”. Each \(\mathcal {F}_{\lambda ,k}\) in \(\mathcal {F}\) considered for a CPRF is a set of functions parameterized by a security parameter \(\lambda \) and an input-length k.

For a class of functions \(\mathcal {F}\) considered for CIHs, we allow each member of \(\mathcal {F}\) to be parameterized by not only \(\lambda \in \mathbb {N}\) but also \(z \in \{0,1\}^*\). The role of z is to associate the functions with a public parameter \(\mathsf {pp}\) generated by \(\mathsf {Setup}(1^{\lambda })\). See the security experiment in Fig. 2.

If we fix an input of a PRF and view its key as a seed of a PRG, then the former can be seen as a latter.

Here, we intentionally use the symbol \(\mathbb {H}\) and \(\mathsf {HGen}\) instead of \(\mathbb {G}\) and \(\mathsf {GGen}\). Looking ahead, in Sect. 4.2, the latter symbols will be used to represent yet another group of order q and corresponding group generator. There, we should require \(\mathbb {H}\) to be \(\mathbb {QR}_q\).

According to the definition given in [3], we should give

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-96881-0_19/471489_1_En_19_IEq1067_HTML.gif

for all \(\lambda \in \mathbb {N}\) and \(n\in \mathbb {N}\). However, since

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-96881-0_19/471489_1_En_19_IEq1070_HTML.gif

is the same for all \(\lambda \) if n is fixed in the case of the bit-fixing, we use this simpler notation.

Abdalla, M., Benhamouda, F., Passelègue, A., Paterson, K.G.: Related-key security for pseudorandom functions beyond the linear barrier. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 77–94. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_5CrossRef

Abusalah, H., Fuchsbauer, G., Pietrzak, K.: Constrained PRFs for unbounded inputs. In: Sako, K. (ed.) CT-RSA 2016. LNCS, vol. 9610, pp. 413–428. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29485-8_24CrossRef

Attrapadung, N., Matsuda, T., Nishimaki, R., Yamada, S., Yamakawa, T.: Constrained PRFs for \( {NC}^1\) in traditional groups. IACR Cryptol. ePrint Arch. 2018, 154 (2018)

Boneh, D., Boyen, X.: Short signatures without random oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 56–73. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_4CrossRef

Bellare, M., Cash, D.: Pseudorandom functions and permutations provably secure against related-key attacks. IACR Cryptol. ePrint Arch., 397 (2010). Version 20150729:233210. Preliminary Version Appeared in CRYPTO 2010

Bellare, M., Cash, D.: Pseudorandom functions and permutations provably secure against related-key attacks. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 666–684. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_36CrossRef

Boneh, D., Franklin, M.K.: Identity-based encryption from the weil pairing. SIAM J. Comput. 32(3), 586–615 (2003)MathSciNetCrossRef

Banerjee, A., Fuchsbauer, G., Peikert, C., Pietrzak, K., Stevens, S.: Key-homomorphic constrained pseudorandom functions. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 31–60. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46497-7_2CrossRef

Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (im)possibility of obfuscating programs. J. ACM 59(2), 601–648 (2012)MathSciNetCrossRef

10.

Boyle, E., Goldwasser, S., Ivan, I.: Functional signatures and pseudorandom functions. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 501–519. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54631-0_29CrossRef

11.

Bitansky, N.: Verifiable random functions from non-interactive witness-indistinguishable proofs. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10678, pp. 567–594. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70503-3_19CrossRef

12.

Boneh, D., Kim, S., Montgomery, H.: Private puncturable PRFs from standard lattice assumptions. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part I. LNCS, vol. 10210, pp. 415–445. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_15CrossRef

13.

Boneh, D., Lewi, K., Wu, D.J.: Constraining pseudorandom functions privately. In: Fehr, S. (ed.) PKC 2017, Part II. LNCS, vol. 10175, pp. 494–524. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54388-7_17CrossRef

14.

Brakerski, Z., Tsabary, R., Vaikuntanathan, V., Wee, H.: Private constrained PRFs (and mode) from LWE. In: TCC 2017 (2017)CrossRef

15.

Brakerski, Z., Vaikuntanathan, V.: Constrained key-homomorphic PRFs from standard lattice assumptions. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 1–30. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46497-7_1CrossRef

16.

Boneh, D., Waters, B.: Constrained pseudorandom functions and their applications. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 280–300. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-42045-0_15CrossRef

17.

Boyle, E., Gilboa, N., Ishai, Y.: Breaking the circuit size barrier for secure computation under DDH. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 509–539. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_19CrossRef

18.

Canetti, R., Chen, Y.: Constraint-hiding constrained PRFs for NC¹ from LWE. In: EUROCRYPT 2017, Part I, pp. 446–476 (2017)

19.

Cohen, A., Goldwasser, S., Vaikuntanathan, V.: Aggregate pseudorandom functions and connections to learning. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 61–89. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46497-7_3CrossRef

20.

Cook, S.A., Hoover, H.J.: A depth-universal circuit. SIAM J. Comput. 14(4), 833–839 (1985)MathSciNetCrossRef

21.

Camenisch, J., Hohenberger, S., Lysyanskaya, A.: Compact E-Cash. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 302–321. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_18CrossRef

22.

Döttling, N., Garg, S.: Identity-based encryption from the diffie-hellman assumption. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part I. LNCS, vol. 10401, pp. 537–569. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_18CrossRef

23.

Deshpande, A., Koppula, V., Waters, B.: Constrained pseudorandom functions for unconstrained inputs. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part II. LNCS, vol. 9666, pp. 124–153. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_5CrossRef

24.

Fuchsbauer, G., Konstantinov, M., Pietrzak, K., Rao, V.: Adaptive security of constrained PRFs. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 82–101. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45608-8_5CrossRef

25.

Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_1CrossRef

26.

Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM J. Comput. 45(3), 882–929 (2016)MathSciNetCrossRef

27.

Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792–807 (1986)MathSciNetCrossRef

28.

Goyal, R., Hohenberger, S., Koppula, V., Waters, B.: A generic approach to constructing and proving verifiable random functions. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10678, pp. 537–566. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70503-3_18CrossRef

29.

Goldenberg, D., Liskov, M.: On related-secret pseudorandomness. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 255–272. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11799-2_16CrossRef

30.

Goyal, V., O’Neill, A., Rao, V.: Correlated-input secure hash functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 182–200. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19571-6_12CrossRef

31.

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). https://doi.org/10.1007/978-3-642-32009-5_11CrossRef

32.

Hofheinz, D., Kamath, A., Koppula, V., Waters, B.: Adaptively secure constrained pseudorandom functions. IACR Cryptol. ePrint Arch. 2014, 720 (2014)

33.

Hohenberger, S., Koppula, V., Waters, B.: Adaptively secure puncturable pseudorandom functions in the standard model. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015, Part I. LNCS, vol. 9452, pp. 79–102. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_4CrossRefMATH

34.

Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145–161. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_9CrossRef

35.

Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. ACMCCS 2013, 669–684 (2013)

36.

Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. J. ACM 51(2), 231–262 (2004)MathSciNetCrossRef

37.

Peikert, C., Shiehian, S.: Privately constraining and programming PRFs, the LWE way. In: Abdalla, M., Dahab, R. (eds.) PKC 2018. LNCS, vol. 10770, pp. 675–701. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76581-5_23CrossRef

38.

Yamada, S.: Asymptotically compact adaptively secure lattice IBEs and verifiable random functions via generalized partitioning techniques. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part III. LNCS, vol. 10403, pp. 161–193. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9_6CrossRef

39.

Zhandry, M.: How to avoid obfuscation using witness PRFs. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016, Part II. LNCS, vol. 9563, pp. 421–448. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49099-0_16CrossRef

Title: Constrained PRFs for in Traditional Groups
Authors: Nuttapong Attrapadung
Takahiro Matsuda
Ryo Nishimaki
Shota Yamada
Takashi Yamakawa
Publisher: Springer International Publishing
Book: Advances in Cryptology – CRYPTO 2018
Print ISBN: 978-3-319-96880-3

Electronic ISBN: 978-3-319-96881-0

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-96881-0_19

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner