Title | A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles |

Publication Type | Journal Article |

Year of Publication | 2024 |

Authors | Katz, J, Sela, B |

Date Published | 1/30/2024 |

Abstract | We study the (quantum) security of pseudorandom generators (PRGs) constructed from random oracles. We prove a "lifting theorem" showing, roughly, that if such a PRG is unconditionally secure against classical adversaries making polynomially many queries to the random oracle, then it is also (unconditionally) secure against quantum adversaries in the same sense. As a result of independent interest, we also show that any pseudo-deterministic quantum-oracle algorithm (i.e., a quantum algorithm that with high probability returns the same value on repeated executions) can be simulated by a computationally unbounded but query bounded classical-oracle algorithm with only a polynomial blowup in the number of queries. This implies as a corollary that our lifting theorem holds even for PRGs that themselves make quantum queries to the random oracle. |

URL | https://arxiv.org/abs/2401.14319 |