Paper 2023/1142
On the Efficiency of Generic, Quantum Cryptographic Constructions
, Technology Innovation InstituteAbstract
One of the central questions in cryptology is how efficient generic constructions of cryptographic primitives can be. Gennaro, Gertner, Katz, and Trevisan [SIAM J. Compt. 2005] studied the lower bounds of the number of invocations of a (trapdoor) oneway permutation in order to construct cryptographic schemes, e.g., pseudorandom number generators, digital signatures, and public-key and symmetric-key encryption. Recently quantum machines have been explored to _construct_ cryptographic primitives other than quantum key distribution. This paper studies the efficiency of _quantum_ black-box constructions of cryptographic primitives when the communications are _classical_. Following Gennaro et al., we give the lower bounds of the number of invocations of an underlying quantumly-computable quantum-oneway permutation (QC-qOWP) when the _quantum_ construction of pseudorandom number generator (PRG) and symmetric-key encryption (SKE) is weakly black-box. Our results show that the quantum black-box constructions of PRG and SKE do not improve the number of invocations of an underlying QC-qOWP.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Quantum constructionquantum reductionblack-box constructionefficiency
- Contact author(s)
- xagawa @ gmail com
- History
- 2023-07-27: approved
- 2023-07-24: received
- See all versions
- Short URL
- https://ia.cr/2023/1142
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1142,
author = {Keita Xagawa},
title = {On the Efficiency of Generic, Quantum Cryptographic Constructions},
howpublished = {Cryptology ePrint Archive, Paper 2023/1142},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/1142}},
url = {https://eprint.iacr.org/2023/1142}
}
