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