---
_id: '21396'
abstract:
- lang: eng
text: "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.\r\n\r\nMost 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.\r\n\r\nFirst, 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."
author:
- first_name: Tibor
full_name: Jager, Tibor
last_name: Jager
- first_name: David
full_name: Niehues, David
id: '36113'
last_name: Niehues
citation:
ama: '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'
apa: 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
bibtex: '@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} }'
chicago: 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.
ieee: 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.
mla: 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.
short: 'T. Jager, D. Niehues, in: Lecture Notes in Computer Science, Cham, 2020.'
conference:
end_date: 2019-08-16
location: Waterloo, Canada
name: Selected Areas in Cryptography
start_date: 2019-08-12
date_created: 2021-03-08T16:50:31Z
date_updated: 2022-01-06T06:54:58Z
ddc:
- '000'
department:
- _id: '558'
doi: 10.1007/978-3-030-38471-5_13
file:
- access_level: closed
content_type: application/pdf
creator: davnie
date_created: 2021-03-08T17:02:37Z
date_updated: 2021-03-08T17:02:37Z
file_id: '21399'
file_name: Jager und Niehues - 2020 - On the Real-World Instantiability of Admissible
Ha.pdf
file_size: 706743
relation: main_file
file_date_updated: 2021-03-08T17:02:37Z
has_accepted_license: '1'
keyword:
- Admissible hash functions
- Verifiable random functions
- Error-correcting codes
- Provable security
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/content/pdf/10.1007%252F978-3-030-38471-5_13.pdf
place: Cham
project:
- _id: '1'
name: SFB 901
- _id: '4'
name: SFB 901 - Project Area C
- _id: '13'
name: SFB 901 - Subproject C1
publication: Lecture Notes in Computer Science
publication_identifier:
isbn:
- '9783030384708'
- '9783030384715'
issn:
- 0302-9743
- 1611-3349
publication_status: published
quality_controlled: '1'
related_material:
link:
- relation: later_version
url: https://eprint.iacr.org/2019/1335.pdf
status: public
title: On the Real-World Instantiability of Admissible Hash Functions and Efficient
Verifiable Random Functions
type: book_chapter
user_id: '36113'
year: '2020'
...