On the Real-World Instantiability of Admissible Hash Functions and Efficient Verifiable Random Functions

T. Jager, D. Niehues, in: Lecture Notes in Computer Science, Cham, 2020.

Download
Restricted Jager und Niehues - 2020 - On the Real-World Instantiability of Admissible Ha.pdf 706.74 KB
Book Chapter | Published | English
Author
Jager, Tibor; Niehues, DavidLibreCat
Abstract
Verifiable random functions (VRFs) are essentially digital signatures with additional properties, namely verifiable uniqueness and pseudorandomness, which make VRFs a useful tool, e.g., to prevent enumeration in DNSSEC Authenticated Denial of Existence and the CONIKS key management system, or in the random committee selection of the Algorand blockchain. Most standard-model VRFs rely on admissible hash functions (AHFs) to achieve security against adaptive attacks in the standard model. Known AHF constructions are based on error-correcting codes, which yield asymptotically efficient constructions. However, previous works do not clarify how the code should be instantiated concretely in the real world. The rate and the minimal distance of the selected code have significant impact on the efficiency of the resulting cryptosystem, therefore it is unclear if and how the aforementioned constructions can be used in practice. First, we explain inherent limitations of code-based AHFs. Concretely, we assume that even if we were given codes that achieve the well-known Gilbert-Varshamov or McEliece-Rodemich-Rumsey-Welch bounds, existing AHF-based constructions of verifiable random functions (VRFs) can only be instantiated quite inefficiently. Then we introduce and construct computational AHFs (cAHFs). While classical AHFs are information-theoretic, and therefore work even in presence of computationally unbounded adversaries, cAHFs provide only security against computationally bounded adversaries. However, we show that cAHFs can be instantiated significantly more efficiently. Finally, we use our cAHF to construct the currently most efficient verifiable random function with full adaptive security in the standard model.
Publishing Year
Book Title
Lecture Notes in Computer Science
Conference
Selected Areas in Cryptography
Conference Location
Waterloo, Canada
Conference Date
2019-08-12 – 2019-08-16
LibreCat-ID

Cite this

Jager T, Niehues D. On the Real-World Instantiability of Admissible Hash Functions and Efficient Verifiable Random Functions. In: Lecture Notes in Computer Science. Cham; 2020. doi:10.1007/978-3-030-38471-5_13
Jager, T., & Niehues, D. (2020). On the Real-World Instantiability of Admissible Hash Functions and Efficient Verifiable Random Functions. In Lecture Notes in Computer Science. Cham. https://doi.org/10.1007/978-3-030-38471-5_13
@inbook{Jager_Niehues_2020, place={Cham}, title={On the Real-World Instantiability of Admissible Hash Functions and Efficient Verifiable Random Functions}, DOI={10.1007/978-3-030-38471-5_13}, booktitle={Lecture Notes in Computer Science}, author={Jager, Tibor and Niehues, David}, year={2020} }
Jager, Tibor, and David Niehues. “On the Real-World Instantiability of Admissible Hash Functions and Efficient Verifiable Random Functions.” In Lecture Notes in Computer Science. Cham, 2020. https://doi.org/10.1007/978-3-030-38471-5_13.
T. Jager and D. Niehues, “On the Real-World Instantiability of Admissible Hash Functions and Efficient Verifiable Random Functions,” in Lecture Notes in Computer Science, Cham, 2020.
Jager, Tibor, and David Niehues. “On the Real-World Instantiability of Admissible Hash Functions and Efficient Verifiable Random Functions.” Lecture Notes in Computer Science, 2020, doi:10.1007/978-3-030-38471-5_13.
Main File(s)
File Name
Jager und Niehues - 2020 - On the Real-World Instantiability of Admissible Ha.pdf 706.74 KB
Access Level
Restricted Closed Access
Last Uploaded
2021-03-08T17:02:37Z


Link(s) to Main File(s)
Access Level
Restricted Closed Access
External material:
Later Version

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar
ISBN Search