Paper 2018/658

Blockchained Post-Quantum Signatures

Konstantinos Chalkias, James Brown, Mike Hearn, Tommy Lillehagen, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. 2018 IEEE International Conference on Blockchain (Blockchain-2018)
Keywords
post-quantum cryptographydigital signaturedistributed ledgerblockchainMerkle tree
Contact author(s)
chalkiaskostas @ gmail com
History
2018-07-07: received
Short URL
https://ia.cr/2018/658
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/658,
      author = {Konstantinos Chalkias and James Brown and Mike Hearn and Tommy Lillehagen and Igor Nitto and Thomas Schroeter},
      title = {Blockchained Post-Quantum Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2018/658},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/658}},
      url = {https://eprint.iacr.org/2018/658}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.