A tight parallel repetition theorem for partially simulatable interactive arguments via smooth KL-divergence. (English) Zbl 1524.68039
Micciancio, Daniele (ed.) et al., Advances in cryptology – CRYPTO 2020. 40th annual international cryptology conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 12172, 544-573 (2020).
Summary: Hardness amplification is a central problem in the study of interactive protocols. While “natural” parallel repetition transformation is known to reduce the soundness error of some special cases of interactive arguments: three-message protocols
[M. Bellare et al., FOCS 1997, 374–383 (1997; doi:10.1109/SFCS.1997.646126)]
and public-coin protocols
[J. Håstad et al., Lect. Notes Comput. Sci. 5978, 1–18 (2010; Zbl 1274.94075);
K.-M. Chung and F.-H. Liu, Lect. Notes Comput. Sci. 5978, 19–36 (2010; Zbl 1274.94052);
K.-M. Chung and R. Pass, Lect. Notes Comput. Sci. 9015, 229–246 (2015; Zbl 1379.94034)],
it fails to do so in the general case
[Bellare et al., loc. cit.;
K. Pietrzak and D. Wikström, J. Cryptology 25, No. 1, 116–135 (2012; Zbl 1272.94057)].
The only known round-preserving approach that applies to all interactive arguments is I. Haitner’s random-terminating transformation [SIAM J. Comput. 42, No. 6, 2487–2501 (2013; Zbl 1285.68010)], who showed that the parallel repetition of the transformed protocol reduces the soundness error at a weak exponential rate: if the original \(m\)-round protocol has soundness error \(1-\varepsilon\), then the \(n\)-parallel repetition of its random-terminating variant has soundness error \((1-\varepsilon)^{\varepsilon n{/}m^4}\) (omitting constant factors). Håstad et al. have generalized this result to partially simulatable interactive arguments, showing that the \(n\)-fold repetition of an \(m\)-round \(\delta\)-simulatable argument of soundness error \(1-\varepsilon\) has soundness error \((1-\varepsilon)^{\varepsilon \delta^2 n{/}m^2}\). When applied to random-terminating arguments, the Håstad et al. bound matches that of Haitner.
In this work we prove that parallel repetition of random-terminating arguments reduces the soundness error at a much stronger exponential rate: the soundness error of the \(n\) parallel repetition is \((1-\varepsilon)^{n{/}m}\), only an \(m\) factor from the optimal rate of \((1-\varepsilon)^n\) achievable in public-coin and three-message arguments. The result generalizes to \(\delta\)-simulatable arguments, for which we prove a bound of \((1-\varepsilon)^{\delta n{/}m}\). This is achieved by presenting a tight bound on a relaxed variant of the KL-divergence between the distribution induced by our reduction and its ideal variant, a result whose scope extends beyond parallel repetition proofs. We prove the tightness of the above bound for random-terminating arguments, by presenting a matching protocol.
For the entire collection see [Zbl 1499.94001].
The only known round-preserving approach that applies to all interactive arguments is I. Haitner’s random-terminating transformation [SIAM J. Comput. 42, No. 6, 2487–2501 (2013; Zbl 1285.68010)], who showed that the parallel repetition of the transformed protocol reduces the soundness error at a weak exponential rate: if the original \(m\)-round protocol has soundness error \(1-\varepsilon\), then the \(n\)-parallel repetition of its random-terminating variant has soundness error \((1-\varepsilon)^{\varepsilon n{/}m^4}\) (omitting constant factors). Håstad et al. have generalized this result to partially simulatable interactive arguments, showing that the \(n\)-fold repetition of an \(m\)-round \(\delta\)-simulatable argument of soundness error \(1-\varepsilon\) has soundness error \((1-\varepsilon)^{\varepsilon \delta^2 n{/}m^2}\). When applied to random-terminating arguments, the Håstad et al. bound matches that of Haitner.
In this work we prove that parallel repetition of random-terminating arguments reduces the soundness error at a much stronger exponential rate: the soundness error of the \(n\) parallel repetition is \((1-\varepsilon)^{n{/}m}\), only an \(m\) factor from the optimal rate of \((1-\varepsilon)^n\) achievable in public-coin and three-message arguments. The result generalizes to \(\delta\)-simulatable arguments, for which we prove a bound of \((1-\varepsilon)^{\delta n{/}m}\). This is achieved by presenting a tight bound on a relaxed variant of the KL-divergence between the distribution induced by our reduction and its ideal variant, a result whose scope extends beyond parallel repetition proofs. We prove the tightness of the above bound for random-terminating arguments, by presenting a matching protocol.
For the entire collection see [Zbl 1499.94001].
References:
| [1] | Bellare, M., Impagliazzo, R., Naor, M.: Does parallel repetition lower the error in computationally sound protocols? In: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, Miami Beach, Florida, USA, 19-22 October 1997, pp. 374-383 (1997) |
| [2] | Berman, I., Haitner, I., Tsfadia, E.: A tight parallel repetition theorem for partially simulatable interactive arguments via smooth KL-divergence. Cryptology ePrint Archive, Report 2019/393 (2019). https://eprint.iacr.org/2019/393 · Zbl 1524.68039 |
| [3] | Brakerski, Z.; Vaikuntanathan, V., Efficient fully homomorphic encryption from (standard) LWE, J. ACM, 43, 2, 831-871 (2014) · Zbl 1302.94037 |
| [4] | Canetti, R.; Halevi, S.; Steiner, M.; Kilian, J., Hardness amplification of weakly verifiable puzzles, Theory of Cryptography, 17-33 (2005), Heidelberg: Springer, Heidelberg · Zbl 1079.94538 · doi:10.1007/978-3-540-30576-7_2 |
| [5] | Chung, F.; Lu, L., Connected components in random graphs with given expected degree sequences, Ann. Comb., 6, 125-145 (2002) · Zbl 1009.05124 · doi:10.1007/PL00012580 |
| [6] | Chung, K-M; Liu, F-H; Micciancio, D., Parallel repetition theorems for interactive arguments, Theory of Cryptography, 19-36 (2010), Heidelberg: Springer, Heidelberg · Zbl 1274.94052 · doi:10.1007/978-3-642-11799-2_2 |
| [7] | Chung, K.M., Pass, R.: The randomness complexity of parallel repetition. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 658-667 (2011) · Zbl 1292.68073 |
| [8] | Chung, K-M; Pass, R.; Dodis, Y.; Nielsen, JB, Tight parallel repetition theorems for public-coin arguments Using KL-divergence, Theory of Cryptography, 229-246 (2015), Heidelberg: Springer, Heidelberg · Zbl 1379.94034 · doi:10.1007/978-3-662-46497-7_9 |
| [9] | Damgärd, I.B., Pfitzmann, B.: Sequential iteration arguments and an efficient zero-knowledge argument for NP. In: Annual International Colloquium on Automata, Languages and Programming (ICALP), pp. 772-783 (1998) |
| [10] | Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, 31 May-03 June 2014, pp. 624-633 (2014) · Zbl 1315.91001 |
| [11] | Dodis, Y.; Jain, A.; Moran, T.; Wichs, D.; Cramer, R., Counterexamples to hardness amplification beyond negligible, Theory of Cryptography, 476-493 (2012), Heidelberg: Springer, Heidelberg · Zbl 1304.68072 · doi:10.1007/978-3-642-28914-9_27 |
| [12] | Donsker, MD; Varadhan, SRS, Asymptotic evaluation of certain markov process expectations for large time. IV, Commun. Pure Appl. Math., 36, 2, 183-212 (1983) · Zbl 0512.60068 · doi:10.1002/cpa.3160360204 |
| [13] | Feige, U.: On the success probability of the two provers in one-round proof systems. In: Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, 30 June-3 July 1991, pp. 116-123 (1991) |
| [14] | Feige, U.; Verbitsky, O., Error reduction by parallel repetition - a negative result, Combinatorica, 22, 4, 461-478 (2002) · Zbl 1017.68052 · doi:10.1007/s00493-002-0001-0 |
| [15] | Fortnow, L., Rompel, J., Sipser, M.: Errata for on the power of multi-prover interactive protocols. In: Proceedings: Fifth Annual Structure in Complexity Theory Conference, Universitat Politècnica de Catalunya, Barcelona, Spain, 8-11 July 1990, pp. 318-319 (1990) · Zbl 0938.68824 |
| [16] | Goldreich, O., Modern Cryptography Probabilistic Proofs and Pseudorandomness (1999), Heidelberg: Springer, Heidelberg · Zbl 0907.94002 · doi:10.1007/978-3-662-12521-2 |
| [17] | Haitner, I., A parallel repetition theorem for any interactive argument, SIAM J. Comput., 42, 6, 2487-2501 (2013) · Zbl 1285.68010 · doi:10.1137/100810630 |
| [18] | Håstad, J.; Pass, R.; Wikström, D.; Pietrzak, K.; Micciancio, D., An efficient parallel repetition theorem, Theory of Cryptography, 1-18 (2010), Heidelberg: Springer, Heidelberg · Zbl 1274.94075 · doi:10.1007/978-3-642-11799-2_1 |
| [19] | Holenstein, T., Parallel repetition: simplification and the no-signaling case, Theory Comput., 5, 1, 141-172 (2009) · Zbl 1213.68297 · doi:10.4086/toc.2009.v005a008 |
| [20] | Moshkovitz, D.: Parallel repetition from fortification. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, 18-21 October 2014, pp. 414-423 (2014) |
| [21] | Mulzer, W.: Chernoff bounds (2018). https://page.mi.fu-berlin.de/mulzer/notes/misc/chernoff.pdf |
| [22] | Pass, R.; Venkitasubramaniam, M., A parallel repetition theorem for constant-round Arthur-Merlin proofs, TOCT, 4, 4, 10:1-10:22 (2012) · Zbl 1322.94090 · doi:10.1145/2382559.2382561 |
| [23] | Pietrzak, K.; Wikström, D., Parallel repetition of computationally sound protocols revisited, J. Cryptol., 25, 1, 116-135 (2012) · Zbl 1272.94057 · doi:10.1007/s00145-010-9090-x |
| [24] | Rao, A., Parallel repetition in projection games and a concentration bound, SIAM J. Comput., 40, 6, 1871-1891 (2011) · Zbl 1235.68078 · doi:10.1137/080734042 |
| [25] | Raz, R., A parallel repetition theorem, SIAM J. Comput., 27, 3, 763-803 (1998) · Zbl 0911.68082 · doi:10.1137/S0097539795280895 |
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.
