A
Menu
February 28, 2022 preprint Open access Aachen paper

Efficient NIZKs and Signatures from Commit-and-Open Protocols in the QROM

arXiv (Cornell University)

DOI: 10.48550/arxiv.2202.13730 Full text (OA) OpenAlex

Abstract

Commit-and-open Sigma-protocols are a popular class of protocols for constructing non-interactive zero-knowledge arguments and digital-signature schemes via the Fiat-Shamir transformation. Instantiated with hash-based commitments, the resulting non-interactive schemes enjoy tight online-extractability in the random oracle model. Online extractability improves the tightness of security proofs for the resulting digital-signature schemes by avoiding lossy rewinding or forking-lemma based extraction. In this work, we prove tight online extractability in the quantum random oracle model (QROM), showing that the construction supports post-quantum security. First, we consider the default case where committing is done by element-wise hashing. In a second part, we extend our result to Merkle-tree based commitments. Our results yield a significant improvement of the provable post-quantum security of the digital-signature scheme Picnic. Our analysis makes use of a recent framework by Chung et al. [arXiv:2010.11658] for analysing quantum algorithms in the QROM using purely classical reasoning. Therefore, our results can to a large extent be understood and verified without prior knowledge of quantum information science.

Authors 4

  1. Jelle Don

    Centrum Wiskunde & Informatica

    Affiliation as printed

    Centrum Wiskunde & Informatica (CWI) , Amsterdam , Netherlands

  2. Serge Fehr Aachen Mathematical Institute

    Leiden University · Centrum Wiskunde & Informatica

    Affiliation as printed

    Centrum Wiskunde & Informatica (CWI) , Amsterdam , Netherlands

    Mathematical Institute , Leiden University , Netherlands

  3. Christian Majenz

    Technical University of Denmark

    Affiliation as printed

    Cyber Security Section , Department of Applied Mathematics and Computer Science , Technical University of Denmark , Kgs. Lyngby , Denmark

  4. Christian Schaffner

    QuSoft · University of Amsterdam

    Affiliation as printed

    Informatics Institute , University of Amsterdam , Amsterdam , Netherlands

    QuSoft , Amsterdam , Netherlands

Cited by 0 stored of 0

No patents citing this paper on Lens.org (checked 2026-10-11).

References 0