Skip to main content
main-content
Top

Hint

Swipe to navigate through the chapters of this book

2017 | OriginalPaper | Chapter

Efficient Rational Proofs for Space Bounded Computations

Authors : Matteo Campanelli, Rosario Gennaro

Published in: Decision and Game Theory for Security

Publisher: Springer International Publishing

share
SHARE

Abstract

We present new protocols for the verification of space bounded polytime computations against a rational adversary. For such computations requiring sublinear space our protocol requires only a verifier running in sublinear-time. We extend our main result in several directions: (i) we present protocols for randomized complexity classes, using a new composition theorem for rational proofs which is of independent interest; (ii) we present lower bounds (i.e. conditional impossibility results) for Rational Proofs for various complexity classes.
Our new protocol is the first rational proof not based on the circuit model of computation, and the first sequentially composable protocols for a well-defined language class.
Footnotes
1
We also point out that in [16] a rational protocol for P, polytime computations, is presented, but for the case of a computationally bounded prover, i.e. a rational argument.
 
2
This is basically the covert adversary model for multiparty computation introduced in [2].
 
3
We point out that the new machine \(M_2\) introduces a small error. For our specific case this error keeps the overall error probability negligible and we can ignore it.
 
4
A common reference string is a string generated by a trusted party to which both the prover and the verifier have access; it is a common assumption in cryptographic literature, e.g. Non-Interactive Zero Knowledge [7].
 
5
Since we only sketch our proof the reader is invited to see details of the proof [15].
 
6
We stress that in this comparison we are interested in protocols with similar efficiency parameters. For example, the work in [3] presents several large complexity classes for which we have rational proofs. However, these protocols require a polynomial verifier and do not obtain a noticeable reward gap.
 
7
The construction in Theorem 5.1 in [4] is shown to be sequentially composable in [8].
 
Literature
1.
go back to reference Anderson, D.P., Cobb, J., Korpela, E., Lebofsky, M., Werthimer, D.: SETI@ home: an experiment in public-resource computing. Commun. ACM 45(11), 56–61 (2002) CrossRef Anderson, D.P., Cobb, J., Korpela, E., Lebofsky, M., Werthimer, D.: SETI@ home: an experiment in public-resource computing. Commun. ACM 45(11), 56–61 (2002) CrossRef
2.
go back to reference Aumann, Y., Lindell, Y.: Security against covert adversaries: efficient protocols for realistic adversaries. J. Cryptology 23(2), 281–343 (2010) MathSciNetCrossRefMATH Aumann, Y., Lindell, Y.: Security against covert adversaries: efficient protocols for realistic adversaries. J. Cryptology 23(2), 281–343 (2010) MathSciNetCrossRefMATH
3.
go back to reference Azar, P.D., Micali, S.: Rational proofs. In: Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, pp. 1017–1028. ACM (2012) Azar, P.D., Micali, S.: Rational proofs. In: Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, pp. 1017–1028. ACM (2012)
4.
go back to reference Azar, P.D., Micali, S.: Super-efficient rational proofs. In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, pp. 29–30. ACM (2013) Azar, P.D., Micali, S.: Super-efficient rational proofs. In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, pp. 29–30. ACM (2013)
5.
go back to reference Babai, L.: Trading group theory for randomness. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp. 421–429. ACM (1985) Babai, L.: Trading group theory for randomness. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp. 421–429. ACM (1985)
6.
go back to reference Belenkiy, M., Chase, M., Christopher Erway, C., Jannotti, J., Küpçü, A., Lysyanskaya, A.: Incentivizing outsourced computation. In: Proceedings of the ACM SIGCOMM 2008 Workshop on Economics of Networked Systems, NetEcon 2008, Seattle, WA, USA, 22 August 2008, pp. 85–90 (2008) Belenkiy, M., Chase, M., Christopher Erway, C., Jannotti, J., Küpçü, A., Lysyanskaya, A.: Incentivizing outsourced computation. In: Proceedings of the ACM SIGCOMM 2008 Workshop on Economics of Networked Systems, NetEcon 2008, Seattle, WA, USA, 22 August 2008, pp. 85–90 (2008)
7.
9.
go back to reference Chen, J., McCauley, S., Singh, S.: Rational proofs with multiple provers. In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pp. 237–248. ACM (2016) Chen, J., McCauley, S., Singh, S.: Rational proofs with multiple provers. In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pp. 237–248. ACM (2016)
10.
go back to reference De Agostino, S., Silvestri, R.: Bounded size dictionary compression: SC \(_k\)-completeness and NC algorithms. Inf. Comput. 180(2), 101–112 (2003) CrossRefMATH De Agostino, S., Silvestri, R.: Bounded size dictionary compression: SC \(_k\)-completeness and NC algorithms. Inf. Comput. 180(2), 101–112 (2003) CrossRefMATH
12.
13.
go back to reference Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626–645. Springer, Heidelberg (2013). doi: 10.​1007/​978-3-642-38348-9_​37 CrossRef Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626–645. Springer, Heidelberg (2013). doi: 10.​1007/​978-3-642-38348-9_​37 CrossRef
14.
go back to reference Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989) MathSciNetCrossRefMATH Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989) MathSciNetCrossRefMATH
15.
go back to reference Guo, S., Hubáček, P., Rosen, A., Vald, M.: Rational arguments: single round delegation with sublinear verification. In: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, pp. 523–540. ACM (2014) Guo, S., Hubáček, P., Rosen, A., Vald, M.: Rational arguments: single round delegation with sublinear verification. In: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, pp. 523–540. ACM (2014)
17.
18.
go back to reference Johnson, D.S.: The np-completeness column: the many limits on approximation. ACM Trans. Algorithms (TALG) 2(3), 473–489 (2006) MathSciNetCrossRef Johnson, D.S.: The np-completeness column: the many limits on approximation. ACM Trans. Algorithms (TALG) 2(3), 473–489 (2006) MathSciNetCrossRef
19.
go back to reference Kalai, Y.T., Raz, R., Rothblum, R.D.: How to delegate computations: the power of no-signaling proofs. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 485–494. ACM (2014) Kalai, Y.T., Raz, R., Rothblum, R.D.: How to delegate computations: the power of no-signaling proofs. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 485–494. ACM (2014)
20.
go back to reference Karp, R.M., Upfal, E., Wigderson, A.: Constructing a perfect matching is in random nc. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp. 22–32. ACM (1985) Karp, R.M., Upfal, E., Wigderson, A.: Constructing a perfect matching is in random nc. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp. 22–32. ACM (1985)
21.
go back to reference Khot, S., Ponnuswami, A.K.: Better inapproximability results for maxclique, chromatic number and min-3lin-deletion. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 226–237. Springer, Heidelberg (2006). doi: 10.​1007/​11786986_​21 CrossRef Khot, S., Ponnuswami, A.K.: Better inapproximability results for maxclique, chromatic number and min-3lin-deletion. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 226–237. Springer, Heidelberg (2006). doi: 10.​1007/​11786986_​21 CrossRef
22.
go back to reference Larson, S.M., Snow, C.D., Shirts, M., Pande, V.S.: Folding@ home and genome@ home: Using distributed computing to tackle previously intractable problems in computational biology. arXiv preprint arXiv:​0901.​0866 (2009) Larson, S.M., Snow, C.D., Shirts, M., Pande, V.S.: Folding@ home and genome@ home: Using distributed computing to tackle previously intractable problems in computational biology. arXiv preprint arXiv:​0901.​0866 (2009)
23.
go back to reference Makarychev, K., Manokaran, R., Sviridenko, M.: Maximum quadratic assignment problem: reduction from maximum label cover and LP-based approximation algorithm. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 594–604. Springer, Heidelberg (2010). doi: 10.​1007/​978-3-642-14165-2_​50 CrossRef Makarychev, K., Manokaran, R., Sviridenko, M.: Maximum quadratic assignment problem: reduction from maximum label cover and LP-based approximation algorithm. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 594–604. Springer, Heidelberg (2010). doi: 10.​1007/​978-3-642-14165-2_​50 CrossRef
25.
go back to reference Papakonstantinou, P.A.: Constructions, lower bounds, and new directions in Cryptography and Computational Complexity. Ph.D. Thesis, University of Toronto (2010) Papakonstantinou, P.A.: Constructions, lower bounds, and new directions in Cryptography and Computational Complexity. Ph.D. Thesis, University of Toronto (2010)
26.
go back to reference Reingold, O., Rothblum, R., Rothblum, G.: Constant-round interactive proofs for delegating computation. In: Proceedings of the Forty-Eighth Annual ACM on Symposium on Theory of Computing. ACM (2016). (page to appear) Reingold, O., Rothblum, R., Rothblum, G.: Constant-round interactive proofs for delegating computation. In: Proceedings of the Forty-Eighth Annual ACM on Symposium on Theory of Computing. ACM (2016). (page to appear)
27.
go back to reference Walfish, M., Blumberg, A.J.: Verifying computations without reexecuting them. Commun. ACM 58(2), 74–84 (2015) CrossRef Walfish, M., Blumberg, A.J.: Verifying computations without reexecuting them. Commun. ACM 58(2), 74–84 (2015) CrossRef
Metadata
Title
Efficient Rational Proofs for Space Bounded Computations
Authors
Matteo Campanelli
Rosario Gennaro
Copyright Year
2017
DOI
https://doi.org/10.1007/978-3-319-68711-7_4

Premium Partner