Paper 2021/1303

Black-Box Accumulation Based on Lattices

Sebastian H. Faller
Pascal Baumer
Michael Klooß
Alexander Koch
Astrid Ottenhues
Markus Raiber

Black-box accumulation (BBA) is a cryptographic protocol that allows users to accumulate and redeem points, e.g. in payment systems, and offers provable security and privacy guarantees. Loosely speaking, the transactions of users remain unlinkable, while adversaries cannot claim a false amount of points or use points from other users. Attempts to spend the same points multiple times (double spending) reveal the identity of the misbehaving user and an undeniable proof of guilt. Known instantiations of BBA rely on classical number-theoretic assumptions, which are not post-quantum secure. In this work, we propose the first lattice-based instantiation of BBA, which is plausibly post- quantum secure. It relies on the hardness of the Learning with Errors (LWE) and Short Integer Solution (SIS) assumptions and is secure in the Random Oracle Model (ROM). Our work shows that a lattice-based instantiation of BBA can be realized with a communication cost per transaction of about 199 MB if built on the zero-knowledge protocol by Yang et al. (CRYPTO 2019) and the CL-type signature of Libert et al. (ASIACRYPT 2017). Without any zero-knowledge overhead, our protocol requires 1.8 MB communication.

Note: This is the full version of a paper accepted at the 18th IMA International Conferenceon Cryptography and Coding. It will be updated to include a link to the published version, when available.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. 18th IMA International Conference on Cryptography and Coding
Lattice-based Cryptography Black-box Accumulation (BBA) Electronic Funds Transfer Security and Privacy Learning with Errors (LWE) Short Integer Solution (SIS)
Contact author(s)
sebastian faller @ mailbox org
ueeap @ student kit edu
michael klooss @ kit edu
alexander koch @ kit edu
astrid ottenhues @ kit edu
markus raiber @ kit edu
2022-06-12: last of 3 revisions
2021-09-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sebastian H.  Faller and Pascal Baumer and Michael Klooß and Alexander Koch and Astrid Ottenhues and Markus Raiber},
      title = {Black-Box Accumulation Based on Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1303},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.