You are looking at a specific version 20201202:100715 of this paper. See the latest version.

Paper 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.

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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.