Quantum Fast Implementation of Functional Bootstrapping and Private Information Retrieval
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909370206388224 |
|---|---|
| author | Ma, Guangsheng Li, Hongbo |
| author_facet | Ma, Guangsheng Li, Hongbo |
| contents | Classical privacy-preserving computation techniques safeguard sensitive data in cloud computing, but often suffer from low computational efficiency. In this paper, we show that employing a single quantum server can significantly enhance both the efficiency and security of privacy-preserving computation.
We propose an efficient quantum algorithm for functional bootstrapping of large-precision plaintexts, reducing the time complexity from exponential to polynomial in plaintext-size compared to classical algorithms. To support general functional bootstrapping, we design a fast quantum private information retrieval (PIR) protocol with logarithmic query time. The security relies on the learning with errors (LWE) problem with polynomial modulus, providing stronger security than classical ``exponentially fast'' PIR protocol based on ring-LWE with super-polynomial modulus.
Technically, we extend a key classical homomorphic operation, known as blind rotation, to the quantum setting through encrypted conditional rotation. Underlying our extension are insights for the quantum extension of polynomial-based cryptographic tools that may gain dramatic speedups. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_20182 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum Fast Implementation of Functional Bootstrapping and Private Information Retrieval Ma, Guangsheng Li, Hongbo Quantum Physics Computational Complexity Cryptography and Security Classical privacy-preserving computation techniques safeguard sensitive data in cloud computing, but often suffer from low computational efficiency. In this paper, we show that employing a single quantum server can significantly enhance both the efficiency and security of privacy-preserving computation. We propose an efficient quantum algorithm for functional bootstrapping of large-precision plaintexts, reducing the time complexity from exponential to polynomial in plaintext-size compared to classical algorithms. To support general functional bootstrapping, we design a fast quantum private information retrieval (PIR) protocol with logarithmic query time. The security relies on the learning with errors (LWE) problem with polynomial modulus, providing stronger security than classical ``exponentially fast'' PIR protocol based on ring-LWE with super-polynomial modulus. Technically, we extend a key classical homomorphic operation, known as blind rotation, to the quantum setting through encrypted conditional rotation. Underlying our extension are insights for the quantum extension of polynomial-based cryptographic tools that may gain dramatic speedups. |
| title | Quantum Fast Implementation of Functional Bootstrapping and Private Information Retrieval |
| topic | Quantum Physics Computational Complexity Cryptography and Security |
| url | https://arxiv.org/abs/2409.20182 |