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
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
LP Solutions of Vectorial Integer Subset Sums – Cryptanalysis of Galbraith’s Binary Matrix LWE Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Predictable Arguments of Knowledge

verfasst von : Antonio Faonio, Jesper Buus Nielsen, Daniele Venturi

Erschienen in: Public-Key Cryptography – PKC 2017

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

We initiate a formal investigation on the power of predictability for argument of knowledge systems for NP. Specifically, we consider private-coin argument systems where the answer of the prover can be predicted, given the private randomness of the verifier; we call such protocols Predictable Arguments of Knowledge (PAoK).
Our study encompasses a full characterization of PAoK, showing that such arguments can be made extremely laconic, with the prover sending a single bit, and assumed to have only one round (i.e., two messages) of communication without loss of generality.
We additionally explore PAoK satisfying additional properties (including zero-knowledge and the possibility of re-using the same challenge across multiple executions with the prover), present several constructions of PAoK relying on different cryptographic tools, and discuss applications to cryptography.

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 Asymptotically Tight Bounds for Composing ORAM with PIR
Nächstes Kapitel Removing Erasures with Explainable Hash Proof Systems
Fußnoten
1
Similar fine-grained definitions have already been considered in the literature, e.g., for differing-inputs obfuscation [6].
 
2
It is easy to see that generating all the challenges at the same time, independently of the prover’s answers, is without loss of generality.
 
3
This further justifies our interest to arguments (as opposed to proofs) for NP as Goldreich et al. [30] showed that unless the polynomial-time hierarchy collapses there does not exist a laconic proof system for all NP.
 
4
Domain extension for Ext-WE can be obtained by encrypting each bit of a message individually.
 
5
Very recently, Bellare et al. [7] show that assuming sub-exponential one-way functions and sub-exponential indistinguishability obfuscation, differing-input obfuscation for Turing Machines [2] is impossible. While this result adds another negative evidence, it does not apply directly to Ext-WE.
 
6
The connection between Hash Proof Systems and Witness Encryption was already noted by [23].
 
7
Namely, following the terminology in [6], extractability only holds for a specific class of circuit samplers, related to the underlying instance sampler.
 
8
Roughly speaking, a random self-reducible relation is a relation for which average-case hardness implies worst-case hardness.
 
9
This is because the trivial protocol where the prover forwards a witness is not predictable.
 
10
We note that, in the other direction, predictable arguments seem to imply some kind of hash-proof system where “statistical smoothness” is replaced by “computational smoothness.” We leave it as an interesting direction for future research to explore potential applications of such “computationally smooth” hash-proof systems and their connection to trapdoor hash-proof system (see Benhamouda et al. [8]).
 
11
In the description above we let \({\textsf {Resp}}\) output also all previous answers \(a_1,\ldots ,a_{i-1}\); while this is not necessary it can be assumed w.l.o.g. and will simplify the proof of Theorem 1.
 
12
This model is sometimes also known as the Uniform Random String (URS) model.
 
13
This is necessary, as otherwise a malicious prover could query both (x, 0) and (x, 1), for \(x\not \in L\), and succeed with probability 1.
 
14
On a high level, the difference is that functional signatures allow to generate punctured signature keys, whereas our signature scheme allows to puncture the message space.
 
Literatur
1.
Abusalah, H., Fuchsbauer, G., Pietrzak, K.: Offline witness encryption. IACR Cryptology ePrint Archive, 2015:838 (2015)
2.
Ananth, P., Boneh, D., Garg, S., Sahai, A., Zhandry, M.: Differing-inputs obfuscation and applications. IACR Cryptology ePrint Archive, 2013:689 (2013)
3.
Angluin, D., Lichtenstein, D.: Provable security of cryptosystems: a survey. Technical report TR-288, Yale University, October 1983
4.
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (im)possibility of obfuscating programs. J. ACM 59(2), 6 (2012)MathSciNetCrossRefMATH
5.
Bellare, M., Impagliazzo, R., Naor, M.: Does parallel repetition lower the error in computationally sound protocols? In: FOCS, pp. 374–383 (1997)
6.
Bellare, M., Stepanovs, I., Tessaro, S.: Poly-many hardcore bits for any one-way function and a framework for differing-inputs obfuscation. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 102–121. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-45608-8_​6
7.
Bellare, M., Stepanovs, I., Waters, B.: New negative results on differing-inputs obfuscation. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 792–821. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49896-5_​28 CrossRef
8.
Benhamouda, F., Blazy, O., Chevalier, C., Pointcheval, D., Vergnaud, D.: New techniques for SPHFs and efficient one-round PAKE protocols. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 449–475. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40041-4_​25 CrossRef
9.
10.
11.
12.
13.
14.
15.
Chung, K.-M., Pass, R.: Tight parallel repetition theorems for public-coin arguments using KL-divergence. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 229–246. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46497-7_​9 CrossRef
16.
Derler, D., Slamanig, D.: Practical witness encryption for algebraic languages and how to reply an unknown whistleblower. IACR Cryptology ePrint Archive, 2015:1073 (2015)
17.
18.
Dziembowski, S., Pietrzak, K., Wichs, D.: Non-malleable codes, pp. 434–452. In: Innovations in Computer Science (2010)
19.
Faonio, A., Nielsen, J.B.: Fully leakage-resilient codes. IACR Cryptology ePrint Archive, 2015:1151 (2015)
20.
Faonio, A., Nielsen, J.B., Venturi, D. Mind your coins: fully leakage-resilient signatures with graceful degradation. In: ICALP, pp. 456–468 (2015)
21.
22.
Faust, S., Mukherjee, P., Nielsen, J.B., Venturi, D.: A tamper and leakage resilient von Neumann architecture. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 579–603. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46447-2_​26
23.
Garg, S., Gentry, C., Halevi, S., Wichs, D.: On the implausibility of differing-inputs obfuscation and extractable witness encryption with auxiliary input. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 518–535. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44371-2_​29 CrossRef
24.
Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications. In: STOC, pp. 467–476 (2013)
25.
26.
Goldreich, O.: The Foundations of Cryptography, Basic Techniques, vol. 1. Cambridge University Press, Cambridge (2001)CrossRefMATH
27.
Goldreich, O., Håstad, J.: On the complexity of interactive proofs with bounded communication. Inf. Process. Lett. 67(4), 205–214 (1998)MathSciNetCrossRefMATH
28.
Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: STOC, pp. 25–32 (1989)
29.
30.
Goldreich, O., Vadhan, S.P., Wigderson, A.: On interactive proofs with a laconic prover. Comput. Complex. 11(1–2), 1–53 (2002)MathSciNetCrossRefMATH
31.
Goldwasser, S., Kalai, Y.T., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: How to run turing machines on encrypted data. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 536–553. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40084-1_​30 CrossRef
32.
33.
34.
35.
Malkin, T., Teranishi, I., Vahlis, Y., Yung, M.: Signatures resilient to continual leakage on memory and computation. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 89–106. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-19571-6_​7 CrossRef
36.
Nielsen, J.B., Venturi, D., Zottarel, A.: On the connection between leakage tolerance and adaptive security. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 497–515. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-36362-7_​30 CrossRef
37.
Okamoto, T., Ohta, K.: Divertible zero knowledge interactive proofs and commutative random self-reducibility. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 134–149. Springer, Heidelberg (1990). doi:10.​1007/​3-540-46885-4_​16
38.
Pass, R., Venkitasubramaniam, M.: An efficient parallel repetition theorem for Arthur-Merlin games. In: STOC, pp. 420–429 (2007)
39.
Pietrzak, K., Wikström, D.: Parallel repetition of computationally sound protocols revisited. J. Cryptol. 25(1), 116–135 (2012)MathSciNetCrossRefMATH
40.
Tompa, M., Woll, H.: Random self-reducibility and zero knowledge interactive proofs of possession of information. In: FOCS, pp. 472–482 (1987)
41.
42.
43.
Metadaten
Titel
Predictable Arguments of Knowledge
verfasst von
Antonio Faonio
Jesper Buus Nielsen
Daniele Venturi
Copyright-Jahr
2017
Verlag
Springer Berlin Heidelberg
Buch
Public-Key Cryptography – PKC 2017

Print ISBN: 978-3-662-54364-1

Electronic ISBN: 978-3-662-54365-8

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-662-54365-8_6

Premium Partner

    Bildnachweise