Search results for Quantum reduction

Loïs HugueninDumittan, Serge VaudenayPublished 20240409 Show abstract PDF
Proving whether it is possible to build INDCCA publickey encryption (PKE) from INDCPA PKE in a blackbox manner is a major open problem in theoretical cryptography. In a significant breakthrough, Gertner, Malkin and Myers showed in 2007 that shielding blackbox reductions from INDCCA to INDCPA do not exist in the standard model. Shielding means that the decryption algorithm of the INDCCA scheme does not call the encryption algorithm of the underlying INDCPA scheme. In other words, it implies that every tentative construction of INDCCA from INDCPA must have a reencryption step when decrypting.
This result was only proven with respect to classical algorithms. In this work we show that it stands in a postquantum setting. That is, we prove that there is no postquantum shielding blackbox construction of INDCCA PKE from INDCPA PKE. In the type of reductions we consider, i.e. postquantum ones, the constructions are still classical in the sense that the schemes must be computable on classical computers, but the adversaries and the reduction algorithm can be quantum. This suggests that considering quantum notions, which are stronger than their classical counterparts, and allowing for quantum reductions does not make building INDCCA publickey encryption easier.

Keita XagawaPublished 20240409 Show abstract PDF
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) oneway permutation in order to construct cryptographic schemes, e.g., pseudorandom number generators, digital signatures, and publickey and symmetrickey encryption.
Recently, quantum machines have been explored to _construct_ cryptographic primitives other than quantum key distribution. This paper studies the efficiency of _quantum_ blackbox 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 quantumlycomputable quantumoneway permutation when the _quantum_ construction of pseudorandom number generator and symmetrickey encryption is weakly blackbox. Our results show that the quantum blackbox constructions of pseudorandom number generator and symmetrickey encryption do not improve the number of invocations of an underlying quantumlycomputable quantumoneway permutation.