More Web Proxy on the site http://driver.im/

Article

Non-interactive verifiable computing: outsourcing computation to untrusted workers

Authors:

Rosario Gennaro,

Bryan ParnoAuthors Info & Claims

CRYPTO'10: Proceedings of the 30th annual conference on Advances in cryptology

Pages 465 - 482

Published: 15 August 2010 Publication History

Abstract

We introduce and formalize the notion of Verifiable Computation, which enables a computationally weak client to "outsource" the computation of a function F on various dynamically-chosen inputs x₁, ...,x_k to one or more workers. The workers return the result of the function evaluation, e.g., y_i = F(x_i), as well as a proof that the computation of F was carried out correctly on the given value x_i. The primary constraint is that the verification of the proof should require substantially less computational effort than computing F(_i) from scratch.

We present a protocol that allows the worker to return a computationally-sound, non-interactive proof that can be verified in O(mċpoly(λ)) time, where m is the bit-length of the output of F, and λ is a security parameter. The protocol requires a one-time pre-processing stage by the client which takes O(|C|ċpoly(λ)) time, where C is the smallest known Boolean circuit computing F. Unlike previous work in this area, our scheme also provides (at no additional cost) input and output privacy for the client, meaning that the workers do not learn any information about the x_i or y_i values.

References

[1]

Amazon Elastic Compute Cloud, http://aws.amazon.com/ec2

[2]

The Folding@home project. Stanford University, http://www.stanford.edu/group/pandegroup/cosm/

[3]

Sun Utility Computing, http://www.sun.com/service/sungrid/index.jsp

[4]

The Great Internet Mersenne Prime Search, http://www.mersenne.org/

[5]

Anderson, D.P., Cobb, J., Korpela, E., Lebofsky, M., Werthimer, D.: SETI@Home: An experiment in public-resource computing. Communications of the ACM 45(11), 56-61 (2002).

Digital Library

[6]

Babai, L.: Trading group theory for randomness. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 421-429. ACM, New York (1985).

Digital Library

[7]

Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahay, A., Vadhan, S., Yang, K.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1-18. Springer, Heidelberg (2001).

Digital Library

[8]

Barak, B., Haitner, I., Hofheinz, D., Ishai, Y.: Bounded key-dependent message security. In: Proceedings of EuroCrypt (June 2010).

Digital Library

[9]

Belenkiy, M., Chase, M., Erway, C.C., Jannotti, J., Küpçü, A., Lysyanskaya, A.: Incentivizing outsourced computation. In: Proceedings of the Workshop on Economics of Networked Systems (NetEcon), pp. 85-90. ACM, New York (2008).

Digital Library

[10]

Chaum, D., Pedersen, T.: Wallet databases with observers. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 89-105. Springer, Heidelberg (1993).

Digital Library

[11]

Gennaro, R., Gentry, C., Parno, B.: Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers, http://eprint.iacr.org/2009/547

[12]

Gentry, C.: A fully homomorphic encryption scheme. PhD thesis, Stanford University (2009).

Digital Library

[13]

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the ACM Symposium on the Theory of Computing (STOC) (2009).

Digital Library

[14]

Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: Proceedings of the ACM Symposium on the Theory of Computing (2008).

Digital Library

[15]

Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. SIAM Journal on Computing 18(1), 186-208 (1989).

Digital Library

[16]

Golle, P., Mironov, I.: Uncheatable distributed computations. In: Proceedings of the RSA Conference (2001).

Digital Library

[17]

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).

Digital Library

[18]

Kalai, Y.T., Raz, R.: Probabilistically checkable arguments. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 143-159. Springer, Heidelberg (2009).

Digital Library

[19]

Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: Proceedings of the ACM Symposium on Theory of Computing (STOC) (1992).

Digital Library

[20]

Kilian, J.: Improved efficient arguments (preliminary version). In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 311-324. Springer, Heidelberg (1995).

Digital Library

[21]

Lindell, Y., Pinkas, B.: A proof of Yao's protocol for secure two-party computation. Journal of Cryptology 22(2), 161-188 (2009).

Digital Library

[22]

Micali, S.: CS proofs (extended abstract). In: Proceedings of the IEEE Symposium on Foundations of Computer Science (1994).

Digital Library

[23]

Molnar, D.: The SETI@Home problem. ACM Crossroads, 7.1 (2000).

[24]

Monrose, F., Wyckoff, P., Rubin, A.: Distributed execution with remote audit. In: Proceedings of ISOC Network and Distributed System Security Symposium (NDSS) (February 1999).

[25]

Rothblum, G.: Delegating Computation Reliably: Paradigms and Constructions. PhD thesis, Massachusetts Institute of Technology (2009).

[26]

Rothblum, G., Vadhan, S.: Are PCPs inherent in efficient arguments? In: Proceedings of Computational Complexity (CCC) (2009).

Digital Library

[27]

Smart, N.P., Vercauteren, F.: Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 420-443. Springer, Heidelberg (2010).

Digital Library

[28]

Smith, S., Weingart, S.: Building a high-performance, programmable secure coprocessor. Computer Networks (Special Issue on Computer Network Security) 31, 831-960 (1999).

Digital Library

[29]

Trusted Computing Group. Trusted platform module main specification. Version 1.2, Revision 103 (July 2007).

[30]

van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Proceedings of EuroCrypt (June 2010).

Digital Library

[31]

Yao, A.: Protocols for secure computations. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (1982).

Digital Library

[32]

Yao, A.: How to generate and exchange secrets. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (1986).

Digital Library

[33]

Yee, B.S.: Using Secure Coprocessors. PhD thesis, Carnegie Mellon University (1994).

Cited By

DeStefano ZMa JBonneau JWalfish MWitchel EArpaci-Dusseau ARossbach CKeeton K(2024)NOPE: Strengthening domain authentication with succinct proofsProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695962(673-692)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3694715.3695962
Tzialla IWang JZhu JPanda AWalfish M(2024)Efficient Auditing of Event-driven Web ApplicationsProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3650089(1208-1224)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3650089
Di Crescenzo GKhodjaeva MKrishnan RShur DFernandes EAlcaraz C(2022)Single-Server Delegation of Small-Exponent Exponentiation from Quasilinear-Time Clients and ApplicationsProceedings of the 4th Workshop on CPS & IoT Security and Privacy10.1145/3560826.3563385(15-26)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3560826.3563385
Show More Cited By

Non-interactive verifiable computing: outsourcing computation to untrusted workers
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data layout
2. Security and privacy

Recommendations

Broadcast and verifiable secret sharing: new security models and round optimal constructions
Multi-Client non-interactive verifiable computation
TCC'13: Proceedings of the 10th theory of cryptography conference on Theory of Cryptography

Gennaro et al. (Crypto 2010) introduced the notion of non-interactive verifiable computation, which allows a computationally weak client to outsource the computation of a function f on a series of inputs x⁽¹⁾,... to a more powerful but untrusted server. ...
Secure verifiable non-interactive oblivious transfer protocol using RSA and Bit commitment on distributed environment

In this paper, we have discussed the issues concerning the basic concept and classification of OT (Oblivious Transfer). We have proposed secure verifiable non-interactive oblivious transfer protocols for the exchange of secrets on distributed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CRYPTO'10: Proceedings of the 30th annual conference on Advances in cryptology

August 2010

743 pages

ISBN:3642146228

Editor:
Tal Rabin
IBM T.J. Watson Research Center, Hawthorne, NY

Sponsors

IACR: International Association for Cryptologic Research

In-Cooperation

University of California, Santa Barbara

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 15 August 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

176
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

DeStefano ZMa JBonneau JWalfish MWitchel EArpaci-Dusseau ARossbach CKeeton K(2024)NOPE: Strengthening domain authentication with succinct proofsProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695962(673-692)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3694715.3695962
Tzialla IWang JZhu JPanda AWalfish M(2024)Efficient Auditing of Event-driven Web ApplicationsProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3650089(1208-1224)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3650089
Di Crescenzo GKhodjaeva MKrishnan RShur DFernandes EAlcaraz C(2022)Single-Server Delegation of Small-Exponent Exponentiation from Quasilinear-Time Clients and ApplicationsProceedings of the 4th Workshop on CPS & IoT Security and Privacy10.1145/3560826.3563385(15-26)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3560826.3563385
Wang HZheng DZhao Q(2021)Publicly Verifiable Outsourcing Computation for QR Decomposition Based on BlockchainSecurity and Communication Networks10.1155/2021/66325182021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/6632518
Cevallos AStewart ABaldimtsi FRoughgarden T(2021)A verifiably secure and proportional committee election ruleProceedings of the 3rd ACM Conference on Advances in Financial Technologies10.1145/3479722.3480988(29-42)Online publication date: 26-Sep-2021
https://dl.acm.org/doi/10.1145/3479722.3480988
Yan HJiang NLi KWang YYang G(2021)Collusion-free for Cloud Verification toward the View of Game TheoryACM Transactions on Internet Technology10.1145/342355822:2(1-21)Online publication date: 11-Nov-2021
https://dl.acm.org/doi/10.1145/3423558
Zhang YWang SZhang XDong JMao XLong FWang CZhou DGao MSun GMartínez JDuato JJohn L(2021)PipeZKProceedings of the 48th Annual International Symposium on Computer Architecture10.1109/ISCA52012.2021.00040(416-428)Online publication date: 14-Jun-2021
https://dl.acm.org/doi/10.1109/ISCA52012.2021.00040
Yamane MIwamura K(2020)Secure and Efficient Outsourcing of Matrix Multiplication based on Secret Sharing Scheme using only One Server2020 IEEE 17th Annual Consumer Communications & Networking Conference (CCNC)10.1109/CCNC46108.2020.9045277(1-6)Online publication date: 10-Jan-2020
https://dl.acm.org/doi/10.1109/CCNC46108.2020.9045277
El-Yahyaoui AEl Kettani M(2019)About Fully Homomorphic Encryption Improvement TechniquesInternational Journal of Embedded and Real-Time Communication Systems10.4018/IJERTCS.201907010110:3(1-20)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.4018/IJERTCS.2019070101
Xie DYang HQin JMa J(2019)Privacy-Preserving and Publicly Verifiable Protocol for Outsourcing Polynomials Evaluation to a Malicious CloudInternational Journal of Digital Crime and Forensics10.4018/IJDCF.201910010211:4(14-27)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.4018/IJDCF.2019100102
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents