Beholder Signatures

Stefan Dziembowski; Sebastian Faust; Paweł Kędzior; Marcin Mielniczuk; Susil Kumar Mohanty; Krzysztof Pietrzak

Paper 2025/1900

Beholder Signatures

Stefan Dziembowski

, University of Warsaw, IDEAS Institute

Sebastian Faust

, TU Darmstadt

Paweł Kędzior

, University of Warsaw

Marcin Mielniczuk

, University of Warsaw

Susil Kumar Mohanty

, University of Warsaw

Krzysztof Pietrzak

, Institute of Science and Technology Austria

Abstract

We introduce a new primitive, called beholder signatures, which, in some sense, are the opposite of blind signatures. In a beholder signature, one signs a commitment to a (potentially very long) message, and the signature attests that the parties participating in the signing process who know the secret key, jointly also know the entire committed message. This guarantee holds even against distributed adversaries that use secure multi-party computation (MPC) to produce the signature. We work in the distributed adversarial model (Dziembowski, Faust, and Lizurej, Crypto'23), where one assumes that it is infeasible to evaluate a large number of hash queries without any of the participating parties learning the input. We propose a construction of beholder signatures in the random oracle model. The starting point of our construction is proofs of complete knowledge, recently proposed by (Kelkar et al. CCS'24), which again build on Fischlin's transformation of a sigma protocol to a noninteractive, straight-line extractable zero-knowledge proof of knowledge. Our scheme is concretely efficient and comes with a proof-of-concept implementation using Schnorr as the underlying sigma protocol. The primary applications of beholder signatures can be found within the blockchain ecosystem. In particular, we describe how to use them to construct proofs of custody (Feist, 2021) that do not require ephemeral keys and are noninteractive. We also outline applications to data dissemination, data availability, and proofs of replication.

Note: Accepted to CRYPTO 2026

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: signatures straight-line extraction signature schemes proofs of knowledge random oracle model
Contact author(s): stefan dziembowski @ crypto edu pl
sebastian faust @ tu-darmstadt de
p kedzior @ mimuw edu pl
m mielniczuk @ uw edu pl
susilmohanty11 @ gmail com
krzpie @ gmail com
History: 2026-05-05: last of 2 revisions; 2025-10-11: received; See all versions
Short URL: https://ia.cr/2025/1900
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1900,
      author = {Stefan Dziembowski and Sebastian Faust and Paweł Kędzior and Marcin Mielniczuk and Susil Kumar Mohanty and Krzysztof Pietrzak},
      title = {Beholder Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1900},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1900}
}