Paper 2023/1019

The many faces of Schnorr

Victor Shoup, DFINITY
Abstract

Recently, a number of highly optimized threshold signing protocols for Schnorr signatures have been proposed. A key feature of these protocols is that they produce so-called "presignatures" in a "offline" phase (using a relatively heavyweight, high-latency subprotocol), which are then consumed in an "online" phase to generate signatures (using a relatively lightweight, low-latency subprotocol). The idea is to build up a large cache of presignatures in periods of low demand, so as to be able to quickly respond to bursts of signing requests in periods of high demand. Unfortunately, it is well known that using such presignatures naively leads to subexponential attacks. Thus, any protocols based on presignatures must mitigate against these attacks. One such notable protocol is FROST, which provides security even with an unlimited number of presignatures; moreover, assuming unused presignatures are available, signing requests can be processed concurrently with minimal latency. Unfortunately, FROST is not a robust protocol, at least in the asynchronous communication model (arguably the most realistic model for such a protocol). Indeed, a single corrupt party can prevent any signatures from being produced. Recently, a protocol called ROAST was developed to remedy this situation. Unfortunately, ROAST is significantly less efficient that FROST (each signing request runs many instances of FROST concurrently). A more recent protocol is SPRINT, which provides robustness without synchrony assumptions, and actually provides better throughput than FROST. Unfortunately, SPRINT is only secure in very restricted modes of operation. Specifically, to avoid a subexponential attack, only a limited number of presignatures may be produced in advance of signing requests, which somewhat defeats the purpose of presignatures. Our main new result is to show how to securely combine the techniques used in FROST and SPRINT, allowing one to build a threshold Schnorr signing protocol that (i) is secure and robust without synchrony assumptions (like SPRINT), (ii) provides security even with an unlimited number of presignatures, and (assuming unused presignatures are available) signing requests can be processed concurrently with minimal latency (like FROST), (iii) achieves high throughput (like SPRINT), and (iv) achieves optimal resilience. Besides achieving this particular technical result, one of our main goals in this paper is to provide a unifying framework in order to better understand the techniques used in various protocols. To that end, we attempt to isolate and abstract the main ideas of each protocol, stripping away superfluous details, so that these ideas can be more readily combined and implemented in different ways. More specifically, to the extent possible, we try to avoid talking about distributed protocols at all, and rather, we examine the security of the ordinary, non-threshold Schnorr scheme in "enhanced" attack modes that correspond to attacks on various types of threshold signing protocols. Another one of our goals to carry out a security analysis of these enhanced attack modes in the Generic Group Model (GGM), sometimes in conjunction with the Random Oracle Model (ROM). Despite the limitations of these models, we feel that giving security proofs in the GGM or GGM+ROM provides useful insight into the concrete security of the various enhanced attack modes we consider.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
digital signatureSchnorr signaturethreshold cryptographygeneric group model
Contact author(s)
victor @ shoup net
History
2023-10-06: last of 3 revisions
2023-06-30: received
See all versions
Short URL
https://ia.cr/2023/1019
License
Creative Commons Attribution-NonCommercial-NoDerivs
CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2023/1019,
      author = {Victor Shoup},
      title = {The many faces of Schnorr},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1019},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1019}},
      url = {https://eprint.iacr.org/2023/1019}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.