Cryptology ePrint Archive: Report 2020/1508
A Combinatorial Approach to Quantum Random Functions
Nico Döttling and Giulio Malavolta and Sihang Pu
Abstract: Quantum pseudorandom functions (QPRFs) extend the classical security of a PRF by allowing the adversary to issue queries on input superposition. Zhandry [Zhandry, FOCS 2012] showed a separation between the two notions and proved that common construction paradigms are also quantum secure, albeit with a new ad-hoc analysis. In this work, we revisit the question of constructing QPRFs and propose a new method starting from small-domain (classical) PRFs: At the
heart of our approach is a new domain-extension technique based on bipartite expanders. Interestingly, our analysis is almost entirely classical. As a corollary of our main theorem, we obtain the first (approximate) key homomorphic quantum PRF based on the quantum intractability of the learning with errors problem.
Category / Keywords: foundations / Quantum Random Function, Pseudorandom Function
Original Publication (with minor differences): IACR-ASIACRYPT-2020
Date: received 1 Dec 2020
Contact author: sihang pu at email com
Available format(s): PDF | BibTeX Citation
Version: 20201202:100715 (All versions of this report)
Short URL: ia.cr/2020/1508
[ Cryptology ePrint archive ]