Revisiting Fiat-Shamir NIZKPs and Signatures from Seed-Friendly Sigma Protocols

Andrea Flamini; Federico Pintore; Edoardo Signorini

Paper 2026/2858

Revisiting Fiat-Shamir NIZKPs and Signatures from Seed-Friendly Sigma Protocols

Andrea Flamini

, Hasso Plattner Institute, University of Potsdam

Federico Pintore

, University of Trento

Edoardo Signorini

, European Commission, Joint Research Centre

Abstract

Seed-friendly sigma protocols have a small challenge space, and when compiled into NIZKP, they require parallel repetition to reduce extraction error. Fiat-Shamir proofs obtained from seed-friendly Sigma protocols can be made more compact with fixed-weight parallel repetitions, and seed-tree compression. So far, these have been presented as compression techniques for the proof size, but standard analysis of the extraction property of NIZKP still relies on the Forking Lemma and rewinding. In this work, we show that not only fixed-weight parallel repetition and seed-tree compression improve the compactness of the proofs, but also improve their security. Interestingly, when the prover randomness is generated from a salted seed tree, interacting with a random oracle, the standard Fiat-Shamir compilation is straight-line extractable in the classical random-oracle model, without any additional proof field or proof-of-work. We further show that the Fiat-Shamir NIZKP from seed-friendly Sigma protocols satisfies multi-proof zero knowledge, and that its straight-line extractability does not require the underlying seed-friendly Sigma protocol to have unique responses.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: straight-line extraction Fiat-Shamir fixed-weight post-quantum signatures
Contact author(s): andrea flamini @ hpi de
federico pintore @ unitn it
edoardo @ edoars me
History: 2026-11-13: approved; 2026-11-10: received; See all versions
Short URL: https://ia.cr/2026/2858
License: CC BY

BibTeX

@misc{cryptoeprint:2026/2858,
      author = {Andrea Flamini and Federico Pintore and Edoardo Signorini},
      title = {Revisiting Fiat-Shamir {NIZKPs} and Signatures from Seed-Friendly Sigma Protocols},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2858},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2858}
}