期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-61
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In function inversion, we are given a function 𝑓 : [𝑁] ↦→ [𝑁], and want to prepare some advice of size 𝑆, such that we can efficiently invert any image in time 𝑇. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower bounds. Investigation of this problem in the quantum setting was initiated by Nayebi, Aaronson, Belovs, and Trevisan (2015), who proved a lower bound of 𝑆𝑇2 = Ω( ̃ 𝑁) for random permutations against classical advice, leaving open an intriguing possibility that Grover’s search can be sped up to time 𝑂̃( √︀ 𝑁/𝑆). Recent works by Hhan, Xagawa, and Yamakawa (2019), and Chung, Liao, and Qian (2019) extended the argument for random functions and quantum advice, but the lower bound remains 𝑆𝑇2 = Ω( ̃ 𝑁). In this work, we prove that even with quantum advice, 𝑆𝑇 𝑇 2 = Ω( ̃ 𝑁) is required for an algorithm to invert random functions. This demonstrates that Grover’s search is optimal for 𝑆 = 𝑂̃( √ 𝑁), ruling out any substantial speed-up for Grover’s search even with quantum advice. Further improvements to our bounds would imply a breakthrough in circuit lower bounds, as shown by Corrigan-Gibbs and Kogan (2019). To prove this result, we develop a general framework for establishing quantum time-space lower bounds. We further demonstrate the power of our framework by proving the following results. ∙ Yao’s box problem: We prove a tight quantum time-space lower bound for classical advice. For quantum advice, we prove a first time-space lower bound using shadow tomography. These results resolve two open problems posted by Nayebi, Aaronson, Belovs, and Trevisan (2015). ∙ Salted cryptography: We show that “salting generically provably defeats preprocessing,” a result shown by Coretti, Dodis, Guo, and Steinberger (2018), also holds in the quantum setting. In particular, we prove quantum time-space lower bounds for a wide class of salted cryptographic primitives in the quantum random oracle model. This yields the first quantum time-space lower bound for salted collision-finding, which in turn implies that 𝖯𝖶𝖯𝖯𝒪 ̸⊆ 𝖥𝖡𝖰𝖯𝒪/𝗊𝗉𝗈𝗅𝗒 relative to a random oracle 𝒪.
