nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, Interaction, and Trust

verfasst von : Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni

Erschienen in: Advances in Cryptology – CRYPTO 2020

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We present a transformation from NIZK with inefficient provers in the uniform random string (URS) model to ZAPs (two message witness indistinguishable proofs) with inefficient provers. While such a transformation was known for the case where the prover is efficient, the security proof breaks down if the prover is inefficient. Our transformation is obtained via new applications of Nisan-Wigderson designs, a combinatorial object originally introduced in the derandomization literature.

We observe that our transformation is applicable both in the setting of super-polynomial provers/poly-time adversaries, as well as a new fine-grained setting, where the prover is polynomial time and the verifier/simulator/zero knowledge distinguisher are in a lower complexity class, such as \(\mathsf {NC}^1\). We also present \(\mathsf {NC}^1\)-fine-grained NIZK in the URS model for all of \(\mathsf {NP}\) from the worst-case assumption \(\oplus L/\mathrm {poly}\not \subseteq \mathsf {NC}^1\).

Our techniques yield the following applications:

ZAPs for \(\mathsf {AM}\) from Minicrypt assumptions (with super-polynomial time provers),

\(\mathsf {NC}^1\)-fine-grained ZAPs for \(\mathsf {NP}\) from worst-case assumptions,

Protocols achieving an “offline” notion of NIZK (oNIZK) in the standard (no-CRS) model with uniform soundness in both the super-polynomial setting (from Minicrypt assumptions) and the \(\mathsf {NC}^1\)-fine-grained setting (from worst-case assumptions). The oNIZK notion is sufficient for use in indistinguishability-based proofs.

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 Delegation with Updatable Unambiguous Proofs and PPAD-Hardness

Nächstes Kapitel Spartan: Efficient and General-Purpose zkSNARKs Without Trusted Setup

Throughout this work we make a distinction between common reference string denoted as CRS and uniform random string denoted as URS. URS is sometimes referred to common random string in literature. We write URS to avoid the confusion and overloading.

Note that recent work on transparent or trustless (succinct) proofs, typically assumes existence of a public random oracle. We will only consider (at most) short public random strings in this work.

We understand Minicrypt to be chiefly characterized by the lack of key agreement (KA), and note that one-way permutations (OWP) are separated from KA via the original Impagliazzo and Rudich separation [46] For the same reason, we consider Collision-Resistant Hashing to be in Minicrypt.

Note that this is very different from other fine-grained flavors of zero knowledge such as “knowledge tightness” or “precise zero knowledge” [30, 31, 36, 37, 57] which look for a simulation complexity that is tight to each simulator. Under these notions, if a malicious verifier, V, runs for \(n^{c_V}\) steps, then the interaction with the prover should simulatable with order \(O(n^{c_V})\) steps. These verifier-by-verifier notions, in some sense, recover fine-grained zero knowledge with respect to \(\mathsf {TIME}(n^c)\) for all c simultaneously. In this work, we aren’t concerned with such verifier-by-verifier simulation of malicious poly-time verifiers, but instead what can be achieved if one is only concerned with (very) simple malicious verifiers (in order to minimize assumptions).

We note that the GS protocol is used to prove that \(\mathsf {MA}\) is contained in \(\mathsf {AM}\) (by proving that the set of accepting coins of the verifier is sufficiently large). Recall that \(\mathsf {MA}\) is like \(\mathsf {NP}\) except the verifier can be randomized. It is not difficult to observe that our notion under the above transformation yields proofs for \(\mathsf {MA}\) where witnesses that make the randomized verifier accept w.h.p. are indistinguishable.

Recently, [33] constructed one-way permutations in the fine-grained setting. However, their results cannot be extended in straight-forward manner to construct fine-grained NIZKs and therefore are unlikely to lead to simpler constructions without using other techniques. For more discussion on this, we refer the interested readers to Sect. 1.2.

Specifically, the existence of efficient 1/2-hitting set generators (HSG) against co-nondeterministic uniform algorithms [8].

Ananth, P., Deshpande, A., Kalai, Y.T., Lysyanskaya, A.: Fully homomorphic NIZK and NIWI proofs. Cryptology ePrint Archive, Report 2019/732 (2019). https://eprint.iacr.org/2019/732

Applebaum, B.: Cryptography in Constant Parallel Time. ISC. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-17367-7CrossRefMATH

Applebaum, B., Raykov, P.: On the relationship between statistical zero-knowledge and statistical randomized encodings. In: Robshaw and Katz [63], pp. 449–477

Badrinarayan, S., Fernando, R., Jain, A., Khurana, D., Sahai, A.: Statistical ZAP arguments. Cryptology ePrint Archive, Report 2019/780 (2019). https://eprint.iacr.org/2019/780

Ball, M., Dachman-Soled, D., Kulkarni, M.: New techniques for zero-knowledge: leveraging inefficient provers to reduce assumptions and interaction. Cryptology ePrint Archive, Report 2019/1464 (2019). https://eprint.iacr.org/2019/1464

Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Average-case fine-grained hardness. In: Hatami, H., McKenzie, P., King, V. (eds.) 49th ACM STOC, pp. 483–496. ACM Press, June 2017

Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Proofs of work from worst-case assumptions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part I. LNCS, vol. 10991, pp. 789–819. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_26CrossRef

Barak, B., Ong, S.J., Vadhan, S.: Derandomization in cryptography. SIAM J. Comput. 37(2), 380–400 (2007)MathSciNetCrossRef

Barak, B., Ong, S.J., Vadhan, S.P.: Derandomization in cryptography. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 299–315. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_18CrossRefMATH

10.

Barak, B., Pass, R.: On the possibility of one-message weak zero-knowledge. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 121–132. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_7CrossRefMATH

11.

Beimel, A., Gál, A.: On arithmetic branching programs. J. Comput. Syst. Sci. 59(2), 195–220 (1999)MathSciNetCrossRef

12.

Bellare, M., Fuchsbauer, G., Scafuro, A.: NIZKs with an untrusted CRS: security in the face of parameter subversion. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part II. LNCS, vol. 10032, pp. 777–804. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_26CrossRefMATH

13.

Bellare, M., Micali, S., Ostrovsky, R.: Perfect zero-knowledge in constant rounds. In: 22nd ACM STOC, pp. 482–493. ACM Press, May 1990

14.

Bellare, M., Yung, M.: Certifying permutations: noninteractive zero-knowledge based on any trapdoor permutation. J. Cryptol. 9(3), 149–166 (1996). https://doi.org/10.1007/BF00208000MathSciNetCrossRefMATH

15.

Ben-Or, M., Gutfreund, D.: Trading help for interaction in statistical zero-knowledge proofs. J. Cryptol. 16(2), 95–116 (2003). https://doi.org/10.1007/s00145-002-0113-0MathSciNetCrossRefMATH

16.

Ben-Sasson, E., et al.: Computational integrity with a public random string from quasi-linear PCPs. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part III. LNCS, vol. 10212, pp. 551–579. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_19CrossRef

17.

Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Report 2018/046 (2018). https://eprint.iacr.org/2018/046

18.

Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Scalable zero knowledge with no trusted setup. In: Boldyreva and Micciancio [22], pp. 701–732

19.

Bitansky, N., Lin, H.: One-message zero knowledge and non-malleable commitments. In: Beimel, A., Dziembowski, S. (eds.) TCC 2018, Part I. LNCS, vol. 11239, pp. 209–234. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03807-6_8CrossRef

20.

Bitansky, N., Paneth, O.: ZAPs and non-interactive witness indistinguishability from indistinguishability obfuscation. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 401–427. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46497-7_16CrossRefMATH

21.

Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications (extended abstract). In: 20th ACM STOC, pp. 103–112. ACM Press, May 1988

22.

Boldyreva, A., Micciancio, D. (eds.): CRYPTO 2019, Part III. LNCS, vol. 11694. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8CrossRefMATH

23.

Campanelli, M., Gennaro, R.: Fine-grained secure computation. In: Beimel, A., Dziembowski, S. (eds.) TCC 2018, Part II. LNCS, vol. 11240, pp. 66–97. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03810-6_3 CrossRef

24.

Canetti, R. (ed.): TCC 2008. LNCS, vol. 4948. Springer, Heidelberg (2008)MATH

25.

Canetti, R., Chen, Y., Holmgren, J., Lombardi, A., Rothblum, G.N., Rothblum, R.D., Wichs, D.: Fiat-Shamir: from practice to theory. In: Charikar, M., Cohen, E. (eds.) 51st ACM STOC, pp. 1082–1090. ACM Press, June 2019

26.

Chailloux, A., Ciocan, D.F., Kerenidis, I., Vadhan, S.P.: Interactive and noninteractive zero knowledge are equivalent in the help model. In: Canetti [24], pp. 501–534

27.

Ciocan, D.F., Vadhan, S.: Interactive and noninteractive zero knowledge coincide in the help model. Cryptology ePrint Archive, Report 2007/389 (2007). http://eprint.iacr.org/2007/389

28.

De Santis, A., Micali, S., Persiano, G.: Non-interactive zero-knowledge with preprocessing. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 269–282. Springer, New York (1990). https://doi.org/10.1007/0-387-34799-2_21CrossRef

29.

Degwekar, A., Vaikuntanathan, V., Vasudevan, P.N.: Fine-grained cryptography. In: Robshaw and Katz [63], pp. 533–562

30.

Ding, N., Gu, D.: Precise time and space simulatable zero-knowledge. In: Boyen, X., Chen, X. (eds.) ProvSec 2011. LNCS, vol. 6980, pp. 16–33. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24316-5_4CrossRef

31.

Ding, N., Gu, D.: On constant-round precise zero-knowledge. In: Chim, T.W., Yuen, T.H. (eds.) ICICS 2012. LNCS, vol. 7618, pp. 178–190. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34129-8_16CrossRef

32.

Dwork, C., Naor, M.: Zaps and their applications. SIAM J. Comput. 36(6), 1513–1543 (2007)MathSciNetCrossRef

33.

Egashira, S., Wang, Y., Tanaka, K.: Fine-grained cryptography revisited. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019, Part III. LNCS, vol. 11923, pp. 637–666. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34618-8_22CrossRef

34.

Feige, U., Lapidot, D., Shamir, A.: Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput. 29(1), 1–28 (1999)MathSciNetCrossRef

35.

Feige, U., Shamir, A.: Zero knowledge proofs of knowledge in two rounds. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 526–544. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_46CrossRef

36.

Goldreich, O.: The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press, Cambridge (2001)

37.

Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems. J. ACM (JACM) 38(3), 690–728 (1991)MathSciNetCrossRef

38.

Goldreich, O., Oren, Y.: Definitions and properties of zero-knowledge proof systems. J. Cryptol. 7(1), 1–32 (1994). https://doi.org/10.1007/BF00195207MathSciNetCrossRefMATH

39.

Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)MathSciNetCrossRef

40.

Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: 18th ACM STOC, pp. 59–68. ACM Press, May 1986

41.

Goyal, V., Jain, A., Sahai, A.: Simultaneous amplification: the case of non-interactive zero-knowledge. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part II. LNCS, vol. 11693, pp. 608–637. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_21CrossRef

42.

Groth, J., Ostrovsky, R., Sahai, A.: Non-interactive zaps and new techniques for NIZK. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 97–111. Springer, Heidelberg (2006). https://doi.org/10.1007/11818175_6CrossRef

43.

Groth, J., Ostrovsky, R., Sahai, A.: New techniques for noninteractive zero-knowledge. J. ACM (JACM) 59(3), 11 (2012)MathSciNetCrossRef

44.

Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415–432. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_24CrossRef

45.

Impagliazzo, R.: A personal view of average-case complexity. In: Tenth Annual IEEE Conference on Proceedings of Structure in Complexity Theory, pp. 134–147. IEEE (1995)

46.

Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: 21st ACM STOC, pp. 44–61. ACM Press, May 1989

47.

Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: 41st FOCS, pp. 294–304. IEEE Computer Society Press, November 2000

48.

Ishai, Y., Kushilevitz, E.: Perfect constant-round secure computation via perfect randomizing polynomials. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 244–256. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45465-9_22CrossRef

49.

Itoh, T., Ohta, Y., Shizuya, H.: Language dependent secure bit commitment. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 188–201. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48658-5_20CrossRef

50.

Jain, A., Jin, Z.: Statistical zap arguments from quasi-polynomial LWE. Cryptology ePrint Archive, Report 2019/839 (2019). https://eprint.iacr.org/2019/839

51.

Jain, A., Kalai, Y.T., Khurana, D., Rothblum, R.: Distinguisher-dependent simulation in two rounds and its applications. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part II. LNCS, vol. 10402, pp. 158–189. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_6CrossRefMATH

52.

Kalai, Y.T., Khurana, D., Sahai, A.: Statistical witness indistinguishability (and more) in two messages. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10822, pp. 34–65. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_2CrossRefMATH

53.

Katsumata, S., Nishimaki, R., Yamada, S., Yamakawa, T.: Designated verifier/prover and preprocessing NIZKs from Diffie-Hellman assumptions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019, Part II. LNCS, vol. 11477, pp. 622–651. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_22CrossRef

54.

Kim, S., Wu, D.J.: Multi-theorem preprocessing NIZKs from lattices. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part II. LNCS, vol. 10992, pp. 733–765. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_25CrossRef

55.

Lapidot, D., Shamir, A.: Publicly verifiable non-interactive zero-knowledge proofs. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 353–365. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-38424-3_26CrossRef

56.

LaVigne, R., Lincoln, A., Williams, V.V.: Public-key cryptography in the fine-grained setting. In: Boldyreva and Micciancio [22], pp. 605–635

57.

Micali, S., Pass, R.: Local zero knowledge. In: STOC, pp. 306–315. ACM (2006)

58.

Nisan, N., Wigderson, A.: Hardness vs. randomness (extended abstract). In: 29th FOCS, pp. 2–11. IEEE Computer Society Press, October 1988

59.

Ong, S.J., Vadhan, S.P.: An equivalence between zero knowledge and commitments. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 482–500. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_27. [24]CrossRef

60.

Ostrovsky, R., Wigderson, A.: One-way fuctions are essential for non-trivial zero-knowledge. In: Proceedings of Second Israel Symposium on Theory of Computing Systems, ISTCS 1993, Natanya, Israel, 7–9 June 1993, pp. 3–17 (1993)

61.

Pass, R., Shelat, A.: Unconditional characterizations of non-interactive zero-knowledge. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 118–134. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_8CrossRef

62.

Peikert, C., Shiehian, S.: Noninteractive zero knowledge for NP from (plain) learning with errors. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part I. LNCS, vol. 11692, pp. 89–114. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_4CrossRef

63.

Robshaw, M., Katz, J. (eds.): CRYPTO 2016, Part III. LNCS, vol. 9816. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3CrossRefMATH

64.

Toda, S.: Counting problems computationally equivalent to. SIAM J. Comput. 13, 423–439 (1984)MathSciNetCrossRef

65.

Wu, H., Wang, F.: A survey of noninteractive zero knowledge proof system and its applications (2014). https://doi.org/10.1155/2014/560484

Titel: New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, Interaction, and Trust
verfasst von: Marshall Ball
Dana Dachman-Soled
Mukul Kulkarni
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2020
Print ISBN: 978-3-030-56876-4

Electronic ISBN: 978-3-030-56877-1

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-56877-1_24

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner