CISPA
Browse
cispa_all_3353.pdf (386.74 kB)

A Combinatorial Approach to Quantum Random Functions

Download (386.74 kB)
conference contribution
posted on 2023-11-29, 18:14 authored by Nico DöttlingNico Döttling, Giulio Malavolta, Sihang PuSihang Pu
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.

History

Preferred Citation

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

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT)

Legacy Posted Date

2021-02-04

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_3353, title = "A Combinatorial Approach to Quantum Random Functions", author = "Döttling, Nico and Malavolta, Giulio and Pu, Sihang", booktitle="{International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT)}", year="2020", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC