Integrity Coded Databases: An Evaluation of Performance, Efficiency, and Practicality

Dan Kondratyuk, Jake Rodden, Elmer DuranarXiv 2018 · arXiv

Introduction

As organizations increasingly migrate sensitive data to third-party cloud providers, they face a significant "trust gap." While standard encryption ensures data privacy, it does not guarantee data integrity—the assurance that records have not been maliciously modified, added, or deleted. Integrity Coded Databases (ICDBs) address this by appending cryptographic "Integrity Codes" to data, enabling users to verify the correctness and freshness of retrieved information. This paper evaluates the real-world performance and storage costs associated with various ICDB implementations.

Methodology

The study examines three cryptographic schemes and two architectural models for integrity verification:

Cryptographic Schemes

  1. RSA Encryption: A robust public-key approach that generates fixed 1024-bit codes regardless of input size.
  2. Cryptographic Hashing: Utilizes PBKDF2 with HMAC-SHA1 to produce 128-bit outputs, offering better storage efficiency than RSA.
  3. AES (Advanced Encryption Standard): A symmetric-key block cipher that facilitates fast computation and potential data recovery.

Architectural Models

The researchers compared One Code per Field (OCF), where every column is protected individually, against One Code per Tuple (OCT), which generates a single code for an entire row. OCT significantly improves the data-to-code ratio and reduces metadata overhead.

Experimental Setup

The evaluation utilized three standard MySQL datasets of varying scales:

  • World (0.8 MiB): Small-scale geographic data.
  • Sakila (7 MiB): Medium-scale DVD rental records.
  • Employees (200 MiB): Large-scale personnel data.

Results and Analysis

Storage Overhead

The choice of cryptographic scheme profoundly impacts storage requirements. On average, database size increased by 2.5x with AES, 9x with Hashing, and 23x with RSA. The "small data penalty" is particularly evident in RSA, where a 1024-bit code might protect a field as small as 48 bits, leading to massive inefficiencies.

Storage overhead across datasets and cryptographic schemes

Performance and the Verification Bottleneck

While SQL execution times remain relatively stable, the primary performance bottleneck lies in the verification phase. For RSA-based OCF, the time required for the client to verify integrity codes can be up to 40,000x longer than the actual database execution. This overhead effectively dwarfs all other parts of the query lifecycle.

Query execution breakdown highlighting the verification bottleneck

Conversion times also vary wildly. While AES can process the Employees database in seconds, RSA-based conversion was estimated to require over 18 hours. Query latency ratios further highlight these costs: AES-based queries in the World dataset were 1.74x slower than standard SQL, while RSA-based queries were 4.86x slower.

Conclusion

While ICDBs provide essential security guarantees for outsourced data, the overheads—particularly for RSA-based field-level coding—are currently prohibitive for many production environments. Transitioning to per-tuple (OCT) coding and implementing parallel verification processes are critical steps toward making ICDBs practically viable. Future work should explore hybrid models and the performance of ICDBs in NoSQL and other SQL environments.

Summary updated

BibTeX
@misc{kondratyuk2018integrity,
  author = {Dan Kondratyuk and Jake Rodden and Elmer Duran},
  title = {{Integrity Coded Databases: An Evaluation of Performance, Efficiency, and Practicality}},
  year = {2018},
  eprint = {1802.00230},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.00230},
}
Figure