Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Lower Bounds on Anonymous Whistleblowing Kapitel lesen Erstes Kapitel lesen

2023 | OriginalPaper | Buchkapitel

Generalized Special-Sound Interactive Proofs and Their Knowledge Soundness

verfasst von : Thomas Attema, Serge Fehr, Nicolas Resch

Erschienen in: Theory of Cryptography

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Multilinear Schwartz-Zippel Mod N and Lattice-Based Succinct Arguments
Nächstes Kapitel From Polynomial IOP and Commitments to Non-malleable zkSNARKs
Fußnoten
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.
 
Literatur
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)
Metadaten
Titel
Generalized Special-Sound Interactive Proofs and Their Knowledge Soundness
verfasst von
Thomas Attema
Serge Fehr
Nicolas Resch
Copyright-Jahr
2023
Buch
Theory of Cryptography

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

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

Copyright-Jahr: 2023

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

Premium Partner

    Bildnachweise