Skip to main content

2019 | OriginalPaper | Buchkapitel

Designated-Verifier Pseudorandom Generators, and Their Applications

verfasst von : Geoffroy Couteau, Dennis Hofheinz

Erschienen in: Advances in Cryptology – EUROCRYPT 2019

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

We provide a generic construction of non-interactive zero-knowledge (NIZK) schemes. Our construction is a refinement of Dwork and Naor’s (FOCS 2000) implementation of the hidden bits model using verifiable pseudorandom generators (VPRGs). Our refinement simplifies their construction and relaxes the necessary assumptions considerably.
As a result of this conceptual improvement, we obtain interesting new instantiations:
  • A designated-verifier NIZK (with unbounded soundness) based on the computational Diffie-Hellman (CDH) problem. If a pairing is available, this NIZK becomes publicly verifiable. This constitutes the first fully secure CDH-based designated-verifier NIZKs (and more generally, the first fully secure designated-verifier NIZK from a non-generic assumption which does not already imply publicly-verifiable NIZKs), and it answers an open problem recently raised by Kim and Wu (CRYPTO 2018).
  • A NIZK based on the learning with errors (LWE) assumption, and assuming a non-interactive witness-indistinguishable (NIWI) proof system for bounded distance decoding (BDD). This simplifies and improves upon a recent NIZK from LWE that assumes a NIZK for BDD (Rothblum et al., PKC 2019).

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!

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!

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!

Fußnoten
1
In the HBM, there exist unconditionally secure \(\textsf {NIZK}\) proofs [17].
 
2
A formal argument requires a little care in choosing parameters, and in randomizing \(\mathsf {hb} \) with an additional component in the \(\textsf {NIZK}\) common reference string.
 
3
One might wonder why we do not follow another route to obtain VPRGs from NIWI proofs for \(\mathsf {BDD}\). Specifically, [3, 23] construct even verifiable random functions from a NIWI for a (complex) LWE-related language. However, these constructions inherently use disjunctions, and it seems unlikely that the corresponding NIWIs can be reduced to the \(\mathsf {BDD}\) language.
 
4
The actual construction of [37] relies on a new notion of public-key encryption with prover-assisted oblivious ciphertext sampling, but the high level idea is comparable to the \(\mathsf {VPRG}\)-based approach. A side contribution of our construction is that it is conceptually much simpler and straightforward than the construction of [37].
 
5
Since n is the order of \(\mathbb {G}\) and \(\mathbb {G}\) is a group in which CDH is assumed to hold, 2 / n is negligible in the security parameter.
 
6
Strictly speaking, this may not be true, depending on \(G_m\): the LWE parameters may depend on the size of the \(G_{m,i}\), which in turn may depend on \(m\). However, here we implicitly assume that \(m\le 2^\lambda \) and a suitable \(G_m\) (e.g., one in which \(G_{m,i}(s)\) is of the form \(F_s(i)\) for a PRF \(F:\{0,1\} ^\lambda \rightarrow \{0,1\} \)).
 
Literatur
1.
Zurück zum Zitat Abusalah, H.: Generic instantiations of the hidden bits model for non-interactive zero-knowledge proofs for NP. Master’s thesis, RWTH Aachen (2013) Abusalah, H.: Generic instantiations of the hidden bits model for non-interactive zero-knowledge proofs for NP. Master’s thesis, RWTH Aachen (2013)
5.
Zurück zum Zitat 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 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
6.
Zurück zum Zitat Boyle, E., Couteau, G., Gilboa, N., Ishai, Y.: Compressing vector OLE. In: Lie, D., Mannan, M., Backes, M., Wang, X. (eds.) ACM CCS 2018, pp. 896–912. ACM Press, October 2018 Boyle, E., Couteau, G., Gilboa, N., Ishai, Y.: Compressing vector OLE. In: Lie, D., Mannan, M., Backes, M., Wang, X. (eds.) ACM CCS 2018, pp. 896–912. ACM Press, October 2018
12.
Zurück zum Zitat Couteau, G., Hofheinz, D.: Designated-verifier pseudorandom generators, and their applications. Cryptology ePrint Archive (2019) Couteau, G., Hofheinz, D.: Designated-verifier pseudorandom generators, and their applications. Cryptology ePrint Archive (2019)
16.
Zurück zum Zitat Dwork, C., Naor, M.: Zaps and their applications. In: 41st FOCS, pp. 283–293. IEEE Computer Society Press, November 2000 Dwork, C., Naor, M.: Zaps and their applications. In: 41st FOCS, pp. 283–293. IEEE Computer Society Press, November 2000
17.
Zurück zum Zitat Feige, U., Lapidot, D., Shamir, A.: Multiple non-interactive zero knowledge proofs based on a single random string (extended abstract). In: 31st FOCS, pp. 308–317. IEEE Computer Society Press, October 1990 Feige, U., Lapidot, D., Shamir, A.: Multiple non-interactive zero knowledge proofs based on a single random string (extended abstract). In: 31st FOCS, pp. 308–317. IEEE Computer Society Press, October 1990
18.
Zurück zum Zitat Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: 21st ACM STOC, pp. 25–32. ACM Press, May 1989 Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: 21st ACM STOC, pp. 25–32. ACM Press, May 1989
19.
Zurück zum Zitat Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (extended abstract). In: 27th FOCS, pp. 174–187. IEEE Computer Society Press, October 1986 Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (extended abstract). In: 27th FOCS, pp. 174–187. IEEE Computer Society Press, October 1986
20.
Zurück zum Zitat Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)MathSciNetCrossRef Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)MathSciNetCrossRef
22.
Zurück zum Zitat Gorbunov, S., Vaikuntanathan, V., Wichs, D.: Leveled fully homomorphic signatures from standard lattices. In: Servedio, R.A., Rubinfeld, R. (eds.) 47th ACM STOC, pp. 469–477. ACM Press, June 2015 Gorbunov, S., Vaikuntanathan, V., Wichs, D.: Leveled fully homomorphic signatures from standard lattices. In: Servedio, R.A., Rubinfeld, R. (eds.) 47th ACM STOC, pp. 469–477. ACM Press, June 2015
27.
Zurück zum Zitat Katsumata, S., Nishimaki, R., Yamada, S., Yamakawa, T.: Designated verifier/prover and preprocessing NIZKs from Diffie-Hellman assumptions. In: Eurocrypt 2019 (2019) Katsumata, S., Nishimaki, R., Yamada, S., Yamakawa, T.: Designated verifier/prover and preprocessing NIZKs from Diffie-Hellman assumptions. In: Eurocrypt 2019 (2019)
28.
Zurück zum Zitat Kilian, J., Petrank, E.: An efficient noninteractive zero-knowledge proof system for NP with general assumptions. J. Cryptol. 11(1), 1–27 (1998)MathSciNetCrossRef Kilian, J., Petrank, E.: An efficient noninteractive zero-knowledge proof system for NP with general assumptions. J. Cryptol. 11(1), 1–27 (1998)MathSciNetCrossRef
31.
Zurück zum Zitat Oren, Y.: On the cunning power of cheating verifiers: some observations about zero knowledge proofs (extended abstract). In: 28th FOCS, pp. 462–471. IEEE Computer Society Press, October 1987 Oren, Y.: On the cunning power of cheating verifiers: some observations about zero knowledge proofs (extended abstract). In: 28th FOCS, pp. 462–471. IEEE Computer Society Press, October 1987
32.
Zurück zum Zitat Ostrovsky, R., Wigderson, A.: One-way functions are essential for non-trivial zero-knowledge. In: 1993 Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems, pp. 3–17. IEEE (1993) Ostrovsky, R., Wigderson, A.: One-way functions are essential for non-trivial zero-knowledge. In: 1993 Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems, pp. 3–17. IEEE (1993)
35.
Zurück zum Zitat Quach, W., Rothblum, R.D., Wichs, D.: Reusable designated-verifier NIZKs forall NP from CDH. In: Eurocrypt 2019 (2019) Quach, W., Rothblum, R.D., Wichs, D.: Reusable designated-verifier NIZKs forall NP from CDH. In: Eurocrypt 2019 (2019)
36.
Zurück zum Zitat Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 84–93. ACM Press, May 2005 Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 84–93. ACM Press, May 2005
37.
Zurück zum Zitat Rothblum, R.D., Sealfon, A., Sotiraki, K.: Towards non-interactive zero-knowledge for NP from LWE. In: PKC 2019 (2019) Rothblum, R.D., Sealfon, A., Sotiraki, K.: Towards non-interactive zero-knowledge for NP from LWE. In: PKC 2019 (2019)
38.
Zurück zum Zitat Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Shmoys, D.B. (ed.) 46th ACM STOC, pp. 475–484. ACM Press, May/June 2014 Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Shmoys, D.B. (ed.) 46th ACM STOC, pp. 475–484. ACM Press, May/June 2014
39.
Zurück zum Zitat Vadhan, S.P.: An unconditional study of computational zero knowledge. In: 45th FOCS, pp. 176–185. IEEE Computer Society Press, October 2004 Vadhan, S.P.: An unconditional study of computational zero knowledge. In: 45th FOCS, pp. 176–185. IEEE Computer Society Press, October 2004
Metadaten
Titel
Designated-Verifier Pseudorandom Generators, and Their Applications
verfasst von
Geoffroy Couteau
Dennis Hofheinz
Copyright-Jahr
2019
DOI
https://doi.org/10.1007/978-3-030-17656-3_20