SIMD-Aware Homomorphic Compression and Application to Private Database Query

• URL: http://arxiv.org/abs/2408.17063v1
• Date: Fri, 30 Aug 2024 07:49:34 GMT
• Title: SIMD-Aware Homomorphic Compression and Application to Private Database Query
• Authors: Jung Hee Cheon, Keewoo Lee, Jai Hyun Park, Yongdong Yeo,
• Abstract summary: 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 sparse encrypted vectors consisting of query results. We propose a new homomorphic compression scheme with PDQ as its main application.
• Score: 11.07170537925803
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Effective Instruction Parsing Plugin for Complex Logical Query Answering on Knowledge Graphs [51.33342412699939]
  Knowledge Graph Query Embedding (KGQE) aims to embed First-Order Logic (FOL) queries in a low-dimensional KG space for complex reasoning over incomplete KGs. Recent studies integrate various external information (such as entity types and relation context) to better capture the logical semantics of FOL queries. We propose an effective Query Instruction Parsing (QIPP) that captures latent query patterns from code-like query instructions.
  arXiv  Detail & Related papers  (2024-10-27T03:18:52Z)
• A framework for compressing unstructured scientific data via serialization [2.5768995309704104]
  We present a general framework for compressing unstructured scientific data with known local connectivity. A common application is simulation data defined on arbitrary finite element meshes. The framework employs a greedy topology preserving reordering of original nodes which allows for seamless integration into existing data processing pipelines.
  arXiv  Detail & Related papers  (2024-10-10T15:53:35Z)
• Ranking LLMs by compression [13.801767671391604]
  We use five large language models as priors for compression, then compare their performance on challenging natural language processing tasks. Experimental results show that compression ratio and model performance are positively correlated, so it can be used as a general metric to evaluate large language models.
  arXiv  Detail & Related papers  (2024-06-20T10:23:38Z)
• Enc2DB: A Hybrid and Adaptive Encrypted Query Processing Framework [47.11111145443189]
  We introduce Enc2DB, a novel secure database system following a hybrid strategy on and openGauss. We present a micro-benchmarking test and self-adaptive mode switch strategy that can choose the best execution path (cryptography or TEE) to answer a given query. We also design and implement a ciphertext index compatible with native cost model and querys to accelerate query processing.
  arXiv  Detail & Related papers  (2024-04-10T08:11:12Z)
• Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity [92.1840862558718]
  We introduce MARINA-P, a novel method for downlink compression, employing a collection of correlated compressors. We show that MARINA-P with permutation compressors can achieve a server-to-worker communication complexity improving with the number of workers. We introduce M3, a method combining MARINA-P with uplink compression and a momentum step, achieving bidirectional compression with provable improvements in total communication complexity as the number of workers increases.
  arXiv  Detail & Related papers  (2024-02-09T13:58:33Z)
• Extreme Compression of Large Language Models via Additive Quantization [59.3122859349777]
  Our algorithm, called AQLM, generalizes the classic Additive Quantization (AQ) approach for information retrieval. We provide fast GPU and CPU implementations of AQLM for token generation, which enable us to match or outperform optimized FP16 implementations for speed.
  arXiv  Detail & Related papers  (2024-01-11T18:54:44Z)
• LeCo: Lightweight Compression via Learning Serial Correlations [9.108815508920882]
  Lightweight data compression is a key technique that allows column stores to exhibit superior performance for analytical queries. We propose LeCo (i.e., Learned Compression), a framework that uses machine learning to remove the serial redundancy in a value sequence automatically. We observe up to 5.2x speed up in a data analytical query in the Arrow columnar execution engine and a 16% increase in RocksDB's throughput.
  arXiv  Detail & Related papers  (2023-06-27T10:46:36Z)
• Learning Accurate Performance Predictors for Ultrafast Automated Model Compression [86.22294249097203]
  We propose an ultrafast automated model compression framework called SeerNet for flexible network deployment. Our method achieves competitive accuracy-complexity trade-offs with significant reduction of the search cost.
  arXiv  Detail & Related papers  (2023-04-13T10:52:49Z)
• HE is all you need: Compressing FHE Ciphertexts using Additive HE [29.043858170208875]
  Homomorphic Encryption (HE) is a commonly used tool for building privacy-preserving applications. We present a new compression technique that uses an additive homomorphic encryption scheme with small ciphertexts to compress large homomorphic ciphertexts.
  arXiv  Detail & Related papers  (2023-03-16T02:28:40Z)
• A Generic Network Compression Framework for Sequential Recommender Systems [71.81962915192022]
  Sequential recommender systems (SRS) have become the key technology in capturing user's dynamic interests and generating high-quality recommendations. We propose a compressed sequential recommendation framework, termed as CpRec, where two generic model shrinking techniques are employed. By the extensive ablation studies, we demonstrate that the proposed CpRec can achieve up to 4$sim$8 times compression rates in real-world SRS datasets.
  arXiv  Detail & Related papers  (2020-04-21T08:40:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.