Paper 2019/1335

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

Tibor Jager and David Niehues

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 show 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 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 present a new VRF scheme using cAHFs and show that it is currently the most efficient verifiable random function with full adaptive security in the standard model.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. Selected Areas in Cryptography 2019
Keywords
admissible hash functionsverifiable random functionserror- correcting codesprovable security.
Contact author(s)
david niehues @ uni-paderborn de
History
2019-11-21: revised
2019-11-20: received
See all versions
Short URL
https://ia.cr/2019/1335
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1335,
      author = {Tibor Jager and David Niehues},
      title = {On the Real-World Instantiability of Admissible Hash Functions and Efficient Verifiable Random Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/1335},
      year = {2019},
      url = {https://eprint.iacr.org/2019/1335}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.