International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 02 December 2020

Nico Döttling, Giulio Malavolta, Sihang Pu
ePrint Report ePrint Report
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.
Expand

Additional news items may be found on the IACR news page.