Blockchained Post-Quantum Signatures

Konstantinos Chalkias; James Brown; Mike Hearn; Tommy Lillehagen; Igor Nitto; Thomas Schroeter

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 cryptography digital signature distributed ledger blockchain Merkle tree
Contact author(s): chalkiaskostas @ gmail com
History: 2018-07-07: received
Short URL: https://ia.cr/2018/658
License: 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}
}