Paper 2023/420

Making Classical (Threshold) Signatures Post-Quantum for Single Use on a Public Ledger

Laurane Marco, École Polytechnique Fédérale de Lausanne
Abdullah Talayhan, École Polytechnique Fédérale de Lausanne
Serge Vaudenay, École Polytechnique Fédérale de Lausanne
Abstract

The Bitcoin architecture heavily relies on the ECDSA signature scheme which is broken by quantum adversaries as the secret key can be computed from the public key in quantum polynomial time. To mitigate this attack, bitcoins can be paid to the hash of a public key (P2PKH). However, the first payment reveals the public key so all bitcoins attached to it must be spent at the same time (i.e. the remaining amount must be transferred to a new wallet). Some problems remain with this approach: the owners are vulnerable against rushing adversaries between the time the signature is made public and the time it is committed to the blockchain. Additionally, there is no equivalent mechanism for threshold signatures. Finally, no formal analysis of P2PKH has been done. In this paper, we formalize the security notion of a digital signature with a hidden public key and we propose and prove the security of a generic transformation that converts a classical signature to a post-quantum one that can be used only once. We compare it with P2PKH. Namely, our proposal relies on pre-image resistance instead of collision resistance as for P2PKH, so allows for shorter hashes. Additionally, we propose the notion of a delay signature to address the problem of the rushing adversary when used with a public ledger and discuss the advantages and disadvantages of our approach. We further extend our results to threshold signatures.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
post-quantum cryptographythreshold signaturesblockchain
Contact author(s)
laurane marco @ epfl ch
abdullah talayhan @ epfl ch
serge vaudenay @ epfl ch
History
2023-03-24: approved
2023-03-23: received
See all versions
Short URL
https://ia.cr/2023/420
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/420,
      author = {Laurane Marco and Abdullah Talayhan and Serge Vaudenay},
      title = {Making Classical (Threshold) Signatures Post-Quantum for Single Use on a Public Ledger},
      howpublished = {Cryptology ePrint Archive, Paper 2023/420},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/420}},
      url = {https://eprint.iacr.org/2023/420}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.