SIMD-Aware Homomorphic Compression and Application to Private Database Query
<|reference_start|>SIMD-Aware Homomorphic Compression and Application to Private Database Query: 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.<|reference_end|>
@article{cheon2024simd-aware,
    title={SIMD-Aware Homomorphic Compression and Application to Private Database
  Query},
    author={Jung Hee Cheon, Keewoo Lee, Jai Hyun Park, Yongdong Yeo},
    journal={arXiv preprint arXiv:2408.17063},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.17063},
    primaryClass={cs.CR}
}