IEEE Access (Jan 2022)
Improving Bitcoin’s Post-Quantum Transaction Efficiency With a Novel Lattice-Based Aggregate Signature Scheme Based on CRYSTALS-Dilithium and a STARK Protocol
Abstract
This paper proposes a novel lattice-based aggregate signature (LAS) scheme that brings post-quantum security to the Bitcoin system without sacrificing its transaction efficiency. Bitcoin currently employs Elliptic Curve Digital Signature Algorithm (ECDSA), which is insecure against the emerging quantum technology, so post-quantum signature schemes like the proposed LAS will become necessary in the near future. However, most of the post-quantum signatures schemes have large signature sizes which decrease Bitcoin’s efficiency. Even CRYSTALS-Dilithium, the most prominent post-quantum signature scheme chosen by the National Institute of Standards and Technology (NIST), has this adverse limitation: it would cause Bitcoin’s transaction efficiency to fall by 17 times from 2759.36622 transactions per block (tpb) to 159.48374 tpb. The existing signature schemes are unable to resolve this efficiency problem for Bitcoin. We crafted a novel LAS scheme based on CRYSTALS-Dilithium and a zero-knowledge Scalable Transparent Arguments of Knowledge (STARK) protocol to tackle this problem. The proposed LAS scheme takes full advantage of signature aggregation using the STARK protocol and Dilithium’s easy and fast implementation, thus generating signatures with post-quantum security and small signature sizes which are critical to transaction efficiency. Our proofs convey the correctness, compactness, and post-quantum security of our scheme in the quantum random oracle model, and our implementation in Python conveyed that the proposed scheme would only decrease Bitcoin’s transaction efficiency by 3 times, a significant improvement from using Dilithium and other lattice-based aggregate signature schemes. Our proposed scheme has many advantages over the existing schemes and will become very valuable to Bitcoin.
Keywords
