Quasi-linear size zero knowledge from linear-algebraic PCPs. (English) Zbl 1375.94101
Kushilevitz, Eyal (ed.) et al., Theory of cryptography. 13th international conference, TCC 2016-A, Tel Aviv, Israel, January 10–13, 2016. Proceedings. Part II. Berlin: Springer (ISBN 978-3-662-49098-3/pbk; 978-3-662-49099-0/ebook). Lecture Notes in Computer Science 9563, 33-64 (2016).
Summary: The seminal result that every language having an interactive proof also has a zero-knowledge interactive proof assumes the existence of one-way functions. R. Ostrovsky and A. Wigderson [“One-way functions are essential for non-trivial zero-knowledge”. In: ISTCS 1993 (1993; doi:10.1109/ISTCS.1993.253489)] proved that this assumption is necessary: if one-way functions do not exist, then only languages in BPP have zero-knowledge interactive proofs.{
}
M. Ben-Or et al. [“Multi-prover interactive proofs: how to remove intractability assumptions”. In: STOC 1988 (1988)] proved that, nevertheless, every language having a multi-prover interactive proof also has a zero-knowledge multi-prover interactive proof, unconditionally. Their work led to, among many other things, a line of work studying zero knowledge without intractability assumptions. In this line of work, J. Kilian et al. [Proceedings of the 29th annual ACM symposium on theory of computing, STOC 1997, New York, NY: ACM, 496–505 (1999; Zbl 0963.68192)] defined and constructed zero-knowledge probabilistically checkable proofs (PCPs).{
}
While PCPs with quasilinear-size proof length, but without zero knowledge, are known, no such result is known for zero knowledge PCPs. In this work, we show how to construct “2-round” PCPs that are zero knowledge and of length \(\tilde{O}(K)\) where \(K\) is the number of queries made by a malicious polynomial time verifier. Previous solutions required PCPs of length at least \(K^6\) to maintain zero knowledge. In this model, which we call duplex PCP (DPCP), the verifier first receives an oracle string from the prover, then replies with a message, and then receives another oracle string from the prover; a malicious verifier can make up to \(K\) queries in total to both oracles.{
} Deviating from previous works, our constructions do not invoke the PCP Theorem as a blackbox but instead rely on certain algebraic properties of a specific family of PCPs. We show that if the PCP has a certain linear algebraic structure – which many central constructions can be shown to possess – we can add the zero knowledge property at virtually no cost (up to additive lower order terms) while introducing only minor modifications in the algorithms of the prover and verifier. We believe that our linear-algebraic characterization of PCPs may be of independent interest, as it gives a simplified way to view previous well-studied PCP constructions.
For the entire collection see [Zbl 1331.94003].
For the entire collection see [Zbl 1331.94003].
MSC:
| 94A60 | Cryptography |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
Citations:
Zbl 0963.68192References:
| [1] | Alon, N.: Combinatorial Nullstellensatz. Comb. Probab. Comput. 8, 7–29 (1999) · Zbl 0920.05026 · doi:10.1017/S0963548398003411 |
| [2] | Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. JACM 45, 501–555 (1998) · Zbl 1065.68570 · doi:10.1145/278298.278306 |
| [3] | Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. JACM 45, 70–122 (1998) · Zbl 0903.68076 · doi:10.1145/273865.273901 |
| [4] | Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: STOC 1991 (1991) · doi:10.1145/103418.103428 |
| [5] | Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex. 1, 3–40 (1991) · Zbl 0774.68041 · doi:10.1007/BF01200056 |
| [6] | Babai, L., Moran, S.: Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class. J. Comput. Syst. Sci. 36, 254–276 (1988) · Zbl 0652.03029 · doi:10.1016/0022-0000(88)90028-1 |
| [7] | Bellare, M., Goldreich, O.: On defining proofs of knowledge. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 390–420. Springer, Heidelberg (1993) · Zbl 0823.94016 · doi:10.1007/3-540-48071-4_28 |
| [8] | Ben-Or, M., Goldreich, O., Goldwasser, S., Håstad, J., Kilian, J., Micali, S., Rogaway, P.: Everything provable is provable in zero-knowledge. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 37–56. Springer, Heidelberg (1990) · Zbl 0718.68033 · doi:10.1007/0-387-34799-2_4 |
| [9] | Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A.: Multi-prover interactive proofs: how to remove intractability assumptions. In: STOC 1988 (1988) |
| [10] | Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: Fast reductions from RAMs to delegatable succinct constraint satisfaction problems. In: ITCS 2013 (2013) · Zbl 1361.68088 · doi:10.1145/2422436.2422481 |
| [11] | Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: On the concrete efficiency of probabilistically-checkable proofs. In: STOC 2013 (2013) · Zbl 1293.94054 · doi:10.1145/2488608.2488681 |
| [12] | Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Robust PCPs of proximity, shorter PCPs and applications to coding. In: STOC 2004 (2004) · Zbl 1192.68286 · doi:10.1145/1007352.1007361 |
| [13] | Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Short PCPs verifiable in polylogarithmic time. In: CCC 2005 (2005) · doi:10.1109/CCC.2005.27 |
| [14] | Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput. 36, 889–974 (2006) · Zbl 1118.68071 · doi:10.1137/S0097539705446810 |
| [15] | Ben-Sasson, E., Sudan, M.: Short PCPs with polylog query complexity. SIAM J. Comput. 38, 551–607 (2008) · Zbl 1172.68025 · doi:10.1137/050646445 |
| [16] | Ben-Sasson, E., Viola, E.: Short PCPs with projection queries. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 163–173. Springer, Heidelberg (2014) · Zbl 1410.68135 · doi:10.1007/978-3-662-43948-7_14 |
| [17] | Dinur, I.: The PCP theorem by gap amplification. JACM 54, 12:1–12:44 (2007) · Zbl 1292.68074 · doi:10.1145/1236457.1236459 |
| [18] | Dinur, I., Reingold, O.: Assignment testers: towards a combinatorial proof of the PCP theorem. In: FOCS 2004 (2004) · Zbl 1127.68031 |
| [19] | Dwork, C., Feige, U., Kilian, J., Naor, M., Safra, M.: Low communication 2-prover zero-knowledge proofs for NP. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 215–227. Springer, Heidelberg (1993) · Zbl 0925.68143 · doi:10.1007/3-540-48071-4_15 |
| [20] | Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. In: STOC 1985 (1985) · Zbl 0900.94025 · doi:10.1145/22145.22178 |
| [21] | Goyal, V., Ishai, Y., Mahmoody, M., Sahai, A.: Interactive locking, zero-knowledge PCPs, and unconditional cryptography. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 173–190. Springer, Heidelberg (2010) · Zbl 1280.94063 · doi:10.1007/978-3-642-14623-7_10 |
| [22] | Harsha, P., Sudan, M.: Small PCPs with low query complexity. Comput. Complex. 9, 157–201 (2000) · Zbl 0986.68134 · doi:10.1007/PL00001606 |
| [23] | Impagliazzo, R., Yung, M.: Direct minimum knowledge computations. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 40–51. Springer, Heidelberg (1988) · doi:10.1007/3-540-48184-2_4 |
| [24] | Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge proofs from secure multiparty computation. SIAM J. Comput. 39, 1121–1152 (2009) · Zbl 1192.68239 · doi:10.1137/080725398 |
| [25] | Ishai, Y., Mahmoody, M., Sahai, A.: On efficient zero-knowledge PCPs. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 151–168. Springer, Heidelberg (2012) · Zbl 1304.68056 · doi:10.1007/978-3-642-28914-9_9 |
| [26] | Ishai, Y., Mahmoody, M., Sahai, A., Xiao, D.: On zero-knowledge PCPs: limitations, simplifications, and applications (2015). http://www.cs.virginia.edu/mohammad/files/papers/ZKPCPs-Full.pdf |
| [27] | Kalai, Y.T., Raz, R.: Interactive PCP. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 536–547. Springer, Heidelberg (2008) · Zbl 1155.68504 · doi:10.1007/978-3-540-70583-3_44 |
| [28] | Kilian, J., Petrank, E., Tardos, G.: Probabilistically checkable proofs with zero knowledge. In: STOC 1997 (1997) · Zbl 0963.68192 · doi:10.1145/258533.258643 |
| [29] | Lapidot, D., Shamir, A.: A one-round, two-prover, zero-knowledge protocol for NP. Combinatorica 15, 204–214 (1995) · Zbl 0834.94015 · doi:10.1007/BF01200756 |
| [30] | Lund, C., Fortnow, L., Karloff, H., Noam, N.: Algebraic methods for interactive proof systems. JACM 39, 859–868 (1992) · Zbl 0799.68097 · doi:10.1145/146585.146605 |
| [31] | Mahmoody, M., Xiao, D.: Languages with efficient zero-knowledge PCPs are in SZK. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 297–314. Springer, Heidelberg (2013) · Zbl 1315.94089 · doi:10.1007/978-3-642-36594-2_17 |
| [32] | Mie, T.: Polylogarithmic two-round argument systems. J. Math. Cryptol. 2, 343–363 (2008) · Zbl 1158.94003 |
| [33] | Ostrovsky, R., Wigderson, A.: One-way functions are essential for non-trivial zero-knowledge. In: ISTCS 1993 (1993) · doi:10.1109/ISTCS.1993.253489 |
| [34] | Polishchuk, A., Spielman, D.A.: Nearly-linear size holographic proofs. In: STOC 1994 (1994) · Zbl 1345.68180 · doi:10.1145/195058.195132 |
| [35] | Shamir, A.: IP = PSPACE. JACM 39, 869–877 (1992) · Zbl 0799.68096 · doi:10.1145/146585.146609 |
| [36] | Spielman, D.: Computationally efficient error-correcting codes and holographic proofs. Ph.D. thesis, Massachusetts Institute of Technology (1995) |
| [37] | Szegedy, M.: Many-valued logics and holographic proofs. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 676–686. Springer, Heidelberg (1999) · Zbl 0938.03022 · doi:10.1007/3-540-48523-6_64 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
