Paper 2020/1508
A Combinatorial Approach to Quantum Random Functions
Nico Döttling, 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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2020
- Keywords
- Quantum Random FunctionPseudorandom Function
- Contact author(s)
- sihang pu @ email com
- History
- 2020-12-02: received
- Short URL
- https://ia.cr/2020/1508
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1508,
author = {Nico Döttling and Giulio Malavolta and Sihang Pu},
title = {A Combinatorial Approach to Quantum Random Functions},
howpublished = {Cryptology ePrint Archive, Paper 2020/1508},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1508}},
url = {https://eprint.iacr.org/2020/1508}
}
