[{"publication_status":"published","date_updated":"2022-01-06T06:55:24Z","publication_identifier":{"isbn":["9783030752477","9783030752484"],"issn":["0302-9743","1611-3349"]},"author":[{"full_name":"Niehues, David","first_name":"David","last_name":"Niehues","id":"36113"}],"year":"2021","title":"Verifiable Random Functions with Optimal Tightness","doi":"10.1007/978-3-030-75248-4_3","language":[{"iso":"eng"}],"abstract":[{"text":"Verifiable random functions (VRFs), introduced by Micali,\r\nRabin and Vadhan (FOCS’99), are the public-key equivalent of pseudo-\r\nrandom functions. A public verification key and proofs accompanying the\r\noutput enable all parties to verify the correctness of the output. How-\r\never, all known standard model VRFs have a reduction loss that is much\r\nworse than what one would expect from known optimal constructions of\r\nclosely related primitives like unique signatures. We show that:\r\n1. Every security proof for a VRF that relies on a non-interactive\r\nassumption has to lose a factor of Q, where Q is the number of adver-\r\nsarial queries. To that end, we extend the meta-reduction technique\r\nof Bader et al. (EUROCRYPT’16) to also cover VRFs.\r\n2. This raises the question: Is this bound optimal? We answer this ques-\r\ntion in the affirmative by presenting the first VRF with a reduction\r\nfrom the non-interactive qDBDHI assumption to the security of VRF\r\nthat achieves this optimal loss.\r\nWe thus paint a complete picture of the achievability of tight verifiable\r\nrandom functions: We show that a security loss of Q is unavoidable and\r\npresent the first construction that achieves this bound.","lang":"eng"}],"publication":"Public-Key Cryptography – PKC 2021","department":[{"_id":"558"}],"type":"book_chapter","date_created":"2021-05-10T16:07:50Z","file":[{"creator":"davnie","date_created":"2021-05-10T16:09:17Z","date_updated":"2021-05-10T16:09:17Z","relation":"main_file","access_level":"closed","file_size":697361,"file_name":"Niehues - 2021 - Verifiable Random Functions with Optimal Tightness.pdf","content_type":"application/pdf","file_id":"22060"}],"has_accepted_license":"1","status":"public","user_id":"36113","ddc":["000"],"_id":"22059","project":[{"name":"SFB 901","_id":"1"},{"_id":"4","name":"SFB 901 - Project Area C"},{"name":"SFB 901 - Subproject C1","_id":"13"}],"citation":{"ieee":"D. Niehues, “Verifiable Random Functions with Optimal Tightness,” in <i>Public-Key Cryptography – PKC 2021</i>, Cham, 2021.","apa":"Niehues, D. (2021). Verifiable Random Functions with Optimal Tightness. In <i>Public-Key Cryptography – PKC 2021</i>. Cham. <a href=\"https://doi.org/10.1007/978-3-030-75248-4_3\">https://doi.org/10.1007/978-3-030-75248-4_3</a>","short":"D. Niehues, in: Public-Key Cryptography – PKC 2021, Cham, 2021.","chicago":"Niehues, David. “Verifiable Random Functions with Optimal Tightness.” In <i>Public-Key Cryptography – PKC 2021</i>. Cham, 2021. <a href=\"https://doi.org/10.1007/978-3-030-75248-4_3\">https://doi.org/10.1007/978-3-030-75248-4_3</a>.","mla":"Niehues, David. “Verifiable Random Functions with Optimal Tightness.” <i>Public-Key Cryptography – PKC 2021</i>, 2021, doi:<a href=\"https://doi.org/10.1007/978-3-030-75248-4_3\">10.1007/978-3-030-75248-4_3</a>.","bibtex":"@inbook{Niehues_2021, place={Cham}, title={Verifiable Random Functions with Optimal Tightness}, DOI={<a href=\"https://doi.org/10.1007/978-3-030-75248-4_3\">10.1007/978-3-030-75248-4_3</a>}, booktitle={Public-Key Cryptography – PKC 2021}, author={Niehues, David}, year={2021} }","ama":"Niehues D. Verifiable Random Functions with Optimal Tightness. In: <i>Public-Key Cryptography – PKC 2021</i>. Cham; 2021. doi:<a href=\"https://doi.org/10.1007/978-3-030-75248-4_3\">10.1007/978-3-030-75248-4_3</a>"},"file_date_updated":"2021-05-10T16:09:17Z","place":"Cham"}]