Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Lower Bounds on Anonymous Whistleblowing Read chapter Read first chapter

2023 | OriginalPaper | Chapter

Generalized Special-Sound Interactive Proofs and Their Knowledge Soundness

Authors : Thomas Attema, Serge Fehr, Nicolas Resch

Published in: Theory of Cryptography

Publisher: Springer Nature Switzerland

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

A classic result in the theory of interactive proofs shows that a special-sound \(\varSigma \)-protocol is automatically a proof of knowledge. This result is very useful to have, since the latter property is typically tricky to prove from scratch, while the former is often easy to argue — if it is satisfied. While classic \(\varSigma \)-protocols often are special-sound, this is unfortunately not the case for many recently proposed, highly efficient interactive proofs, at least not in this strict sense. Motivated by this, the original result was recently generalized to k-special-sound \(\varSigma \)-protocols (for arbitrary, polynomially bounded k), and to multi-round versions thereof. This generalization is sufficient to analyze (e.g.) Bulletproofs-like protocols, but is still insufficient for many other examples.
In this work, we push the relaxation of the special soundness property to the extreme, by allowing an arbitrary access structure \(\varGamma \) to specify for which subsets of challenges it is possible to compute a witness, when given correct answers to these challenges (for a fixed first message). Concretely, for any access structure \(\varGamma \), we identify parameters \(t_\varGamma \) and \(\kappa _\varGamma \), and we show that any \(\varGamma \)-special-sound \(\varSigma \)-protocol is a proof of knowledge with knowledge error \(\kappa _\varGamma \) if \(t_\varGamma \) is polynomially bounded. Similarly for multi-round protocols.
We apply our general result to a couple of simple but important example protocols, where we obtain a tight knowledge error as an immediate corollary. Beyond these simple examples, we analyze the FRI protocol. Here, showing the general special soundness notion is non-trivial, but can be done (for a certain range of parameters) by recycling some of the techniques used to argue ordinary soundness of the protocol (as an IOP). Again as a corollary, we then derive that the FRI protocol, as an interactive proof by using a Merkle-tree commitment, has a knowledge extractor with almost optimal knowledge error, with the caveat that the extractor requires (expected) quasi-polynomial time.
Finally, building up on the technique for the parallel repetition of k-special-sound \(\varSigma \)-protocols, we show the same strong parallel repetition result for \(\varGamma \)-special-sound \(\varSigma \)-protocol and its multi-round variant.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Multilinear Schwartz-Zippel Mod N and Lattice-Based Succinct Arguments
next chapter From Polynomial IOP and Commitments to Non-malleable zkSNARKs
Footnotes
1
We point out that, when considering the FRI protocol for an actual hash function (rather than the random oracle), ordinary soundness is meaningless: the existence of an opening of a Merkle commitment with a certain (not too obscure) property holds trivially. Thus, it is crucial to argue knowledge soundness in this case.
 
2
For the constant-round variant, we obtain genuine knowledge-soundness \((1-\delta )^t+O(N/|\mathbb {F}|)\), that is here the knowledge extractor’s expected running time is \(N^{O(1)}\). We also point out that a simple argument can be used to show knowledge soundness \((1-2^\mu \delta )^t + O(N/|\mathbb {F}|)\), where \(\mu \) is the number of rounds; however, this result is only meaningful for fairly extreme parameters.
 
3
See [3] for a proof of this claim.
 
4
In the original version of [3], the restriction was \(|S| < k\). Here, when considering 3-round protocols, this makes no difference, but it does for the multi-round case.
 
5
In the original version of [3], the restriction was \(|S_i| < k_i\), i.e., the sets were not required to be maximal (this makes no difference for \(\mu = 1\), but it does for the multi-round case, where the min is not necessarily attained by maximal sets). However, in an updated version, this was changed to the above (in essence because of a similar issue as discussed below).
 
6
We use this somewhat cumbersome notation as we will later need to denote j-fold Cartesian products of sets, and for this operation we will use the standard notation \(S^j\).
 
7
Observe that this is a concrete instantiation of the idea alluded to in Remark 1: we can either extract a witness to the desired relation, or a solution to a computationally hard problem.
 
8
That is, we explicitly remove repetitions, so B(c) is not interpreted as a multi-set.
 
Literature
1.
Full version of this paper. IACR ePrint 2023/818 (2023)
2.
Attema, T., Cramer, R., Kohl, L.: A compressed \(\Sigma \)-protocol theory for lattices. In: CRYPTO, vol. 12826, pp. 549–579 (2021)
3.
Attema, T., Fehr, S.: Parallel repetition of \((k_1,\dots , k_{\mu })\)-special-sound multi-round interactive proofs. In: CRYPTO, vol. 13507, pp. 415–443 (2022)
4.
Attema, T., Fehr, S., Klooß, M.: Fiat-shamir transformation of multi-round interactive proofs. In: TCC, vol. 13747, pp. 113–142 (2022)
5.
Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Fast reed-solomon interactive oracle proofs of proximity. In: ICALP, vol. 107, pp. 14:1–14:17 (2018)
6.
Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs. In: TCC, vol. 9986, pp. 31–60 (2016)
7.
Bootle, J., Cerulli, A., Chaidos, P., Groth, J., Petit, C.: Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In: EUROCRYPT, vol. 9666, pp. 327–357 (2016)
8.
Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: IEEE (S &P), pp. 315–334 (2018)
9.
Don, J., Fehr, S., Majenz, C., Schaffner, C.: Efficient NIZKs and signatures from commit-and-open protocols in the QROM. In: CRYPTO, vol. 13508, pp. 729–757 (2022)
10.
Don, J., Fehr, S., Majenz, C., Schaffner, C.: Online-extractability in the quantum random-oracle model. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT, vol. 13277, pp. 677–706 (2022)
11.
Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: Kosaraju, S.R., Fellows, M., Wigderson, A., Ellis, J.A. (eds.) STOC, pp. 723–732 (1992)
12.
Micali, S.: CS proofs (extended abstracts). In: FOCS, pp. 436–453 (1994)
13.
14.
Wikström, D.: Special soundness revisited. IACR ePrint 2018/1157 (2018)
15.
Wikström, D.: Special soundness in the random oracle model. IACR ePrint 2021/1265 (2021)
Metadata
Title
Generalized Special-Sound Interactive Proofs and Their Knowledge Soundness
Authors
Thomas Attema
Serge Fehr
Nicolas Resch
Copyright Year
2023
Book
Theory of Cryptography

Print ISBN: 978-3-031-48620-3

Electronic ISBN: 978-3-031-48621-0

Copyright Year: 2023

DOI
https://doi.org/10.1007/978-3-031-48621-0_15

Premium Partner

    Image Credits