(2020) A Combinatorial Approach to Quantum Random Functions.
|
Text
QRF.pdf Download (396kB) | Preview |
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.
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Nico Döttling (Cryptographic Algorithms, CA) |
| Conference: | ASIACRYPT International Conference on the Theory and Application of Cryptology and Information Security |
| Depositing User: | Nico Döttling |
| Date Deposited: | 04 Feb 2021 09:06 |
| Last Modified: | 11 May 2021 17:20 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3353 |
Actions
Actions (login required)
 |
View Item |