Post-quantum auditing for outsourced storage with probabilistic guarantees

Auditing outsourced data is a fundamental mechanism for detecting data loss or corruption in untrusted storage environments. Existing auditing schemes rely on public-key primitives based on classical hardness assumptions, which are not secure against quantum adversaries. In this paper, we investigate the issue of post-quantum auditing of outsourced data. We design the PQ-Audit auditing scheme, which utilizes a hash-based signature construction. Specifically, PQ-Audit consists of a small number of hash-based signatures and a hypertree to verify the authenticity of the outsourced data. The data owner signs each outsourced data object before storing it, and the storage server saves these signed data objects for subsequent auditing purposes. However, considering the large size of post-quantum signatures, directly auditing all certified data objects is inefficient. To address this issue, PQ-Audit introduces a sampling-based auditing mechanism that draws inspiration from the provable data possession principle. Audits are conducted on a randomly selected subset of outsourced data objects, which reduces the communication and verification costs during the auditing process and enables efficient auditing. The security analysis demonstrates that PQ-Audit can detect data loss or damage with a probability proportional to the sampling parameter, thereby achieving post-quantum security. Additionally, we conducted a large number of experiments, and the results show that PQ-Audit can efficiently audit large-scale outsourced datasets.