×

Distributed pseudorandom functions for general access structures in NP. (English) Zbl 1452.94058

Qing, Sihan (ed.) et al., Information and communications security. 19th international conference, ICICS 2017, Beijing, China, December 6–8, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10631, 81-87 (2018).
Summary: Distributed pseudorandom functions (DPRFs) originally introduced by Naor, Pinkas and Reingold [M. Naor et al., Eurocrypt 1999, Lect. Notes Comput. Sci. 1592, 327–346 (1999; Zbl 0931.94046)] are pseudorandom functions (PRFs), whose computation is distributed to multiple servers. Although by distributing the function computation, we avoid single points of failures, this distribution usually implies the need for multiple interactions with the parties (servers) involved in the computation of the function. In this paper, we take distributed pseudorandom functions (DPRFs) even further, by pursuing a very natural direction. We ask if it is possible to construct distributed PRFs for a general class of access mechanism going beyond the threshold access structure and the access structure that can be described by a polynomial-size monotone span programs. More precisely, our contributions are two-fold and can be summarised as follows: (i) we introduce the notion of single round distributed PRFs for a general class of access structure (monotone functions in NP), (ii) we provide a provably secure general construction of distributed PRFs for every mNP access structure from puncturable PRFs based on indistinguishable obfuscation.
For the entire collection see [Zbl 1435.68039].

MSC:

94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
94A62 Authentication, digital signatures and secret sharing

Citations:

Zbl 0931.94046
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boneh, D., Lewi, K., Montgomery, H., Raghunathan, A.: Key homomorphic PRFs and their applications. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 410-428. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_23 · Zbl 1310.94129 · doi:10.1007/978-3-642-40041-4_23
[2] De Santis, A., Desmedt, Y., Frankel, Y., Yung, M.: How to share a function securely. In: Proceedings of STOC 1994, pp. 522-533. ACM, New York (1994) · Zbl 1345.94094
[3] Desmedt, Y., Frankel, Y.: Threshold cryptosystems. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 307-315. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_28 · doi:10.1007/0-387-34805-0_28
[4] Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: Proceedings of FOCS 2013, Washington, D.C., USA, pp. 40-49. IEEE Computer Society (2013) · Zbl 1348.94048
[5] Grigni, M., Sipser, M.: Monotone complexity (1990) · Zbl 0766.68040
[6] Komargodski, I., Naor, M., Yogev, E.: Secret-sharing for NP. J. Cryptol. 30(2), 444-469 (2017) · Zbl 1377.94057 · doi:10.1007/s00145-015-9226-0
[7] Naor, M., Pinkas, B., Reingold, O.: Distributed pseudo-random functions and KDCs. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 327-346. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_23 · Zbl 0931.94046 · doi:10.1007/3-540-48910-X_23
[8] Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. J. ACM (JACM) 51(2), 231-262 (2004) · Zbl 1248.94086 · doi:10.1145/972639.972643
[9] Nielsen, J. · doi:10.1007/3-540-45708-9_26
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.