An Integrity Lock Architecture for Supporting Distributed Authorizations in Database Federations

Wei Li, Lingyu Wang, Bo Zhu, Lei ZhangIFIP 2008 · DOI · OpenAlex

Abstract

In loosely coupled database federations, autonomous organizations must share data without a centralized security authority or full mutual trust. This paper proposes an adapted Integrity Lock architecture that secures data through cryptographic signatures. By implementing a novel two-dimensional grid of Merkle Hash Trees (MHTs), the system ensures data integrity and supports efficient updates in dynamic environments. Experimental results demonstrate that with appropriate caching, the security overhead remains minimal while providing robust detection of unauthorized modifications.

Introduction

Modern information systems often require data sharing across organizational boundaries, such as between a university and a hospital. These "loosely coupled" federations present a significant security challenge: how to maintain fine-grained access control and data integrity when the remote database storing the shared information is not fully trusted. Traditional models often assume static data or rely on a centralized authority, neither of which is practical in dynamic, autonomous federations.

The Integrity Lock Architecture

The authors address these challenges by adapting the Integrity Lock architecture. Originally designed for multi-level secure databases, this approach treats the local database (the data owner) as a trusted front-end filter. When data is exported to an untrusted remote database, the local system appends cryptographic stamps—MACs or digital signatures—directly to the records.

Figure 2: Conceptual overview of a database federation between a university and a hospital, showing local and remote database interactions.

This "lock" ensures that security policies are bound to the data itself. When a query is executed, the local system retrieves the data and verifies the stamps. If the remote DBMS attempts to tamper with the data or bypass access controls, the verification process will fail, alerting the data owner to the breach.

The 2D Merkle Hash Tree Grid

A primary innovation of this work is the use of a two-dimensional grid of Merkle Hash Trees (MHTs) to manage data integrity in dynamic systems. While row-level signatures can detect tampering within a record, they cannot easily detect the omission of entire records (the completeness problem) or efficiently handle frequent updates.

Figure 6: The 2D MHT grid structure showing row signatures (y) and column signatures (x) derived from attribute values.

As shown in Figure 6, the system maintains two sets of signatures:

  • Row Signatures ($y_i$): Each tuple (row) is represented by a signature derived from an MHT of its attributes.
  • Column Signatures ($x_j$): Each attribute (column) across all records is represented by a signature derived from a separate MHT.

This grid allows the system to "localize" modifications. If a single cell in the database is changed, both its corresponding row and column signatures will become invalid. This dual-axis verification pinpoints the exact location of the change, facilitating a more efficient dispute resolution process.

Verification and Update Protocol

To maintain performance, the system employs a three-stage "lazy" verification protocol:

  1. Detection: Integrity is checked only at the time of a query (read operation) rather than during every write.
  2. Proof Collection: If a signature mismatch is detected, the local database requests signed logs from the remote database to determine if the update was authorized by a legitimate user.
  3. Accommodation: If the update is proven legitimate, the local database recomputes the affected row and column signatures and transmits them to the remote database to "lock" the new state.

Performance and Evaluation

The architecture was evaluated using a Java-based implementation with an Oracle 10g backend. The study focused on the computational cost of maintaining the 2D MHT grid.

A key finding was the impact of caching. Recomputing a column-wide MHT for every update is an $O(N)$ operation. However, by caching the upper levels of the MHT (the top 3–10 levels), the authors reduced the update cost to $O(\log N)$. This optimization allows the secured system to achieve performance parity with standard, unsecured database updates. Furthermore, the study found that dynamic caching (using an LRU policy) is particularly effective when user queries are clustered around specific data segments.

Conclusion

The proposed Integrity Lock architecture provides a robust framework for securing distributed authorizations in database federations. By binding security to the data via a 2D MHT grid, the system achieves end-to-end integrity without requiring a trusted remote DBMS. Future work will explore handling concurrent updates from multiple organizations and mitigating potential denial-of-service attacks where a malicious remote database intentionally corrupts data to trigger constant verification cycles.

Summary updated

BibTeX
@inproceedings{li2008integrity,
  author = {Wei Li and Lingyu Wang and Bo Zhu and Lei Zhang},
  title = {{An Integrity Lock Architecture for Supporting Distributed Authorizations in Database Federations}},
  booktitle = {IFIP},
  year = {2008},
  doi = {10.1007/978-0-387-09699-5\_13},
}
Figure