Processing Private Queries over an Obfuscated Database Using Hidden Vector Encryption

Alberto Trombetta, Giuseppe Persiano, Stefano BraghinNordSec 2014 · DOI

TL;DR

This paper introduces a novel attribute-based encryption scheme called Hidden Vector Encryption (HVE) to enable private querying of encrypted data stored in the cloud. Their approach allows users to perform SQL-like selection-projection queries on encrypted data without decrypting the entire database, offering a practical solution for secure cloud data management.

What Problem Does This Paper Address?

The increasing adoption of cloud computing for data storage presents a significant security challenge: how to ensure data confidentiality when the data is managed by a potentially untrusted third-party provider. While encrypting data is a common solution, it severely limits the ability to query and utilize the data. Traditional database systems rely on the DBMS to enforce access control, but this is not viable when the DBMS itself is untrusted. Existing solutions for searching encrypted data often struggle with structured, relational data and expressive SQL-like queries. This paper addresses the need for a method to perform specific, selective queries on encrypted relational data in a cloud environment, where the data owner can control access based on query attributes without revealing the query itself or the data to the cloud provider.

Methods

The core of the paper's contribution is an application-level database encryption technique based on a Hidden Vector Encryption (HVE) scheme. This scheme is built upon the Dual Pairing Vector Space (DPVS) framework. Here's a breakdown of their approach:

  • Attribute-Based Encryption (ABE): The system uses an ABE scheme where data is encrypted with attributes, and users are granted decryption keys associated with specific attribute policies. This allows for fine-grained access control.
  • Hidden Vector Encryption (HVE): This is a specific type of ABE where the search values within the encrypted data and the query attributes are "obfuscated." This means that the cloud provider cannot infer the search criteria from the encrypted data or the query tokens.
  • DPVS Framework: The underlying cryptographic construction leverages the DPVS framework, which is efficient for handling large alphabets of attributes, a common scenario in real-world databases.
  • Two-Phase Query Processing:
    1. Data Owner Setup: The data owner encrypts the database using an ABE scheme. They then generate "parametric" decryption keys that encode query structures but leave specific search values as placeholders.
  • User Querying: Users receive these parametric keys. When a user wants to query, they provide the specific search values, which are then used to complete the decryption key. A separate, trusted query processor then uses this complete key to query the encrypted database.
  • Amortized Scheme: For scenarios where multiple related records need to be encrypted (e.g., rows with similar attributes), they propose an amortized scheme that reduces the overall ciphertext size.
  • Application-Level Encryption: The encryption and decryption logic operate at the application level, meaning the untrusted DBMS only stores encrypted data and does not perform any decryption or query processing itself.

Datasets

The paper does not introduce new benchmarks or datasets. Instead, they use synthetic relational tables of varying sizes for their experimental evaluation. They also mention using real-world, off-the-shelf RDBMS (SQLite) for their implementation.

Key Insights and Ideas

  • Decoupling Encryption from Querying: The HVE scheme allows data to be encrypted independently of any specific queries. This means new queries or users can be added without re-encrypting the entire database, a significant advantage for dynamic environments.
  • Obfuscated Search: The "hidden vector" aspect is crucial. It ensures that the cloud provider cannot learn the search parameters from the encrypted data or the query keys, thus preserving query privacy.
  • Practicality for Relational Data: Unlike many prior works that focused on unstructured data, this approach is specifically designed for structured, relational databases and supports expressive SQL-like selection-projection queries.
  • Trusted Query Processor: The architecture relies on a trusted, separate query processor. This is a pragmatic choice, acknowledging that while the DBMS might be untrusted, a dedicated, secure component can handle the decryption and query execution.
  • Efficiency Gains with Amortization: The amortized scheme demonstrates a clever way to reduce storage overhead when dealing with datasets that have many records with similar attribute structures.

Key Results

The paper presents experimental results demonstrating the feasibility of their approach:

  • Query Execution Times: They show that encrypted query execution times are reasonable and scale linearly with the number of columns in the database schema. The primary cost is attributed to cryptographic operations, particularly pairings.
  • Space Overhead: The space overhead for storing the encrypted database scales linearly with the number of columns involved in the encryption. They provide a rule of thumb: limit encryption to columns involved in search predicates to reduce this overhead.
  • Feasibility on Off-the-Shelf RDBMS: Their implementation successfully integrates with an off-the-shelf RDBMS, indicating practical applicability.

Limitations and Future Work

  • Trusted Query Processor Dependency: The system relies on a trusted query processor. If this processor is compromised, the entire system's security is at risk.
  • Query Complexity: While they support selection-projection queries, more complex query types like joins and aggregate queries are not directly addressed in this paper.
  • Future Work: The authors explicitly state they are working on extending their system to handle:
  • Join queries: Combining data from multiple tables.
  • Aggregate queries: Performing operations like SUM, AVG, COUNT on encrypted data.
  • Indexing: Developing mechanisms to avoid full table scans for improved query performance.
  • Verification: Adding mechanisms to verify that the query processor has faithfully executed the query.

Summary updated

BibTeX
@inproceedings{trombetta2014processing,
  author = {Alberto Trombetta and Giuseppe Persiano and Stefano Braghin},
  title = {{Processing Private Queries over an Obfuscated Database Using Hidden Vector Encryption}},
  booktitle = {NordSec},
  year = {2014},
  doi = {10.1007/978-3-319-11599-3\_6},
}
Figure