SIMD-Aware Homomorphic Compression and Application to Private Database Query
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909301366325248 |
|---|---|
| author | Cheon, Jung Hee Lee, Keewoo Park, Jai Hyun Yeo, Yongdong |
| author_facet | Cheon, Jung Hee Lee, Keewoo Park, Jai Hyun Yeo, Yongdong |
| contents | In a private database query scheme (PDQ), a server maintains a database, and users send queries to retrieve records of interest from the server while keeping their queries private. A crucial step in PDQ protocols based on homomorphic encryption is homomorphic compression, which compresses encrypted sparse vectors consisting of query results. In this work, we propose a new homomorphic compression scheme with PDQ as its main application. Unlike existing approaches, our scheme (i) can be efficiently implemented by fully exploiting homomorphic SIMD technique and (ii) enjoys both asymptotically optimal compression rate and asymptotically good decompression complexity. Experimental results show that our approach is 4.7x to 33.2x faster than the previous best results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_17063 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | SIMD-Aware Homomorphic Compression and Application to Private Database Query Cheon, Jung Hee Lee, Keewoo Park, Jai Hyun Yeo, Yongdong Cryptography and Security In a private database query scheme (PDQ), a server maintains a database, and users send queries to retrieve records of interest from the server while keeping their queries private. A crucial step in PDQ protocols based on homomorphic encryption is homomorphic compression, which compresses encrypted sparse vectors consisting of query results. In this work, we propose a new homomorphic compression scheme with PDQ as its main application. Unlike existing approaches, our scheme (i) can be efficiently implemented by fully exploiting homomorphic SIMD technique and (ii) enjoys both asymptotically optimal compression rate and asymptotically good decompression complexity. Experimental results show that our approach is 4.7x to 33.2x faster than the previous best results. |
| title | SIMD-Aware Homomorphic Compression and Application to Private Database Query |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2408.17063 |