Lattice-based universal accumulator with nonmembership arguments

Zuoxia Yu, Man Ho Au, Rupeng Yang, Junzuo Lai, Qiuliang Xu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

5 Citations (Scopus)


Universal accumulator provides a way to accumulate a set of elements into one. For each element accumulated, it can provide a short membership (resp. nonmembership) witness to attest the fact that the element has been (resp. has not been) accumulated. When combined with a suitable zero-knowledge proof system, it can be used to construct many privacy-preserving applications. However, existing universal accumulators are usually based on non-standard assumptions, e.g., the Strong RSA assumption and the Strong Diffie-Hellman assumptions, and are not secure against quantum attacks. In this paper, we propose the first lattice-based universal accumulator from standard lattice-based assumptions. The starting point of our work is the lattice-based accumulator with Merkle-tree structure proposed by Libert et al. (Eurocrypt’16). We present a novel method to generate short witnesses for non-accumulated members in a Merkle-tree, and give the construction of universal accumulator. Besides, we also propose the first zero-knowledge arguments to prove the possession of the nonmembership witness of a non-accumulated value in the lattice-based setting via the abstract Stern’s protocol of Libert et al. (Asiacrypt’17). Moreover, our proposed universal accumulator can be used to construct many privacy-preserving cryptographic primitives, such as group signature and anonymous credential.

Original languageEnglish
Title of host publicationInformation Security and Privacy - 23rd Australasian Conference, ACISP 2018, Proceedings
EditorsWilly Susilo, Guomin Yang
PublisherSpringer Verlag
Number of pages18
ISBN (Print)9783319936376
Publication statusPublished - 2018
Event23rd Australasian Conference on Information Security and Privacy, ACISP 2018 - Wollongong, Australia
Duration: 11 Jul 201813 Jul 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10946 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference23rd Australasian Conference on Information Security and Privacy, ACISP 2018


  • Abstract stern-like protocol
  • Lattice-based universal accumulator
  • Zero-knowledge arguments of nonmembership

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Lattice-based universal accumulator with nonmembership arguments'. Together they form a unique fingerprint.

Cite this