On the Efficiency of Generic, Quantum Cryptographic Constructions

One of the central questions in cryptology is how efficient generic constructions of cryptographic primitives can be. Gennaro, Gertner, Katz, and Trevisan SIAM J. of Compt. , 2005 studied the lower bounds of the number of invocations of a (trapdoor) one-way 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-one-way permutation when the quantum_ construction of pseudorandom number generator and symmetric-key encryption is weakly black-box. Our results show that the quantum black-box constructions of pseudorandom number generator and symmetric-key encryption do not improve the number of invocations of an underlying quantumly-computable quantum-one-way permutation.