Cryptology ePrint Archive: Report 2021/1265

Special Soundness in the Random Oracle Model

Douglas Wikström

Abstract: We generalize the knowledge extractor for constant-round special sound protocols presented by Wikström (2018) to a knowledge extractor for the corresponding non-interactive Fiat-Shamir proofs in the random oracle model and give an exact analysis of the extraction error and running time.

Relative the interactive case the extraction error is increased by a factor $\ell$ and the running time is increased by a factor $O(\ell)$, where $\ell$ is the number of oracle queries made by the prover.

Through carefully chosen notation and concepts, and a technical lemma, we effectively recast the extraction problem of the notoriously complex non-interactive case to the interactive case. Thus, our approach may be of independent interest.

Category / Keywords: foundations / Fiat-Shamir, random oracle model, witness extraction, knowledge extraction, proof of knowledge, soundness error, knowledge error, exact reduction

Date: received 21 Sep 2021

Contact author: dog at kth se

Available format(s): PDF | BibTeX Citation

Version: 20210922:151247 (All versions of this report)

Short URL: ia.cr/2021/1265


[ Cryptology ePrint archive ]