{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T08:46:12Z","timestamp":1765961172776},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,9,4]],"date-time":"2019-09-04T00:00:00Z","timestamp":1567555200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,9,4]],"date-time":"2019-09-04T00:00:00Z","timestamp":1567555200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00145-019-09331-1","type":"journal-article","created":{"date-parts":[[2019,9,4]],"date-time":"2019-09-04T20:04:27Z","timestamp":1567627467000},"page":"459-493","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Verifiable Random Functions from Non-interactive Witness-Indistinguishable Proofs"],"prefix":"10.1007","volume":"33","author":[{"given":"Nir","family":"Bitansky","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,9,4]]},"reference":[{"issue":"3","key":"9331_CR1","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/s00145-013-9153-x","volume":"27","author":"M Abdalla","year":"2014","unstructured":"M. Abdalla, D. Catalano, D. Fiore, Verifiable random functions: relations to identity-based key encapsulation and new constructions. J. Cryptol.27(3), 544\u2013593 (2014)","journal-title":"J. Cryptol."},{"key":"9331_CR2","unstructured":"D. Boneh, X. Boyen, Secure identity based encryption without random oracles, in Advances in Cryptology - CRYPTO 2004, 24th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15\u201319, 2004, Proceedings (2004), pp. 443\u2013459"},{"issue":"2","key":"9331_CR3","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0020-0190(99)00047-2","volume":"70","author":"E Biham","year":"1999","unstructured":"E. Biham, D. Boneh, O. Reingold, Breaking generalized Diffie\u2013Hellmann modulo a composite is no easier than factoring. Inf. Process. Lett.70(2), 83\u201387 (1999)","journal-title":"Inf. Process. Lett."},{"key":"9331_CR4","doi-asserted-by":"crossref","unstructured":"E. Boyle, S. Goldwasser, I. Ivan, Functional signatures and pseudorandom functions, in H. Krawczyk, editor, PKC 2014: 17th International Conference on Theory and Practice of Public Key Cryptography, Volume 8383 of Lecture Notes in Computer Science, Buenos Aires, Argentina, March 26\u201328 (Springer, Heidelberg, 2014), pp. 501\u2013519","DOI":"10.1007\/978-3-642-54631-0_29"},{"key":"9331_CR5","unstructured":"S. Badrinarayanan, V. Goyal, A. Jain, A. Sahai, Verifiable functional encryption, in Advances in Cryptology\u2014ASIACRYPT 2016\u201422nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4\u20138, 2016, Proceedings, Part II (2016), pp. 557\u2013587"},{"key":"9331_CR6","unstructured":"S. Badrinarayanan, V. Goyal, A. Jain, A. Sahai, A note on VRFs from verifiable functional encryption, p. 051 (2017)"},{"key":"9331_CR7","unstructured":"Z. Brakerski, S. Goldwasser, G.N. Rothblum, V. Vaikuntanathan, Weak verifiable random functions, in 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, March 15\u201317, 2009. Proceedings (2009), pp. 558\u2013576"},{"key":"9331_CR8","unstructured":"M. Blum, Coin flipping by telephone, in Advances in Cryptology: A Report on CRYPTO 81, CRYPTO 81, IEEE Workshop on Communications Security, Santa Barbara, California, USA, August 24\u201326, 1981 (1981), pp. 11\u201315"},{"key":"9331_CR9","unstructured":"D. Boneh, H.W. Montgomery, A. Raghunathan, Algebraic pseudorandom functions with improved efficiency from the augmented cascade, in Proceedings of the 17th ACM Conference on Computer and Communications Security, CCS 2010, Chicago, Illinois, USA, October 4\u20138, 2010 (2010), pp. 131\u2013140"},{"issue":"2","key":"9331_CR10","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1137\/050641958","volume":"37","author":"B Barak","year":"2007","unstructured":"B. Barak, S.J. Ong, S.P. Vadhan, Derandomization in cryptography. SIAM J. Comput.37(2), 380\u2013400 (2007)","journal-title":"SIAM J. Comput."},{"key":"9331_CR11","unstructured":"N. Bitansky, O. Paneth, Zaps and non-interactive witness indistinguishability from indistinguishability obfuscation, in Theory of Cryptography\u201412th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23\u201325, 2015, Proceedings, Part II (2015), pp. 401\u2013427"},{"key":"9331_CR12","unstructured":"M. Bellare, T. Ristenpart, Simulation without the artificial abort: Simplified proof and improved concrete security for waters\u2019 IBE scheme, in Advances in Cryptology\u2014EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26\u201330, 2009. Proceedings (2009), pp. 407\u2013424"},{"issue":"6","key":"9331_CR13","doi-asserted-by":"publisher","first-page":"1084","DOI":"10.1137\/0220068","volume":"20","author":"M Blum","year":"1991","unstructured":"M. Blum, A. De Santis, S. Micali, G. Persiano, Noninteractive zero-knowledge. SIAM J. Comput.20(6), 1084\u20131118 (1991)","journal-title":"SIAM J. Comput."},{"key":"9331_CR14","unstructured":"Z. Brakerski, V. Vaikuntanathan, Constrained key-homomorphic PRFs from standard lattice assumptions\u2014or: how to secretly embed a circuit in your PRF, in Theory of Cryptography\u201412th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23\u201325, 2015, Proceedings, Part II (2015), pp. 1\u201330"},{"key":"9331_CR15","doi-asserted-by":"crossref","unstructured":"D. Boneh, B. Waters, Constrained pseudorandom functions and their applications, in K. Sako, P. Sarkar, editors, Advances in Cryptology\u2014ASIACRYPT 2013, Part II, Volume 8270 of Lecture Notes in Computer Science, Bengalore, India, December 1\u20135 (Springer, Heidelberg, 2013), pp. 280\u2013300","DOI":"10.1007\/978-3-642-42045-0_15"},{"issue":"3","key":"9331_CR16","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s001459900009","volume":"9","author":"M Bellare","year":"1996","unstructured":"M. Bellare, M. Yung, Certifying permutations: noninteractive zero-knowledge based on any trapdoor permutation. J. Cryptol.9(3), 149\u2013166 (1996)","journal-title":"J. Cryptol."},{"key":"9331_CR17","unstructured":"D. Boneh, M. Zhandry, Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation, in Advances in Cryptology\u2014CRYPTO 2014\u201434th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17\u201321, 2014, Proceedings, Part I (2014), pp. 480\u2013499"},{"key":"9331_CR18","unstructured":"J. Chen, S. Gorbunov, S. Micali, G. Vlachos, ALGORAND AGREEMENT: super fast and partition resilient byzantine agreement. IACR Cryptology ePrint Archive 2018:377 (2018)"},{"key":"9331_CR19","unstructured":"M. Chase, S. Meiklejohn, D\u00e9j\u00e0 Q: using dual systems to revisit q-type assumptions, in Advances in Cryptology\u2014EUROCRYPT 2014\u201433rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11\u201315, 2014. Proceedings (2014), pp. 622\u2013639"},{"key":"9331_CR20","unstructured":"N. Chandran, S. Raghuraman, D. Vinayagamurthy, Constrained pseudorandom functions: verifiable and delegatable. Cryptology ePrint Archive 2014:522"},{"issue":"2","key":"9331_CR21","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"L Carter","year":"1979","unstructured":"L. Carter, M.N. Wegman, Universal classes of hash functions. J. Comput. Syst. Sci.18(2), 143\u2013154 (1979)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"9331_CR22","doi-asserted-by":"publisher","first-page":"1513","DOI":"10.1137\/S0097539703426817","volume":"36","author":"C Dwork","year":"2007","unstructured":"C. Dwork, M. Naor, Zaps and their applications. SIAM J. Comput.36(6), 1513\u20131543 (2007)","journal-title":"SIAM J. Comput."},{"key":"9331_CR23","unstructured":"Y. Dodis, Efficient construction of (distributed) verifiable random functions, in Public Key Cryptography\u2014PKC 2003, 6th International Workshop on Theory and Practice in Public Key Cryptography, Miami, FL, USA, January 6\u20138, 2003, Proceedings (2003), pp. 1\u201317"},{"key":"9331_CR24","unstructured":"Y. Dodis, A. Yampolskiy, A verifiable random function with short proofs and keys, in Public Key Cryptography\u2014PKC 2005, 8th International Workshop on Theory and Practice in Public Key Cryptography, Les Diablerets, Switzerland, January 23\u201326, 2005, Proceedings (2005), pp. 416\u2013431"},{"issue":"1","key":"9331_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539792230010","volume":"29","author":"U Feige","year":"1999","unstructured":"U. Feige, D. Lapidot, A. Shamir, Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput.29(1), 1\u201328 (1999)","journal-title":"SIAM J. Comput."},{"key":"9331_CR26","unstructured":"D. Fiore, D. Schr\u00f6der, Uniqueness is a different story: impossibility of verifiable random functions from trapdoor permutations, in Theory of Cryptography\u20149th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19\u201321, 2012. Proceedings (2012), pp. 636\u2013653"},{"key":"9331_CR27","unstructured":"G. Fuchsbauer, Constrained verifiable random functions, in Security and Cryptography for Networks\u20149th International Conference, SCN 2014, Amalfi, Italy, September 3\u20135, 2014. Proceedings (2014), pp. 95\u2013114"},{"issue":"4","key":"9331_CR28","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O Goldreich","year":"1986","unstructured":"O. Goldreich, S. Goldwasser, S. Micali, How to construct random functions. J. ACM33(4), 792\u2013807 (1986)","journal-title":"J. ACM"},{"key":"9331_CR29","doi-asserted-by":"crossref","unstructured":"R. Goyal, S. Hohenberger, V. Koppula, B. Waters, A generic approach to constructing and proving verifiable random functions. Cryptology ePrint Archive 2017:21","DOI":"10.1007\/978-3-319-70503-3_18"},{"key":"9331_CR30","unstructured":"S. Goldwasser, R. Ostrovsky, Invariant signatures and non-interactive zero-knowledge proofs are equivalent (extended abstract), in Advances in Cryptology\u2014CRYPTO \u201992, 12th Annual International Cryptology Conference, Santa Barbara, California, USA, August 16\u201320, 1992, Proceedings (1992), pp. 228\u2013245"},{"issue":"3","key":"9331_CR31","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/2220357.2220358","volume":"59","author":"J Groth","year":"2012","unstructured":"J. Groth, R. Ostrovsky, A. Sahai, New techniques for noninteractive zero-knowledge. J. ACM59(3), 11 (2012)","journal-title":"J. ACM"},{"issue":"3","key":"9331_CR32","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1007\/s00145-012-9131-8","volume":"26","author":"O Goldreich","year":"2013","unstructured":"O. Goldreich, R.D. Rothblum, Enhancements of trapdoor permutations. J. Cryptol.26(3), 484\u2013512 (2013)","journal-title":"J. Cryptol."},{"key":"9331_CR33","unstructured":"S. Gorbunov, V. Vaikuntanathan, H. Wee, Functional encryption with bounded collusions via multi-party computation, in Advances in Cryptology\u2014CRYPTO 2012\u201432nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19\u201323, 2012. Proceedings (2012), pp. 162\u2013179"},{"key":"9331_CR34","unstructured":"D. Hofheinz, T. Jager, Verifiable random functions from standard assumptions, in Theory of Cryptography\u201413th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10\u201313, 2016, Proceedings, Part I (2016), pp. 336\u2013362"},{"key":"9331_CR35","unstructured":"S. Hohenberger, V. Koppula, B. Waters, Adaptively secure puncturable pseudorandom functions in the standard model, in Advances in Cryptology\u2014ASIACRYPT 2015\u201421st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29\u2013December 3, 2015, Proceedings, Part I (2015), pp. 79\u2013102"},{"key":"9331_CR36","unstructured":"S. Hohenberger, B. Waters, Constructing verifiable random functions with large input spaces, in Advances in Cryptology\u2014EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30\u2013June 3, 2010. Proceedings (2010), pp. 656\u2013672"},{"key":"9331_CR37","unstructured":"T. Jager, Verifiable random functions from weaker assumptions, in Theory of Cryptography\u201412th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23\u201325, 2015, Proceedings, Part II (2015), pp. 121\u2013143"},{"key":"9331_CR38","doi-asserted-by":"crossref","unstructured":"A. Kiayias, S. Papadopoulos, N. Triandopoulos, T. Zacharias, Delegatable pseudorandom functions and applications, in A.-R. Sadeghi, V.D. Gligor, M. Yung, editors, ACM CCS 13: 20th Conference on Computer and Communications Security, November 4\u20138 (ACM Press, Berlin, 2013), pp. 669\u2013684","DOI":"10.1145\/2508859.2516668"},{"key":"9331_CR39","unstructured":"A. Lysyanskaya, Unique signatures and verifiable random functions from the DH-DDH separation, in Advances in Cryptology\u2014CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18\u201322, 2002, Proceedings (2002), pp. 597\u2013612"},{"key":"9331_CR40","unstructured":"S. Micali, M.O. Rabin, S.P. Vadhan, Verifiable random functions, in 40th Annual Symposium on Foundations of Computer Science, FOCS \u201999, 17\u201318 October, 1999, New York, NY, USA (1999), pp. 120\u2013130"},{"key":"9331_CR41","unstructured":"P.B. Miltersen, N.V. Vinodchandran, Derandomizing Arthur\u2013Merlin games using hitting sets, in 40th Annual Symposium on Foundations of Computer Science, FOCS \u201999, 17\u201318 October, 1999, New York, NY, USA (1999), pp. 71\u201380"},{"issue":"2","key":"9331_CR42","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/BF00196774","volume":"4","author":"M Naor","year":"1991","unstructured":"M. Naor, Bit commitment using pseudorandomness. J. Cryptol.4(2), 151\u2013158 (1991)","journal-title":"J. Cryptol."},{"issue":"2","key":"9331_CR43","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1006\/jcss.1998.1618","volume":"58","author":"M Naor","year":"1999","unstructured":"M. Naor, O. Reingold, Synthesizers and their application to the parallel construction of pseudo-random functions. J. Comput. Syst. Sci.58(2), 336\u2013375 (1999)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9331_CR44","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1145\/972639.972643","volume":"51","author":"M Naor","year":"2004","unstructured":"M. Naor, O. Reingold, Number-theoretic constructions of efficient pseudo-random functions. J. ACM51(2), 231\u2013262 (2004)","journal-title":"J. ACM"},{"key":"9331_CR45","unstructured":"D. Papadopoulos, D. Wessels, S. Huque, M. Naor, J. Vcel\u00e1k, L. Reyzin, S. Goldberg, Can NSEC5 be practical for DNSSEC deployments? IACR Cryptology ePrint Archive 2017:99 (2017)"},{"key":"9331_CR46","unstructured":"A. Sahai, H. Seyalioglu, Worry-free encryption: functional encryption with public keys, in Proceedings of the 17th ACM Conference on Computer and Communications Security, CCS 2010, Chicago, Illinois, USA, October 4\u20138, 2010 (2010), pp. 463\u2013472"},{"key":"9331_CR47","doi-asserted-by":"crossref","unstructured":"A. Sahai, B. Waters, How to use indistinguishability obfuscation: deniable encryption, and more, in D.B. Shmoys, editor, 46th Annual ACM Symposium on Theory of Computing, May 31\u2013June 3 (ACM Press, New York, 2014), pp. 475\u2013484","DOI":"10.1145\/2591796.2591825"},{"key":"9331_CR48","unstructured":"B. Waters, Efficient identity-based encryption without random oracles, in Advances in Cryptology\u2014EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22\u201326, 2005, Proceedings (2005), pp. 114\u2013127"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-019-09331-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-019-09331-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-019-09331-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,2]],"date-time":"2020-09-02T23:05:45Z","timestamp":1599087945000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-019-09331-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,4]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["9331"],"URL":"https:\/\/doi.org\/10.1007\/s00145-019-09331-1","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,4]]},"assertion":[{"value":"30 October 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2019","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}