Paper 2024/1100

Unforgeability of Blind Schnorr in the Limited Concurrency Setting

Abstract

A Blind Signature Scheme (BSS) is a cryptographic primitive that enables a user to obtain a digital signature on a message from a signer without revealing the message itself. The standard security notion against malicious users for a BSS is One-More Unforgeability (OMUF). One of the earliest and most well-studied blind signature schemes is the Schnorr BSS, although recent results show it does not satisfy OMUF. On the other hand, the Schnorr BSS does satisfy the weaker notion of sequential OMUF --- which restricts adversaries to opening signing sessions one at a time --- in the Algebraic Group Model (AGM) + Random Oracle Model (ROM). In light of this result, a natural question arises: does the Schnorr BSS satisfy OMUF with regard to adversaries that open no more than a small number of signing sessions concurrently? This paper serves as a first step towards characterizing the security of the Schnorr BSS in the limited concurrency setting. Specifically, we demonstrate that the Schnorr BSS satisfies OMUF when at most two signing sessions can be open concurrently (in the AGM+ROM). Our argument suggests that it is plausible that the Schnorr BSS satisfies OMUF for up to polylogarithmically many concurrent signing sessions.