Cryptology ePrint Archive: Report 2018/658
Blockchained Post-Quantum Signatures
Konstantinos Chalkias and James Brown and Mike Hearn and Tommy Lillehagen and Igor Nitto and Thomas Schroeter
Abstract: Inspired by the blockchain architecture and existing Merkle tree based signature schemes, we propose BPQS, an extensible post-quantum (PQ) resistant digital signature scheme best suited to blockchain and distributed ledger technologies (DLTs). One of the unique characteristics of the protocol is that it can take advantage of application-specific chain/graph structures in order to decrease key generation, signing and verification costs as well as signature size. Compared to recent improvements in the field, BPQS outperforms existing hash-based algorithms when a key is reused for reasonable numbers of signatures, while it supports a fallback mechanism to allow for a practically unlimited number of signatures if required. To our knowledge, this is the first signature scheme that can utilise an existing blockchain or graph structure to reduce the signature cost to one OTS, even when we plan to sign many times. This makes existing many-time stateful signature schemes obsolete for blockchain applications.
We provide an open source implementation of the scheme and benchmark it.
Category / Keywords: public-key cryptography / post-quantum cryptography, digital signature, distributed ledger, blockchain, Merkle tree
Original Publication (with minor differences): 2018 IEEE International Conference on Blockchain (Blockchain-2018)
Date: received 2 Jul 2018, last revised 6 Jul 2018
Contact author: chalkiaskostas at gmail com
Available format(s): PDF | BibTeX Citation
Version: 20180707:152503 (All versions of this report)
Short URL: ia.cr/2018/658
[ Cryptology ePrint archive ]