Miyaji Laboratory

With the advancement of the digital society, the importance of technologies that guarantee data in- tegrity is increasing. Especially in the context of blockchain and anonymous authentication, methods for efficiently verifying massive datasets are indispensable. The foundational technology for this is the cryptographic accumulator, which compresses a large dataset into a short value and allows for the effi- cient proof of inclusion for specific elements. Since additions and deletions of elements occur frequently in these systems, non-membership proof functionality―showing that an element is not included in the set―is also required. Schemes supporting addition and deletion are called dynamic accumulators, while those capable of proving both membership and non-membership are known as universal accumulators. However, mainstream methods currently rely on the RSA assumption or the discrete logarithm problem on elliptic curves, which are vulnerable to decryption by quantum computers. Existing quantum-resistant accumulators also face challenges; a scheme that performs all operations―insertion, deletion, and non- membership proof―within logarithmic time O(logN) relative to the number of elements N has yet to be established. In this research, we propose the first quantum-resistant dynamic universal accumulator. The security of this scheme is reduced to the hardness of the Short Integer Solution (SIS) problem used in lattice-based cryptography. We present an accumulator where addition, deletion, membership proof, and non-membership proof are all achieved with a computational complexity of O(logN). Our structure adopts a Sparse Merkle Tree (SMT). An SMT does not physically store "default nodes" for non-existent elements, substituting them through computation instead. This enables efficient non-membership proofs while minimizing memory usage. Furthermore, as a second proposal, we introduce a method with an improved SMT configuration. By omitting the default parts during certificate generation, we compress the certificate size. In a system with approximately 230 (one billion) users, a tree height of 256, and parameters ensuring NIST-recommended 128-bit security, the membership certificate size is 192 KB for Method 1 and 23.5 KB for Method 2. In Method 1, we realized non-membership proofs with a certificate size comparable to the dynamic membership-only scheme proposed by Libert et al. Method 2 achieves a further 87% reduction in certificate size.