Cryptology ePrint Archive: Report 2021/545

MatRiCT+: More Efficient Post-Quantum Private Blockchain Payments

Muhammed F. Esgin and 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-17x shorter proofs (depending on the number of input accounts, M) and runs 3-8x 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 an ``optimal'' challenge space 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.

Category / Keywords: cryptographic protocols / Post-Quantum, RingCT, Lattice, Zero-Knowledge, Blockchain, Ring Signature

Date: received 23 Apr 2021, last revised 23 Apr 2021

Contact author: muhammed esgin at monash edu, ron steinfeld at monash edu, raymond zhao at monash edu

Available format(s): PDF | BibTeX Citation

Version: 20210427:061011 (All versions of this report)

Short URL: ia.cr/2021/545


[ Cryptology ePrint archive ]