Abstract
We study the problem of verifiable computation (VC) in which a computationally weak client wishes to delegate the computation of a function f on an input x to a computationally strong but untrusted server. We present new general approaches for constructing VC protocols, as well as solving the related problems of program checking and self-correcting. The new approaches reduce the task of verifiable computation to suitable variants of secure multiparty computation (MPC) protocols. In particular, we show how to efficiently convert the secrecy property of MPC protocols into soundness of a VC protocol via the use of a message authentication code (MAC). The new connections allow us to apply results from the area of MPC towards simplifying, unifying, and improving over previous results on VC and related problems.
In particular, we obtain the following concrete applications: (1) The first VC protocols for arithmetic computations which only make a black-box use of the underlying field or ring; (2) a non-interactive VC protocol for boolean circuits in the preprocessing model, conceptually simplifying and improving the online complexity of a recent protocol of Gennaro et al. (Cryptology ePrint Archive: Report 2009/547); (3) NC0 self-correctors for complete languages in the complexity class NC1 and various log-space classes, strengthening previous AC0 correctors of Goldwasser et al. (STOC 2008).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abadi, M., Feigenbaum, J., Kilian, J.: On hiding information from an oracle. In: STOC (1987)
Applebaum, B., Ishai, Y., Kushilevitz, E.: Computationally private randomizing polynomials and their applications. Computional Complexity 15(2), 115–162 (2006)
Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC0. In: SICOMP, vol. 36(4), pp. 845–888 (2006)
Babai, L.: Trading group theory for randomness. In: STOC (1985)
Beaver, D., Feigenbaum, J.: Hiding instances in multioracle queries. In: Choffrut, C., Lengauer, T. (eds.) STACS 1990. LNCS, vol. 415. Springer, Heidelberg (1990)
Beimel, A., Gál, A.: On arithmetic branching programs. JCSS 59(2), 195–220 (1999)
Blum, M., Kannan, S.: Programs that check their work. In: STOC (1989)
Blum, M., Luby, M., Rubinfeld, R.: Program result checking against adaptive programs and in cryptographic settings. In: Distributed Computing and Crypthography: DIMACS Workshop (1990)
Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting programs with applications to numerical problems. In: STOC (1990)
Buntrock, G., Damm, C., Hertrampf, U., Meinel, C.: Structure and importance of logspace-MOD-classes. In: Jantzen, M., Choffrut, C. (eds.) STACS 1991. LNCS, vol. 480. Springer, Heidelberg (1991)
Chung, K.M., Kalai, Y.T., Vadhan, S.: Improved delegation of computation using fully homomorphic encryption (2010) (in submission)
Cramer, R., Fehr, S., Ishai, Y., Kushilevitz, E.: Efficient multi-party computation over rings. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656. Springer, Heidelberg (2003)
Damgård, I., Nielsen, J.: Universally composable efficient multiparty computation from threshold homomorphic encryption. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 247–264. Springer, Heidelberg (2003)
Feigenbaum, J.: Locally random reductions in interactive complexity theory. In: Advances in Computational Complexity Theory. DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 13, pp. 73–98 (1993)
Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: Outsourcing computation to untrusted workers. Cryptology ePrint Archive, Report 2009/547 (2009), http://eprint.iacr.org/
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC (2009)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC, vol. 7 (1987)
Goldwasser, S., Gutfreund, D., Healy, A., Kaufman, T., Rothblum, G.N.: Verifying and decoding in constant depth. In: STOC (2007)
Goldwasser, S., Gutfreund, D., Healy, A., Kaufman, T., Rothblum, G.N.: A (de)constructive approach to program checking. In: STOC (2008)
Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: STOC (2008)
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. In: SICOMP, vol. 18 (1989)
Hohenberger, S., Lysyanskaya, A.: How to securely outsource cryptographic computations. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 264–282. Springer, Heidelberg (2005)
Ishai, Y., Kushilevitz, E.: Randomizing polynomials: A new representation with applications to round-efficient secure computation. In: FOCS (2000)
Ishai, Y., Kushilevitz, E.: Perfect constant-round secure computation via perfect randomizing polynomials. In: ICALP (2002)
Ishai, Y., Prabhakaran, M., Sahai, A.: Secure arithmetic computation with no honest majority. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 294–314. Springer, Heidelberg (2009)
Kalai, Y.T., Raz, R.: Probabilistically checkable arguments. In: Halevi, S. (ed.) Advances in Cryptology - CRYPTO 2009. LNCS, vol. 5677, pp. 143–159. Springer, Heidelberg (2009)
Karchmer, M., Wigderson, A.: On span programs. In: Structure in Complexity Theory Conference (1993)
Lipton, R.J.: New directions in testing. In: Distributed Computing and Cryptography. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 2, pp. 191–202 (1991)
Mahajan, M., Vinay, V.: Determinant: combinatorics, algorithms and complexity. Chicago J. Theoret. Comput. Sci. (5) (1997)
Micali, S.: CS proofs (extended abstracts). In: FOCS (1994)
Rubinfeld, R.: Designing checkers for programs that run in parallel. Algorithmica 15(4), 287–301 (1996)
Yao, A.C.: How to generate and exchange secrets. In: FOCS (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Applebaum, B., Ishai, Y., Kushilevitz, E. (2010). From Secrecy to Soundness: Efficient Verification via Secure Computation. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds) Automata, Languages and Programming. ICALP 2010. Lecture Notes in Computer Science, vol 6198. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14165-2_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-14165-2_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14164-5
Online ISBN: 978-3-642-14165-2
eBook Packages: Computer ScienceComputer Science (R0)