---
OA_place: publisher
OA_type: free access
_id: '22820'
abstract:
- lang: eng
  text: "We introduce a new primitive, called beholder signatures (Full version [14]
    of the paper is available at https://eprint.iacr.org/2025/1900), 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 build on Fischlin’s transformation of a sigma
    protocol to a non-interactive, 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.\r\n\r\nThe primary
    applications of beholder signatures can be found within the blockchain space.
    In particular, we describe how to use them to construct proofs of custody (Feist,
    2021) that do not require ephemeral keys and are non-interactive. We also outline
    applications to data dissemination, data availability, and proofs of replication."
acknowledgement: We used generative AI for grammar, spell checking, and basic editing.
  This research was funded in whole or in part by the Austrian Science Fund (FWF)
  10.55776/F85. This work has been partially funded by the European Research Council
  (ERC) under the European Union’s Horizon 2020 innovation program (grant CRYPTOLAYER-101044770),
  and by the European Research Council under the European Union’s Horizon 2020 innovation
  program (grant PROCONTRA-885666).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Stefan
  full_name: Dziembowski, Stefan
  last_name: Dziembowski
- first_name: Sebastian
  full_name: Faust, Sebastian
  last_name: Faust
- first_name: Paweł
  full_name: Kedzior, Paweł
  last_name: Kedzior
- first_name: Marcin
  full_name: Mielniczuk, Marcin
  last_name: Mielniczuk
- first_name: Susil Kumar
  full_name: Mohanty, Susil Kumar
  last_name: Mohanty
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
citation:
  ama: 'Dziembowski S, Faust S, Kedzior P, Mielniczuk M, Mohanty SK, Pietrzak KZ.
    Beholder signatures. In: <i>46th Annual International Cryptology Conference</i>.
    Vol 16801. Springer; 2026:134-165. doi:<a href="https://doi.org/10.1007/978-3-032-35374-0_5">10.1007/978-3-032-35374-0_5</a>'
  apa: 'Dziembowski, S., Faust, S., Kedzior, P., Mielniczuk, M., Mohanty, S. K., &#38;
    Pietrzak, K. Z. (2026). Beholder signatures. In <i>46th Annual International Cryptology
    Conference</i> (Vol. 16801, pp. 134–165). Santa Barbara, CA, United States: Springer.
    <a href="https://doi.org/10.1007/978-3-032-35374-0_5">https://doi.org/10.1007/978-3-032-35374-0_5</a>'
  chicago: Dziembowski, Stefan, Sebastian Faust, Paweł Kedzior, Marcin Mielniczuk,
    Susil Kumar Mohanty, and Krzysztof Z Pietrzak. “Beholder Signatures.” In <i>46th
    Annual International Cryptology Conference</i>, 16801:134–65. Springer, 2026.
    <a href="https://doi.org/10.1007/978-3-032-35374-0_5">https://doi.org/10.1007/978-3-032-35374-0_5</a>.
  ieee: S. Dziembowski, S. Faust, P. Kedzior, M. Mielniczuk, S. K. Mohanty, and K.
    Z. Pietrzak, “Beholder signatures,” in <i>46th Annual International Cryptology
    Conference</i>, Santa Barbara, CA, United States, 2026, vol. 16801, pp. 134–165.
  ista: 'Dziembowski S, Faust S, Kedzior P, Mielniczuk M, Mohanty SK, Pietrzak KZ.
    2026. Beholder signatures. 46th Annual International Cryptology Conference. CRYPTO:
    International Cryptology Conference, LNCS, vol. 16801, 134–165.'
  mla: Dziembowski, Stefan, et al. “Beholder Signatures.” <i>46th Annual International
    Cryptology Conference</i>, vol. 16801, Springer, 2026, pp. 134–65, doi:<a href="https://doi.org/10.1007/978-3-032-35374-0_5">10.1007/978-3-032-35374-0_5</a>.
  short: S. Dziembowski, S. Faust, P. Kedzior, M. Mielniczuk, S.K. Mohanty, K.Z. Pietrzak,
    in:, 46th Annual International Cryptology Conference, Springer, 2026, pp. 134–165.
conference:
  end_date: 2026-08-20
  location: Santa Barbara, CA, United States
  name: 'CRYPTO: International Cryptology Conference'
  start_date: 2026-08-17
cryptoeprintid: 1
das_tickbox: '0'
date_created: 2026-09-06T22:01:58Z
date_published: 2026-08-11T00:00:00Z
date_updated: 2026-09-10T06:21:13Z
day: '11'
department:
- _id: KrPi
doi: 10.1007/978-3-032-35374-0_5
external_id:
  cryptoeprintid:
  - 2025/1900
fulldoi: https://doi.org/10.1007/978-3-032-35374-0_5
intvolume: '     16801'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1007/978-3-032-35374-0_5
month: '08'
oa: 1
oa_version: Published Version
page: 134-165
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
  grant_number: F8509
  name: Security and Privacy by Design for Complex Systems
publication: 46th Annual International Cryptology Conference
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783032353733'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Beholder signatures
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16801
year: '2026'
...