Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / post-quantum cryptography, one-way permutation, one-way trapdoor permutation, fully black-box reduction, quantum reduction, impossibility

Date: received 2 Nov 2018

Contact author: hosoyamada akinori at lab ntt co jp

Available format(s): PDF | BibTeX Citation

Version: 20181109:162535 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]