Ensuring Dynamic Data Integrity based on Variable Block-size BLS in Untrusted Environment

Long Chen, Wei Song, Siu‐Ming Yiu, Wenjun LuoInternational Journal of Digital Content Technology and its Applications 2013 · DOI

TL;DR

This paper tackles the critical challenge of ensuring data integrity in untrusted cloud environments, especially when data is frequently updated. They propose a novel protocol that combines BLS signatures with a dynamic Merkle hash tree (DMHT) that supports variable block sizes, offering efficient public auditability, dynamic data operations, and user-selectable privacy preservation.

What Problem Does This Paper Address?

Cloud computing offers immense benefits in resource utilization and convenience, but it also introduces significant security and privacy concerns. A major challenge is guaranteeing the integrity of data stored on cloud servers, especially when users need to perform dynamic operations like modifying, inserting, or deleting data. Furthermore, ensuring public auditability (allowing third parties to verify data integrity without accessing the data itself) and privacy preservation (preventing sensitive data from being leaked to auditors) adds further complexity. Existing solutions often struggle with either supporting dynamic operations efficiently, maintaining privacy, or handling the fixed, small block sizes associated with BLS signatures, which can lead to inefficient storage and communication overhead.

Methods

The authors introduce an improved protocol built upon an extended security model where all participants (user, server, and auditor) can potentially be untrusted. Their core contributions include:

  • Dynamic Merkle Hash Tree (DMHT) with Relative Index: To overcome the efficiency limitations of traditional Merkle Hash Trees (MHTs) for dynamic operations, they propose a DMHT. Each node in this tree stores not only its hash but also a "relative index." This index helps in efficiently locating nodes and managing updates. The auxiliary authentication information (AAI) includes sibling node information and their relationship to the current node, aiding in verification.
  • Variable Block-size BLS Scheme: BLS signatures are attractive due to their short signature lengths. However, they typically require fixed and small block sizes, leading to inefficiencies. This paper integrates a BLS-based scheme that supports variable block sizes, allowing for more flexible and efficient data handling.
  • Extended Security Model: The protocol operates under a model where the cloud service provider (CSP) is untrusted, and even the user or auditor might act maliciously. This necessitates robust security mechanisms.
  • User-Selectable Privacy Preservation: The privacy-preserving features are made optional, allowing users to choose whether to enable them based on their trust in the third-party auditor.
  • Batch Auditing: The scheme supports batch auditing, enabling the server to handle multiple auditing requests from different users simultaneously, further improving efficiency.

Datasets

Not discussed in the paper. The paper focuses on a theoretical protocol and its performance analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Variable Block Size is Key for BLS Efficiency: The paper highlights that the fixed, small block size limitation of BLS signatures is a major bottleneck for practical cloud storage integrity. By enabling variable block sizes, they significantly improve efficiency.
  • DMHT with Relative Index Solves Dynamic Operation Bottlenecks: The proposed DMHT structure effectively addresses the O(n) complexity issues of traditional MHTs for dynamic operations (insertion, deletion, modification), achieving O(log n) complexity.
  • Untrusted Participants Require a Robust Model: Designing a secure protocol for cloud environments necessitates assuming that all parties involved might be untrusted, leading to a more comprehensive and secure design.
  • Privacy as a Service: Making privacy preservation a user-selectable option provides flexibility and caters to different trust levels users have with third-party auditors.

Key Results

  • Efficiency Improvement: The proposed protocol achieves a computation complexity of O(log n) for dynamic data operations and integrity verification, a significant improvement over existing O(n) schemes.
  • Reduced Communication Cost: Performance analysis (Figures 6 and 7) shows that their BLS-based scheme with variable block sizes generally offers lower communication costs compared to Wang's RSA-based scheme and even their own BLS scheme without privacy preservation, especially for certain block size configurations.
  • Security Guarantees: The scheme provides storage correctness, privacy preservation (user-selectable), and user data correctness guarantees, assuming the underlying cryptographic primitives are secure.

Limitations and Future Work

  • Performance Trade-offs: While the BLS scheme with privacy preservation offers benefits, the paper notes that its communication cost can exceed Wang's RSA-based scheme when block sizes are very large.
  • Practical Implementation Details: The paper focuses on the theoretical aspects and protocol design. Further work would involve practical implementation and extensive real-world testing.
  • Further Optimization: While significant improvements are shown, there's always room for further optimization in terms of computational and communication overhead.
  • More Complex Dynamic Operations: The paper covers insertion, deletion, and modification. Future work could explore more complex dynamic operations or scenarios.

Summary updated

Abstract

Security becomes the major concern when people utilizing cloud computing. One major challenge is to ensure the integrity of data in untrusted environment under the condition of supporting public auditability and dynamic data operation. The paper proposes an improved data integrity verifying protocol to ensure the security of user’s data and promote the verifying efficiency using dynamic Merkle tree with relative index. The protocol is based on an extended security model for untrusted environment where each participant may act as an untrusted role. Furthermore, because BLS based schemes have the advantages of shorter homomorphic signatures than RSA based schemes but with disadvantage of fixed and small block-size, a BLS based scheme with variable block-size is integrated in the protocol. Performances analysis showed that the improved protocol is effective and provides a practical and flexible solution for untrusted environment. The computation complexity of dynamic data operation and integrity verifying reaches O(log n) definitely.
BibTeX
@article{chen2013ensuring,
  author = {Long Chen and Wei Song and Siu‐Ming Yiu and Wenjun Luo},
  title = {{Ensuring Dynamic Data Integrity based on Variable Block-size BLS in Untrusted Environment}},
  journal = {International Journal of Digital Content Technology and its Applications},
  year = {2013},
  doi = {10.4156/jdcta.vol7.issue5.98},
}
Figure