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
- RSA Encryption: A robust public-key approach that generates fixed 1024-bit codes regardless of input size.
- Cryptographic Hashing: Utilizes PBKDF2 with HMAC-SHA1 to produce 128-bit outputs, offering better storage efficiency than RSA.
- 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.
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.
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