Top

Published in:

2019 | OriginalPaper | Chapter

Adaptively Single-Key Secure Constrained PRFs for \(\mathrm {NC}^1\)

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

Published in: Public-Key Cryptography – PKC 2019

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

We present a construction of an adaptively single-key secure constrained PRF (CPRF) for \(\mathbf {NC}^1\) assuming the existence of indistinguishability obfuscation (IO) and the subgroup hiding assumption over a (pairing-free) composite order group. This is the first construction of such a CPRF in the standard model without relying on a complexity leveraging argument.

To achieve this, we first introduce the notion of partitionable CPRF, which is a CPRF accommodated with partitioning techniques and combine it with shadow copy techniques often used in the dual system encryption methodology. We present a construction of partitionable CPRF for \(\mathbf {NC}^1\) based on IO and the subgroup hiding assumption over a (pairing-free) group. We finally prove that an adaptively single-key secure CPRF for \(\mathbf {NC}^1\) can be obtained from a partitionable CPRF for \(\mathbf {NC}^1\) and IO.

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 Function Private Predicate Encryption for Low Min-Entropy Predicates

next chapter Obfuscating Simple Functionalities from Knowledge Assumptions

It is also known as delegatable PRF [36] and functional PRF [12].

We note that the role of the constraining function f is “reversed” from the definition by Boneh and Waters [10], 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 [14].

A CPRF is called collusion-resistant if it remains secure even if adversaries are given polynomially many constrained keys.

In previous works, both selective-challenge and selective-constraint security are simply called selective security. We use different names for them for clarity.

More precisely, they also generalized their construction to obtain a CPRF for t-puncturing functions, which puncture the input space on t points for a polynomial t (rather than a single point).

Actually, we use an extended notion called a balanced admissible hash function (Sect. 2.2).

It assumes that

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-17259-6_8/483035_1_En_8_IEq92_HTML.gif

holds, where

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-17259-6_8/483035_1_En_8_IEq93_HTML.gif

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-17259-6_8/483035_1_En_8_IEq94_HTML.gif

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-17259-6_8/483035_1_En_8_IEq95_HTML.gif

, and

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-17259-6_8/483035_1_En_8_IEq96_HTML.gif

are groups of order N, p, and q, respectively, g, \(g_1\), and \(g_2\) are generators of

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-17259-6_8/483035_1_En_8_IEq99_HTML.gif

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-17259-6_8/483035_1_En_8_IEq100_HTML.gif

, and

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-17259-6_8/483035_1_En_8_IEq101_HTML.gif

, respectively, and

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-17259-6_8/483035_1_En_8_IEq102_HTML.gif

Note that being given both

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-17259-6_8/483035_1_En_8_IEq161_HTML.gif

and

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-17259-6_8/483035_1_En_8_IEq162_HTML.gif

does not lead to a trivial attack since we use “pairing-free” groups.

We note that even if the underlying partitionable CPRF only supports \(\mathbf {NC}^1\), we can naturally define a constrained key for a function outside \(\mathbf {NC}^1\) in the CPRF given in Sect. 4 because a function class supported by the partitionable CPRF matters only in the security proof and does not matter for the correctness.

The L-DDH assumption was called Assumption 2 by Hohenberger et al. [33].

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 clarity, we will define a CPRF as a primitive that has a public parameter. However, this treatment is compatible with the standard syntax in which there is no public parameter, because it can always be contained as part of a master secret key and constrained secret keys.

Selective-constraint no-evaluation security was simply called no-evaluation security in [2].

Though it is possible to define the adaptive security for PCPRFs in the similar way, we only define the selective-constraint no-evaluation security since we only need it.

The construction will be partition-hiding with respect to h. Looking ahead, we will show that PCPRF that is partition-hiding with respect to a balanced AHF is adaptively single-key secure in Sect. 4. There, we will set h to be a balanced AHF. However, in this section, h can be any efficiently computable function.

This can be done by sampling in \(\mathbb {Z}_N\); if it is not in \(\mathbb {Z}_N^*\), sampling again until it is. This will succeed with an overwhelming probability since N is a composite with two large prime factors.

If one relies on the technique of “exponential number of hybrids” (e.g., [18]), then we can prove the indistinguishability of these two cases without relying on subgroup hiding. However, the technique requires sub-exponentially secure \(\mathsf {iO}\), which we want to avoid.

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 \(\rm NC^1\) in traditional groups. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part II. LNCS, vol. 10992, pp. 543–574. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_19CrossRefMATH

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), 6:1–6:48 (2012)MathSciNetCrossRef

Bellare, M., Ristenpart, T.: Simulation without the artificial abort: simplified proof and improved concrete security for Waters’ IBE scheme. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 407–424. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01001-9_24CrossRef

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

Boneh, D., Boyen, X.: Secure identity based encryption without random oracles. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 443–459. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28628-8_27CrossRef

Boneh, D., Kim, S., Montgomery, H.W.: 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

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

10.

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

11.

Boneh, D., Zhandry, M.: Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 480–499. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_27CrossRef

12.

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

13.

Brakerski, Z., Tsabary, R., Vaikuntanathan, V., Wee, H.: Private constrained PRFs (and More) from LWE. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part I. LNCS, vol. 10677, pp. 264–302. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_10CrossRef

14.

Brakerski, Z., Vaikuntanathan, V.: Constrained key-homomorphic PRFs from standard lattice assumptions - or: how to secretly embed a circuit in your PRF. 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

15.

Canetti, R., Chen, Y.: Constraint-hiding constrained PRFs for NC1 from LWE. Cryptology ePrint Archive, Report 2017/143 (2017)

16.

Canetti, R., Chen, Y.: Constraint-hiding constrained PRFs for NC\(^1\) from LWE. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part I. LNCS, vol. 10210, pp. 446–476. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_16CrossRef

17.

Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM 51(4), 557–594 (2004)MathSciNetCrossRef

18.

Canetti, R., Lin, H., Tessaro, S., Vaikuntanathan, V.: Obfuscation of probabilistic circuits and applications. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 468–497. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46497-7_19CrossRefMATH

19.

Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai trees, or how to delegate a lattice basis. J. Cryptol. 25(4), 601–639 (2012)MathSciNetCrossRef

20.

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

21.

Datta, P., Dutta, R., Mukhopadhyay, S.: Constrained pseudorandom functions for unconstrained inputs revisited: achieving verifiability and key delegation. In: Fehr, S. (ed.) PKC 2017, Part II. LNCS, vol. 10175, pp. 463–493. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54388-7_16CrossRef

22.

Davidson, A., Katsumata, S., Nishimaki, R., Yamada, S.: Constrained PRFs for bit-fixing from OWFs with constant collusion resistance, IACR Cryptology ePrint Archive 2018/982 (2018)

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.

Freeman, D.M.: Converting pairing-based cryptosystems from composite-order groups to prime-order groups. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 44–61. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_3CrossRef

25.

Freire, E.S.V., Hofheinz, D., Paterson, K.G., Striecks, C.: Programmable hash functions in the multilinear setting. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 513–530. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_28CrossRefMATH

26.

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

27.

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

28.

Goldreich, O.: Computational Complexity - A Conceptual Perspective. Cambridge University Press, Cambridge (2008)CrossRef

29.

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

30.

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, Part II. LNCS, vol. 10678, pp. 537–566. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70503-3_18CrossRef

31.

Herold, G., Hesse, J., Hofheinz, D., Ràfols, C., Rupp, A.: Polynomial spaces: a new framework for composite-to-prime-order transformations. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 261–279. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_15CrossRef

32.

Hofheinz, D., Kamath, A., Koppula, V., Waters, B.: Adaptively secure constrained pseudorandom functions. In: FC 2019 (2019, to appear)

33.

Hohenberger, S., Koppula, V., Waters, B.: Adaptively secure puncturable pseudorandom functions in the standard model. Cryptology ePrint Archive, Report 2014/521 (2014)

34.

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

35.

Jager, T.: Verifiable random functions from weaker assumptions. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 121–143. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46497-7_5CrossRef

36.

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

37.

Lewko, A.: Tools for simulating features of composite order bilinear groups in the prime order setting. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 318–335. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_20CrossRefMATH

38.

Lysyanskaya, A.: Unique signatures and verifiable random functions from the DH-DDH separation. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 597–612. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_38CrossRef

39.

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

40.

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

41.

Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: 46th ACM STOC, pp. 475–484 (2014)

42.

Seo, J.H., Cheon, J.H.: Beyond the limitation of prime-order bilinear groups, and round optimal blind signatures. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 133–150. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28914-9_8CrossRefMATH

43.

Sipser, M., Spielman, D.A.: Expander codes. IEEE Trans. Inf. Theor. 42(6), 1710–1722 (1996)MathSciNetCrossRef

44.

Waters, B.: Efficient identity-based encryption without random oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_7CrossRef

45.

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

46.

Zémor, G.: On expander codes. IEEE Trans. Inf. Theor. 47(2), 835–837 (2001)MathSciNetCrossRef

Title: Adaptively Single-Key Secure Constrained PRFs for
Authors: Nuttapong Attrapadung
Takahiro Matsuda
Ryo Nishimaki
Shota Yamada
Takashi Yamakawa
Publisher: Springer International Publishing
Book: Public-Key Cryptography – PKC 2019
Print ISBN: 978-3-030-17258-9

Electronic ISBN: 978-3-030-17259-6

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-17259-6_8

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