ArcEDB: An Arbitrary-Precision Encrypted Database via (Amortized) Modular Homomorphic Encryption

Zhou Zhang, Song Bian, Zian Zhao, Ran Mao, Haoyi Zhou, Jiafeng Hua, Yier Jin, Zhenyu Guan

TL;DR

This paper introduces ArcEDB, a novel encrypted database system that overcomes a critical trade-off in fully homomorphic encryption (FHE). ArcEDB achieves both arbitrary-precision data handling and significantly faster query execution than previous FHE-based solutions, making encrypted databases more practical for real-world applications.

What Problem Does This Paper Address?

Storing sensitive data in the cloud offers convenience and cost savings, but it raises significant security concerns. Encrypted databases (EDBs) aim to solve this by encrypting data before outsourcing it. However, existing FHE-based EDBs face two major hurdles:

  1. Limited Data Precision: To achieve faster computation, many FHE-based EDBs sacrifice data precision, often limiting operations to 32-bit integers. This is problematic for applications dealing with high-precision data like timestamps or financial records, where even a small loss of precision can render the data useless.
  2. High Computational Latency: Evaluating complex SQL queries, especially those involving comparisons and aggregations, requires a massive number of homomorphic operations. This leads to prohibitively slow query execution times, making these systems impractical for interactive use.

The authors aim to bridge this gap by developing an FHE-based EDB that offers both arbitrary-precision data processing and significantly improved query performance.

Methods

ArcEDB's core innovation lies in its novel FHE infrastructure and specialized algorithms designed for database operations:

  • Modular Homomorphic Encryption (MFHE): ArcEDB utilizes a variant of MFHE, which breaks down large numbers into smaller chunks, each encrypted separately. This allows for higher precision without drastically increasing computational overhead.
  • New Plaintext Encoding Schemes:
    • Exponent Encoding: This scheme is crucial for efficient homomorphic comparisons. Instead of directly encrypting the value, it encrypts a representation that allows comparisons to be performed via polynomial multiplications, which are much faster than traditional FHE comparison methods.
  • Modular Ciphertexts: ArcEDB employs modular versions of LWE and RLWE ciphertexts, where large numbers are represented as a sequence of smaller encrypted chunks.
  • Advanced Homomorphic Operators:
    • HCMP (Homomorphic Comparison): A fast comparison operator optimized for exponent-encoded ciphertexts, suitable for limited precision.
  • ArbHCMP (Arbitrary-Precision Homomorphic Comparison): This operator extends HCMP to handle arbitrary precision by combining lower-precision comparisons with a novel homomorphic multiplexer (MUX) operator called GateMUX. GateMUX efficiently combines comparison results from different chunks.
  • SIMDArbHCMP (Amortized Arbitrary-Precision Homomorphic Comparison): This is a batched version of ArbHCMP that processes multiple data items simultaneously, significantly boosting performance for large datasets. It leverages a SIMDCMUX operator.
  • HomSort and SortSynchronize: Novel algorithms for efficient homomorphic sorting and synchronization of columns, addressing a limitation in previous EDBs.
  • Layered Architecture: ArcEDB uses a layered approach (ciphertext, data type, table structure) to decouple low-level FHE primitives from high-level database operations, enhancing flexibility.

Datasets

The paper evaluates ArcEDB using:

  • TPC-H benchmarks: A standard benchmark for relational databases.
  • Real-world time-series database queries: Used to demonstrate performance on time-series data, a domain where precision is critical.

The authors do not introduce new datasets but adapt existing benchmarks to their encrypted database context.

Key Insights and Ideas

  • Exponent Encoding is Key for Fast Comparisons: The paper demonstrates that by encoding data in a specific "exponent" format, homomorphic comparisons can be drastically accelerated, moving away from slower, PBS-based methods.
  • Modular Arithmetic for Precision: Breaking down large numbers into smaller, encrypted chunks (modular arithmetic) is essential for achieving arbitrary precision without overwhelming computational costs.
  • Combining Low-Level Primitives for High-Level Tasks: ArcEDB's success comes from cleverly combining specialized homomorphic operators (like HCMP, GateMUX, SIMDCMUX) to build complex SQL operations (filtering, sorting, aggregation) efficiently.
  • Batching is Crucial for Scale: The SIMDArbHCMP operator, which processes data in batches, is vital for achieving significant speedups on larger datasets, highlighting the importance of parallelization in FHE.
  • Synchronization is a Novel Contribution: The ability to synchronize sorted columns is a significant advancement for EDBs, enabling more complex queries like those involving ORDER BY clauses.

Key Results

  • Filtering Speedup: ArcEDB's ArbHCMP is 6x-56x faster than state-of-the-art (SOTA) methods for relational comparisons and 20x-112x faster for equality comparisons. SIMDArbHCMP offers even greater speedups on larger datasets.
  • Filter-Aggregation Performance: ArcEDB achieves 4x-7x speedup over HE³DB [16] for 10K records and 36x-102x acceleration for 32K records.
  • ORDER BY Performance: ArcEDB is 2x-3x faster than HE³DB [16] and TFHE-rs [111] for single-column sorting and 3x-8x faster than Onion Ring ORAM for column synchronization.
  • End-to-End SQL Queries: ArcEDB is, on average, 16x faster than HE³DB [16] and 72x faster than HEDA [99] on relational databases. For time-series data, it achieves 19x faster than HE³DB and 75x faster than HEDA.
  • Practical Performance: A 10K-row time-series EDB query with 64-bit timestamps can be evaluated in under one minute.
  • Memory Efficiency: ArcEDB uses, on average, 1.6x less memory than HE³DB [16] for 16-bit precision queries.

Limitations and Future Work

  • Latency Improvement Needed: While ArcEDB offers significant speedups, the authors acknowledge that further latency improvements are desirable for real-world interactive applications.
  • Future Work: The authors suggest exploring more advanced cryptographic primitives and hardware-accelerated solutions to further enhance efficiency.

Summary updated

BibTeX
@article{zhang2024arcedb,
  author = {Zhou Zhang and Song Bian and Zian Zhao and Ran Mao and Haoyi Zhou and Jiafeng Hua and Yier Jin and Zhenyu Guan},
  title = {{ArcEDB: An Arbitrary-Precision Encrypted Database via (Amortized) Modular Homomorphic Encryption}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2024},
  url = {https://openreview.net/forum?id=XZGadXh9ut},
}

Loading related content...

Figure