Paper 2018/1066
Finding Collisions in a Quantum World: Quantum Black-Box Separation of Collision-Resistance and One-Wayness
Akinori Hosoyamada and Takashi Yamakawa
Abstract
Since the celebrated work of Impagliazzo and Rudich (STOC 1989), a number of black-box impossibility results have been established. However, these works only ruled out classical black-box reductions among cryptographic primitives. Therefore it may be possible to overcome these impossibility results by using quantum reductions. To exclude such a possibility, we have to extend these impossibility results to the quantum setting. In this paper, we initiate the study of black-box impossibility in the quantum setting. We first formalize a quantum counterpart of fully-black-box reduction following the formalization by Reingold, Trevisan and Vadhan (TCC 2004). Then we prove that there is no quantum fully-black-box reduction from collision-resistant hash function to one-way permutation (or even trapdoor permutation). This is an extension to the quantum setting of the work of Simon (Eurocrypt 1998) who showed a similar result in the classical setting.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- post-quantum cryptographyone-way permutationone-way trapdoor permutationfully black-box reductionquantum reductionimpossibility
- Contact author(s)
- hosoyamada akinori @ lab ntt co jp
- History
- 2020-09-04: last of 4 revisions
- 2018-11-09: received
- See all versions
- Short URL
- https://ia.cr/2018/1066
- License
-
CC BY