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