Quantum Fast Implementation of Private Information Retrieval and Functional Bootstrapping

Quantum computation has found greater efficiency and security across various fields. We show that, in a near-term hybrid cloud computing scenario with only one single quantum server and an entirely classical client, critical bottlenecks in privacy-preserving computation can be addressed. First, we propose an efficient quantum functional bootstrapping algorithm with a runtime polynomial in the plaintext-size, providing an exponential quantum speedup over classical algorithms. Second, we present a secure and fast quantum private information retrieval protocol with logarithmic query time. The security relies on the learning with errors (LWE) problem with polynomial modulus, greatly improving the security of classical fast PIR protocol based on ring-LWE with super-polynomial modulus. Technically, we extend an important classical homomorphic operation, known as blind rotation, to the quantum case by an encrypted conditional rotation technique. This technique holds promise for broader applications in quantum cryptography.