conference paper published yes Stefan Dziembowski author Sebastian Faust author Paweł Kedzior author Marcin Mielniczuk author Susil Kumar Mohanty author Krzysztof Z Pietrzak author 3E04A7AA-F248-11E8-B48F-1D18A9856A870000-0002-9139-1654 KrPi department CRYPTO: International Cryptology Conference Security and Privacy by Design for Complex Systems project 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. The 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. Springer2026Santa Barbara, CA, United States eng 0302-9743 1611-3349 978303235373310.1007/978-3-032-35374-0_5 16801134-165 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> 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. 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> 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. 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. 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>. 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>. 228202026-09-06T22:01:58Z2026-09-10T06:21:13Z