TY - GEN
T1 - Lattice-based universal accumulator with nonmembership arguments
AU - Yu, Zuoxia
AU - Au, Man Ho
AU - Yang, Rupeng
AU - Lai, Junzuo
AU - Xu, Qiuliang
N1 - Funding Information:
Acknowledgement. We appreciate the anonymous reviewers for their valuable suggestions. Part of this work was supported by the National Natural Science Foundation of China (Grant No. 61602396, U1636205, 61572294, 61632020), the MonashU-PolyU-Collinstar Capital Joint Lab on Blockchain and Cryptocurrency Technologies, and from the Research Grants Council of Hong Kong (Grant No. 25206317). The work of Junzuo Lai was supported by the National Natural Science Foundation of China (Grant No. 61572235), and Guangdong Natural Science Funds for Distinguished Young Scholar (No. 2015A030306045).
Publisher Copyright:
© Springer International Publishing AG, part of Springer Nature 2018.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
KW - Abstract stern-like protocol
KW - Lattice-based universal accumulator
KW - Zero-knowledge arguments of nonmembership
UR - http://www.scopus.com/inward/record.url?scp=85049778937&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-93638-3_29
DO - 10.1007/978-3-319-93638-3_29
M3 - Conference article published in proceeding or book
AN - SCOPUS:85049778937
SN - 9783319936376
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 502
EP - 519
BT - Information Security and Privacy - 23rd Australasian Conference, ACISP 2018, Proceedings
A2 - Susilo, Willy
A2 - Yang, Guomin
PB - Springer Verlag
T2 - 23rd Australasian Conference on Information Security and Privacy, ACISP 2018
Y2 - 11 July 2018 through 13 July 2018
ER -