永田 裕大
In the management of large-scale data sets, membership proofs that demonstrate whether an element belongs to a set are essential. Vector commitments (VCs) are a cryptographic primitive that enable such membership proofs. A VC maintains a short commitment to an entire data set represented as a vector and allows one to prove that each element is included in the data set. In VCs, it is crucial that proofs are tamper-resistant and that the generation, update, and verification of proofs for many elements can be performed efficiently. Hyperproofs, proposed by Srinivasan et al., are a vector commitment scheme that enables efficient generation and aggregation of membership proofs for large vectors. In Hyperproofs, proofs are managed in a tree structure, where vector elements are stored at the leaf nodes. Since the proof for each element follows a path in the tree, parts of the proof are shared among different elements. Moreover, the update procedure is designed so that only the path corresponding to the modified element needs to be updated. However, for holders of elements at other positions to update their commitments and proofs, it is necessary to reveal which index in the vector has been updated. Leakage of the update position can expose access patterns, which may pose a privacy concern. In this work, we propose an extension of Hyperproofs that achieves update-position privacy. In the proposed method, a single update is processed as a simultaneous update of multiple positions by also updating positions that do not contain actual elements (dummy updates). By publishing both real and dummy updates in the same format, an observer cannot distinguish the true update position. Furthermore, random update values are applied to the dummy positions to prevent identification based on update patterns. We also provide a security proof for the proposed scheme.
