A Combinatorial Approach to Quantum Random Functions

Döttling, Nico and Malavolta, Giulio and Pu, Sihang
(2020) A Combinatorial Approach to Quantum Random Functions.
In: 26th International Conference on the Theory and Application of Cryptology and Information Security.
Conference: ASIACRYPT International Conference on the Theory and Application of Cryptology and Information Security

[img] Text
QRF.pdf

Download (396kB)

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.

Actions

Actions (login required)

View Item View Item