Paper 2022/833

Stronger Security for Non-Interactive Threshold Signatures: BLS and FROST

Mihir Bellare, University of California, San Diego
Stefano Tessaro, University of Washington
Chenzhi Zhu, University of Washington

We give a unified syntax, and a hierarchy of definitions of security of increasing strength, for non-interactive threshold signature schemes. They cover both fully non-interactive schemes (these are ones that have a single-round signing protocol, the canonical example being threshold-BLS) and ones, like FROST, that have a prior round of message-independent pre-processing. The definitions in the upper echelon of our hierarchy ask for security that is well beyond any currently defined, let alone proven to be met by the just-mentioned schemes, yet natural, and important for modern applications like securing digital wallets. We prove that BLS and FROST are better than advertised, meeting some of these stronger definitions. Yet, they fall short of meeting our strongest definition, a gap we fill for FROST via a simple enhancement to the scheme. We also surface subtle differences in the security achieved by variants of FROST.

Available format(s)
Public-key cryptography
Publication info
Signatures Threshold Cryptography
Contact author(s)
mihir @ eng ucsd edu
tessaro @ cs washington edu
zhucz20 @ cs washington edu
2022-06-27: approved
2022-06-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mihir Bellare and Stefano Tessaro and Chenzhi Zhu},
      title = {Stronger Security for Non-Interactive Threshold Signatures: BLS and FROST},
      howpublished = {Cryptology ePrint Archive, Paper 2022/833},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.