Top

Published in:

2020 | OriginalPaper | Chapter

Statistical ZAP Arguments

Authors : Saikrishna Badrinarayanan, Rex Fernando, Aayush Jain, Dakshita Khurana, Amit Sahai

Published in: Advances in Cryptology – EUROCRYPT 2020

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

Dwork and Naor (FOCS’00) first introduced and constructed two message public coin witness indistinguishable proofs (ZAPs) for NP based on trapdoor permutations. Since then, ZAPs have also been obtained based on the decisional linear assumption on bilinear maps, and indistinguishability obfuscation, and have proven extremely useful in the design of several cryptographic primitives.

However, all known constructions of two-message public coin (or even publicly verifiable) proof systems only guarantee witness indistinguishability against computationally bounded verifiers. In this paper, we construct the first public coin two message witness indistinguishable (WI) arguments for NP with statistical privacy, assuming quasi-polynomial hardness of the learning with errors (LWE) assumption. We also show that the same protocol has a super-polynomial simulator (SPS), which yields the first public-coin SPS statistical zero knowledge argument. Prior to this, there were no known constructions of two-message publicly verifiable WI protocols under lattice assumptions, even satisfying the weaker notion of computational witness indistinguishability.

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

previous chapter Statistical ZAPR Arguments from Bilinear Maps

next chapter Statistical Zaps and New Oblivious Transfer Protocols

Note that this property is satisfied by any \(\varSigma \)-Protocol with a \(1/2-\)special soundness where the bad challenge \(e_{bad}\) can be computed efficiently from the precommitted values \(\{\hat{a}_i\}\), such as Blum’s \(\varSigma \)-protocol.

More formally, if the output of the hash function is \(\ell \) bits long, then even if we rely on sub-exponential assumptions, we cannot hope to have the guessing advantage be smaller than \(2^{-\ell ^\delta }\) for a small positive constant \(\delta <1\).

We note that in our definition, \({\mathcal R} \) does not need to use private state \(\mathsf {state}_{{\mathcal R}, \tau }\) from the commitment phase in order to execute the \(\mathsf {Verify}\) algorithm in the decommitment phase.

Note that \(\mathsf {OT} _2\) also depends on \(\mathsf {OT} _1\). We omit this dependence in our notation for brevity.

Essentially, since \(x \notin L\), if the cheating prover has to succeed, it can either generate a successful response \(z_k\) for verifier’s query bit \(e_k=0\) or \(e_k=1\) and this function determines which bit it is.

Badrinarayanan, S., Garg, S., Ishai, Y., Sahai, A., Wadia, A.: Two-message witness indistinguishability and secure computation in the plain model from new assumptions. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10626, pp. 275–303. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70700-6_10CrossRefMATH

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

Blum, M.: How to prove a theorem so no one else can claim it. In: Proceedings of the International Congress of Mathematicians, Berkeley, CA, pp. 1444–1451 (1986)

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

Brakerski, Z., Döttling, N.: Two-message statistically sender-private OT from LWE. In: Beimel, A., Dziembowski, S. (eds.) TCC 2018. LNCS, vol. 11240, pp. 370–390. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03810-6_14CrossRef

Brassard, G., Crépeau, C., Robert, J.: Information theoretic reductions among disclosure problems. In: FOCS (1986)

Canetti, R., et al.: Fiat-Shamir: from practice to theory. In: STOC (2019)

Chaum, D.: Demonstrating that a public predicate can be satisfied without revealing any information about how. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 195–199. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_13CrossRef

Cramer, R., Damgård, I., Schoenmakers, B.: Proofs of partial knowledge and simplified design of witness hiding protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174–187. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48658-5_19CrossRef

10.

Dwork, C., Naor, M.: Zaps and their applications. In: FOCS (2000)

11.

Dwork, C., Naor, M.: Zaps and their applications. Electronic Colloquium on Computational Complexity (ECCC) (001) (2002)

12.

Dwork, C., Naor, M.: Zaps and their applications. SIAM J. Comput. 36(6), 1513–1543 (2007). https://doi.org/10.1137/S0097539703426817MathSciNetCrossRefMATH

13.

Feige, U., Shamir, A.: Witness indistinguishable and witness hiding protocols. In: STOC (1990)

14.

Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (extended abstract). In: FOCS (1986)

15.

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

16.

Halevi, S., Kalai, Y.T.: Smooth projective hashing and two-message oblivious transfer. J. Cryptol. 25(1), 158–193 (2012). https://doi.org/10.1007/s00145-010-9092-8MathSciNetCrossRefMATH

17.

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

18.

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. LNCS, vol. 10402, pp. 158–189. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_6CrossRefMATH

19.

Kalai, Y.T.: Smooth projective hashing and two-message oblivious transfer. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 78–95. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_5CrossRef

20.

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

21.

Khurana, D., Sahai, A.: Two-message non-malleable commitments from standard sub-exponential assumptions. IACR Cryptology ePrint Archive 2017, 291 (2017). http://eprint.iacr.org/2017/291

22.

Lombardi, A., Vaikuntanathan, V., Wichs, D.: 2-message publicly verifiable WI from (subexponential) LWE. Cryptology ePrint Archive, Report 2019/808 (2019). https://eprint.iacr.org/2019/808

23.

Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: SODA (2001)

24.

Peikert, C., Shiehian, S.: Noninteractive zero knowledge for NP from (plain) learning with errors (2019)

25.

Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: STOC (2014)

Title: Statistical ZAP Arguments
Authors: Saikrishna Badrinarayanan
Rex Fernando
Aayush Jain
Dakshita Khurana
Amit Sahai
Publisher: Springer International Publishing
Book: Advances in Cryptology – EUROCRYPT 2020
Print ISBN: 978-3-030-45726-6

Electronic ISBN: 978-3-030-45727-3

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-45727-3_22

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner