[{"doi":"10.1007/978-3-030-75248-4_3","title":"Verifiable Random Functions with Optimal Tightness","date_created":"2021-05-10T16:07:50Z","author":[{"first_name":"David","last_name":"Niehues","id":"36113","full_name":"Niehues, David"}],"date_updated":"2022-01-06T06:55:24Z","citation":{"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>","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>.","short":"D. Niehues, in: Public-Key Cryptography – PKC 2021, Cham, 2021.","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>","ieee":"D. Niehues, “Verifiable Random Functions with Optimal Tightness,” in <i>Public-Key Cryptography – PKC 2021</i>, 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>."},"place":"Cham","year":"2021","publication_identifier":{"isbn":["9783030752477","9783030752484"],"issn":["0302-9743","1611-3349"]},"has_accepted_license":"1","publication_status":"published","file_date_updated":"2021-05-10T16:09:17Z","language":[{"iso":"eng"}],"ddc":["000"],"department":[{"_id":"558"}],"user_id":"36113","_id":"22059","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Project Area C","_id":"4"},{"_id":"13","name":"SFB 901 - Subproject C1"}],"status":"public","file":[{"file_id":"22060","access_level":"closed","file_name":"Niehues - 2021 - Verifiable Random Functions with Optimal Tightness.pdf","file_size":697361,"creator":"davnie","date_created":"2021-05-10T16:09:17Z","date_updated":"2021-05-10T16:09:17Z","relation":"main_file","content_type":"application/pdf"}],"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","type":"book_chapter"}]