CryptoDB
A Combinatorial Approach to Quantum Random Functions
| Authors: | |
|---|---|
| Download: | |
| Presentation: | Slides |
| Abstract: | Quantum pseudorandom functions (QPRFs) extend the classical security of a PRF by allowing the adversary to issue queries on input superpositions. 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. |
Video from ASIACRYPT 2020
BibTeX
@article{asiacrypt-2020-30694,
title={A Combinatorial Approach to Quantum Random Functions},
booktitle={Advances in Cryptology - ASIACRYPT 2020},
publisher={Springer},
doi={10.1007/978-3-030-64834-3_21},
author={Nico Döttling and Giulio Malavolta and Sihang Pu},
year=2020
}