EKV-VBQ: Ensuring Verifiable Boolean Queries in Encrypted Key-Value Stores

Yuxi Li, Jingjing Chen, Fucai Zhou, Dong JiSensors 2024 · DOI

TL;DR

This paper introduces EKV-VBQ, a novel system for securely querying encrypted key-value data using verifiable Boolean logic. By integrating blockchain for integrity and bilinear accumulators for efficient verification, EKV-VBQ allows users to trust query results from untrusted servers, even with complex queries, while significantly reducing client-side computational load.

What Problem Does This Paper Address?

In today's data-driven world, key-value stores are fundamental to many applications, from e-commerce to IoT. However, when this sensitive data is outsourced to cloud providers, ensuring its privacy and the integrity of query results becomes a major challenge. Traditional encryption methods make searching difficult, and while "encrypted search" techniques exist, they often fall short in two key areas: supporting expressive Boolean queries (combining conditions with AND, OR, NOT) and providing efficient, reliable verification of query results. Existing solutions can be computationally expensive for clients or lack robust verification mechanisms, leaving users vulnerable to data tampering or incorrect results, especially in resource-constrained environments like mobile devices.

Methods

EKV-VBQ tackles these issues through a multi-pronged approach:

  • Blockchain Integration: The core key-value data is stored on a blockchain (specifically Ethereum's PoS). This provides inherent tamper-resistance and immutability, ensuring that once data is added, it cannot be altered or deleted without authorization. This also guarantees query integrity.
  • Homomorphic Encryption and Pseudo-Random Functions: To enable searching on encrypted data, EKV-VBQ uses homomorphic operations (specifically XOR) and pseudo-random functions. This allows the server to perform computations on encrypted data without decrypting it, preserving privacy.
  • Bilinear Map Accumulators: For efficient and lightweight verification of Boolean query results, the paper employs bilinear map accumulators. These cryptographic tools allow the server to generate compact proofs of correctness for query results, which the client can then verify quickly.
  • Lightweight Verification Protocol: A novel verification protocol is designed, leveraging the bilinear accumulators, to ensure that the Boolean query results are not only correct but also complete, meaning all matching records are returned and none have been tampered with.
  • GPU Acceleration: To further enhance performance, especially for proof generation, the system incorporates GPU-accelerated optimizations.

Datasets

Not discussed in the paper. The paper focuses on a synthetic key-value database with 100,000 randomly generated key/value pairs for experimental evaluation.

Key Insights and Ideas

  • Blockchain as a Trust Anchor for Data Integrity: The paper demonstrates how blockchain's inherent immutability can be effectively leveraged to guarantee the integrity of the underlying encrypted data store, removing the need to trust the server for data correctness.
  • Bilinear Accumulators for Efficient Verifiability: The use of bilinear accumulators is a key innovation, enabling a lightweight verification process for complex Boolean queries. This is crucial for client-side performance, especially on mobile devices.
  • Balancing Security and Performance: EKV-VBQ strikes a compelling balance. It achieves strong security guarantees (IND-CLA, Integrity, Unforgeability) while significantly reducing computational overhead for the client, a common bottleneck in existing secure search schemes.
  • GPU Acceleration for Practicality: The integration of GPU acceleration for proof generation highlights a practical approach to making advanced cryptographic schemes feasible in real-world, resource-constrained scenarios.

Key Results

  • Security Guarantees: EKV-VBQ is proven secure against adaptive chosen label attacks (IND-CLA) and guarantees Integrity and Unforgeability under the bilinear q-strong Diffie-Hellman assumption.
  • Performance Improvements:
    • Reduced server-side storage overhead.
  • Efficient proof generation.
  • User-side computational complexity reduced by a factor of log n.
  • GPU-accelerated optimizations reduced computational overhead by up to 50%.
  • Communication Overhead: For query results, the communication overhead decreased as the number of query labels increased (e.g., from 792.05 to 141.01 bytes for 2 to 10 labels). However, proof data volume increased, becoming the primary factor influencing communication.
  • Computation Overhead: Query time on the blockchain was approximately linear with the number of labels. Proof generation was more time-consuming but remained relatively stable. Client-side verification overhead was between 1.4 and 1.6 seconds, representing a significant reduction in computational burden compared to the server.

Limitations and Future Work

  • Limitations: The paper acknowledges that while EKV-VBQ supports Boolean queries, extending it to more complex query types (e.g., range queries, fuzzy searches) would be beneficial. The current implementation relies on specific cryptographic assumptions (bilinear q-strong Diffie-Hellman), and the performance might be further impacted by the choice of curve parameters and pairing algorithms.
  • Future Work:
    • Advanced Blockchain Integration: Exploring newer blockchain platforms like DPoS for lower energy consumption and faster consensus. Investigating sharding or sidechains for enhanced scalability.
  • Mobile and IoT Applications: Further reducing computational load and energy consumption for better practicality on mobile and IoT devices, potentially through hardware-specific optimizations.
  • Complex Queries: Extending support to multi-conditional range queries, fuzzy searches, or keyword proximity searches while maintaining verifiability.
  • Multi-Party Computation (MPC): Integrating EKV-VBQ with MPC frameworks to enable collaborative querying among multiple data owners without revealing private inputs, particularly useful for federated learning or healthcare data sharing.
  • Domain-Specific Adaptations: Adapting EKV-VBQ for privacy-sensitive sectors like healthcare and finance, ensuring compliance with regulations like GDPR and HIPAA.

Summary updated

Abstract

To address the deficiencies in privacy-preserving expressive query and verification mechanisms in outsourced key-value stores, we propose EKV-VBQ, a scheme designed to ensure verifiable Boolean queries over encrypted key-value data. We have integrated blockchain and homomorphic Xor operations and pseudo-random functions to create a secure and verifiable datastore, while enabling efficient encrypted Boolean queries. Additionally, we have designed a lightweight verification protocol using bilinear map accumulators to guarantee the correctness of Boolean query results. Our security analysis demonstrates that EKV-VBQ is secure against adaptive chosen label attacks (<i>IND-CLA</i>) and guarantees <i>Integrity and Unforgeability</i> under the bilinear <i>q</i>-strong Diffie-Hellman assumption. Our performance evaluations showed reduced server-side storage overhead, efficient proof generation, and a significant reduction in user-side computational complexity by a factor of log <i>n</i>. Finally, GPU-accelerated optimizations significantly enhance EKV-VBQ's performance, reducing computational overhead by up to 50%, making EKV-VBQ highly efficient and suitable for deployment in environments with limited computational resources.
BibTeX
@inproceedings{li2024ekv,
  author = {Yuxi Li and Jingjing Chen and Fucai Zhou and Dong Ji},
  title = {{EKV-VBQ: Ensuring Verifiable Boolean Queries in Encrypted Key-Value Stores}},
  booktitle = {Sensors},
  year = {2024},
  doi = {10.3390/s24216792},
}
Figure