### Finding Collisions in a Quantum World: Quantum Black-Box Separation of Collision-Resistance and One-Wayness

##### 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 study 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 functions to one-way permutations (or even trapdoor permutations). We take both of classical and quantum implementations of primitives into account. This is an extension to the quantum setting of the work of Simon (Eurocrypt 1998) who showed a similar result in the classical setting.

Note: Minor changes.

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in ASIACRYPT 2020
Keywords
post-quantum cryptographyone-way permutationone-way trapdoor permutationfully black-box reductionquantum reductionimpossibility
Contact author(s)
akinori hosoyamada bh @ hco ntt co jp
History
2020-09-04: last of 4 revisions
See all versions
Short URL
https://ia.cr/2018/1066

CC BY

BibTeX

@misc{cryptoeprint:2018/1066,
author = {Akinori Hosoyamada and Takashi Yamakawa},
title = {Finding Collisions in a Quantum World: Quantum Black-Box Separation of Collision-Resistance and One-Wayness},
howpublished = {Cryptology ePrint Archive, Paper 2018/1066},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/1066}},
url = {https://eprint.iacr.org/2018/1066}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.