TLARDA: Threshold Label-Aggregating Remote Data Auditing in Decentralized Environment

Remote data integrity auditing enables a client to efficiently ensure the integrity of entire data stored in untrusted servers via auditing. Yet, existing solutions generally emphasize on various metrics (such as minimal storage, fast update, metadata privacy), but not audit performance (e.g., low audit time, small proof size). To this end, a label-aggregating remote data integrity auditing scheme (LARDA) was proposed in ESORICS ’22, which is the state-of-the-art work in terms of proof size and storage cost. However, LARDA needs a trusted third party (TTP) for performing data auditing for all data owners, which introduces a single point of failure since the audit process routinely needs to interact with the TTP. To address this issue, we introduce a new concept called threshold label-aggregating data auditing and propose two novel schemes. Our first solution is based on Pedersen secret sharing technique, which can significantly alleviate the key escrow problem of LARDA. Our second solution is an efficient batch verifying scheme for multiple TTP’s secret key shares, utilizing the KZG (Kate, Zaverucha and Goldberg) secret sharing technique. This scheme can maintain the size of commitment for TTP’s secret key constant rather than a linear factor with the number of TTPs. We conduct comprehensive experiments to demonstrate the scalability of our schemes. In particular, our second scheme improves the verification time for TTP’s secret key shares in constant, only requiring two pairings and one exponentiation in group with an average of 7.39 ms, regardless of the number of TTPs increasing. For our first scheme, the verification procedure requires $2t$ exponentiations in group (where t is the threshold value), ranging from 2.37 ms ( $t = 2$ ) to 26.85 ms ( $t = 35$ ).