Paper 2021/545

MatRiCT+: More Efficient Post-Quantum Private Blockchain Payments

Muhammed F. Esgin, Ron Steinfeld, and Raymond K. Zhao

Abstract

We introduce MatRiCT+, a practical private blockchain payment protocol based on ``post-quantum'' lattice assumptions. MatRiCT+ builds on MatRiCT due to Esgin et al. (ACM CCS'19) and, in general, follows the Ring Confidential Transactions (RingCT) approach used in Monero, the largest privacy-preserving cryptocurrency. In terms of the practical aspects, MatRiCT+ has 2-18x shorter proofs (depending on the number of input accounts, M) and runs 3-11x faster (for a typical transaction) in comparison to MatRiCT. A significant advantage of MatRiCT+ is that the proof length's dependence on M is very minimal (only O(log M)), while MatRiCT has a proof length linear in M. To support its efficiency, we devise several novel techniques in our design of MatRiCT+ to achieve compact lattice-based zero-knowledge proof systems, exploiting the algebraic properties of power-of-2 cyclotomic rings commonly used in practical lattice-based cryptography. Along the way, we design a family of ``optimal'' challenge spaces, using a technique we call partition-and-sample, with minimal $\ell_1$-norm and invertible challenge differences (with overwhelming probability), while supporting highly-splitting power-of-2 cyclotomic rings. We believe all these results to be widely applicable and of independent interest.

Note: New results and further details are added.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. IEEE Symposium on Security and Privacy (S&P) 2022
Keywords
Post-QuantumRingCTLatticeZero-KnowledgeBlockchainRing Signature
Contact author(s)
muhammed esgin @ monash edu
ron steinfeld @ monash edu
raymond zhao @ monash edu
History
2021-07-30: revised
2021-04-27: received
See all versions
Short URL
https://ia.cr/2021/545
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/545,
      author = {Muhammed F.  Esgin and Ron Steinfeld and Raymond K.  Zhao},
      title = {MatRiCT+: More Efficient Post-Quantum Private Blockchain Payments},
      howpublished = {Cryptology ePrint Archive, Paper 2021/545},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/545}},
      url = {https://eprint.iacr.org/2021/545}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.