The (Im)Possibility on Constructing Verifiable Random Functions. (30th April 2021)

• Record Type: Journal Article
• Authors: Cao, Shujiao; Xue, Rui
• Is Part Of: Computer journal. Volume 65:Number 7(2022)
• Page Start: 1826
• Page End: 1845
• Publication Date: 2021-04-30
• Subjects: Verifiable Random Functions -- Indistinguishability Obfuscator -- Black-Box Reduction -- Two-Oracle Technique -- Query Complexity; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxab023
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: In this paper, we further explore the properties of the verifiable random functions in both a black-box and a non-black-box manner. The results are mainly following two parts: $\bullet $ Black-Box Barrier: It is set up for an impossibility result of black-box reduction from verifiable random functions to injective one-way functions and indistinguishability obfuscators, where the verifiable random functions are suggested to be domain-invariant (i.e. the support of the distribution of keys and the domain of the evaluation space are independent of the underlying building blocks). Our result illustrates how the non-domain-invariant constructions circumvent the black-box barriers for constructing verifiable random functions and sheds light on why it is so difficult to give a domain-invariant instantiation. $\bullet $ Non-Black-Box Construction: On the other hand, the verifiable unpredictable functions are constructed from a given primitive by a non-black-box technique called the hitting-set generator. To show it's a somewhat useful technique for constructing the verifiable unpredictable functions, we further derive a limitation of the black-box barrier by proving the barrier still holds between the given primitive and verifiable unpredictable functions. Our results not only analyse the properties of verifiable random functions theoretically, but also reveal the limitation of indistinguishability obfuscators in a black-box manner, and show the advantages by adopting non-black-box techniques.