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
Journal of Cryptology
Published in: Journal of Cryptology 2/2019

06-02-2019

Non-black-box Simulation in the Fully Concurrent Setting, Revisited

Author: Susumu Kiyoshima

Published in: Journal of Cryptology | Issue 2/2019

Log in

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

search-config
loading …

Abstract

We give a new proof of the existence of \(O(n^{\epsilon })\)-round public-coin concurrent zero-knowledge arguments for \(\mathcal {NP}\), where \(\epsilon >0\) is an arbitrary constant. The security is proven in the plain model under the assumption that collision-resistant hash functions exist. The existence of such concurrent zero-knowledge arguments was previously proven by Goyal (STOC’13) in the plain model under the same assumption. In the proof, we use a new variant of the non-black-box simulation technique of Barak (FOCS’01). An important property of our simulation technique is that the simulator runs in a “straight-line” manner in the fully concurrent setting. Compared with the simulation technique of Goyal, which also has such a property, the analysis of our simulation technique is (arguably) simpler.
previous article Hardness-Preserving Reductions via Cuckoo Hashing
next article From Physical to Stochastic Modeling of a TERO-Based TRNG

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
Footnotes
1
We use “\(\mathrm {ZK}\) protocols” to denote \(\mathrm {ZK}\) proofs and arguments.
 
2
The notion of “straight-line simulation” is, unfortunately, hard to formalize. I this paper, we use it only informally.
 
3
Here, \(n^{\log \log n}\) can be replaced with any super-polynomial function. We use \(n^{\log \log n}\) for concreteness.
 
4
The circularity about the simulator committing to a machine that emulates the simulator itself can be avoided by separating it to the main simulator \(\mathcal {S}\) and an auxiliary simulator \(\mathsf {aux}\text {-}\mathcal {S}\). Roughly speaking, \(\mathsf {aux}\text {-}\mathcal {S}\) takes a code of a machine \(\mathrm {\Pi }\) as input and does simulation by committing to \(\mathrm {\Pi }\); then, \(\mathcal {S}\) invokes \(\mathsf {aux}\text {-}\mathcal {S}\) with input \(\mathrm {\Pi }= \mathsf {aux}\text {-}\mathcal {S}\).
 
5
This assumption is used only in this overview.
 
6
Since the length of the \(\mathsf {WIPOK}\) witnesses is bounded by a fixed polynomial, the sizes of the committed machines do not blow up even when they contain every previously generated \(\mathsf {WIPOK}\) witness.
 
7
When the code of the simulator is committed, the randomness used for generating this commitment is also committed; thus, if a protocol is designed naively, we need a commitment scheme such that the committed value is hidden even when it contains the randomness used for the commitment.
 
8
In fact, every language in \(\mathcal {NEXP}\) is polynomial-time reducible to \(L_{\mathcal {U}}\).
 
9
From the construction of \(\mathcal {S}\) and \(\mathsf {aux}\text {-}\mathcal {S}\), the first prover message of \(\mathsf {WIPOK}\) in \(\mathsf {trans}\) must have been computed with witness \(w_s\) and randomness in \(\rho _1, \ldots , \rho _{\kappa }\).
 
10
From the construction of \(\mathsf {aux}\text {-}\mathcal {S}\), every message in the kth child-block is computed by using randomness in \(\rho _{\mathsf {head}(k)}, \ldots , \rho _{\mathsf {head}(k+1)-1}\).
 
11
The definition of good blocks here is slightly different from that in the technical overview in Sect. 2.2.
 
12
From the construction of \(\mathcal {S}\) and \(\mathsf {aux}\text {-}\mathcal {S}\), the first prover message of \(\mathsf {WIPOK}\) in \(\mathsf {trans}\) must have been computed with witness \(w_s\) and randomness in \(\rho _1, \ldots , \rho _{\kappa }\).
 
13
From the construction of \(\mathsf {aux}\text {-}\mathcal {S}\), every message in the kth child-block is computed by using randomness in \(\rho _{\mathsf {head}(k)}, \ldots , \rho _{\mathsf {head}(k+1)-1}\).
 
Literature
1.
2.
B. Barak, How to go beyond the black-box simulation barrier, in FOCS, pp. 106–115 (2001)
3.
4.
M. Bellare, O. Goldreich, On defining proofs of knowledge, in CRYPTO, pp. 390–420 (1992)
5.
6.
B. Barak, O. Goldreich, S. Goldwasser, Y. Lindell, Resettably-sound zero-knowledge and its applications, in FOCS, pp. 116–125 (2001)
7.
M. Blum, How to prove a theorem so no one else can claim it, in The International Congress of Mathematicians, pp. 1444–1451 (1986)
8.
N. Bitansky, O. Paneth, From the impossibility of obfuscation to a new non-black-box simulation technique, in FOCS, pp. 223–232 (2012)
9.
N. Bitansky, O. Paneth, On the impossibility of approximate obfuscation and applications to resettable cryptography, in STOC, pp. 241–250 (2013)
10.
N. Bitansky, O. Paneth, On non-black-box simulation and the impossibility of approximate obfuscation. SIAM J. Comput 44(5), 1325–1383 (2015)MathSciNetCrossRefMATH
11.
M. Bellare, B.S. Yee, Forward-security in private-key cryptography, in CT-RSA, pp. 1–18 (2003)
12.
R. Canetti, O. Goldreich, S. Goldwasser, S. Micali, Resettable zero-knowledge, in STOC, pp. 235–244 (2000)
13.
R. Canetti, J. Kilian, E. Petrank, A. Rosen, Black-box concurrent zero-knowledge requires (almost) logarithmically many rounds. SIAM J. Comput. 32(1), 1–47 (2002)MathSciNetCrossRefMATH
14.
R. Canetti, H. Lin, O. Paneth, Public-coin concurrent zero-knowledge in the global hash model, in TCC, pp. 80–99 (2013)
15.
K.-M. Chung, H. Lin, R. Pass, Constant-round concurrent zero knowledge from P-certificates, in FOCS, pp. 50–59 (2013)
16.
K.-M. Chung, H. Lin, R. Pass, Constant-round concurrent zero-knowledge from indistinguishability obfuscation, in CRYPTO, pp. 287–307 (2015)
17.
Y. Deng, V. Goyal, A. Sahai, Resolving the simultaneous resettability conjecture and a new non-black-box simulation strategy, in FOCS, pp. 251–260 (2009)
18.
19.
U. Feige, A. Shamir, Witness indistinguishable and witness hiding protocols, in STOC, pp. 416–426 (1990)
20.
V. Goyal, D. Gupta, A. Sahai, Concurrent secure computation via non-black box simulation, in CRYPTO, pp. 23–42 (2015)
21.
22.
S. Goldwasser, S. Micali, and C. Rackoff, The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)MathSciNetCrossRefMATH
23.
O. Goldreich, S. Micali, A. Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 691–729 (1991)MathSciNetCrossRefMATH
24.
V. Goyal, Non-black-box simulation in the fully concurrent setting, in STOC, pp. 221–230 (2013)
25.
J. Htad, R. Impagliazzo, L.A. Levin, M. Luby, A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)MathSciNetCrossRefMATH
26.
J. Kilian, E. Petrank, Concurrent and resettable zero-knowledge in poly-loalgorithm rounds, in STOC, pp. 560–569 (2001)
27.
28.
29.
O. Pandey, M. Prabhakaran, A. Sahai, Obfuscation-based non-black-box simulation and four message concurrent zero knowledge for NP, in TCC, pp. 638–667 (2015)
30.
R. Pass, A. Rosen, New and improved constructions of non-malleable cryptographic protocols, in STOC, pp. 533–542 (2005)
31.
M. Prabhakaran, A. Rosen, A. Sahai, Concurrent zero knowledge with logarithmic round-complexity, in FOCS, pp. 366–375 (2002)
32.
33.
R. Pass, W.-L.D. Tseng, D. Wikstrm, On the composition of public-coin zero-knowledge protocols, in CRYPTO, pp. 160–176 (2009)
34.
R. Richardson, J. Kilian, On the concurrent composition of zero-knowledge proofs, in EUROCRYPT, pp. 415–431 (1999)
Metadata
Title
Non-black-box Simulation in the Fully Concurrent Setting, Revisited
Author
Susumu Kiyoshima
Publication date
06-02-2019
Publisher
Springer US
Published in
Journal of Cryptology / Issue 2/2019
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-018-09309-5

Other articles of this Issue 2/2019

Journal of Cryptology 2/2019 Go to the issue

OriginalPaper

Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting

OriginalPaper

Cryptanalysis of the CLT13 Multilinear Map

OriginalPaper

Automated Analysis of Cryptographic Assumptions in Generic Group Models

OriginalPaper

On Tight Security Proofs for Schnorr Signatures

OriginalPaper

Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials

OriginalPaper

(Efficient) Universally Composable Oblivious Transfer Using a Minimal Number of Stateless Tokens

Premium Partner

    Image Credits