research-article

Public Access

Full Accounting for Verifiable Outsourcing

Authors:

Andrew J. Blumberg,

Michael Walfish,

Thomas WiesAuthors Info & Claims

CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

Pages 2071 - 2086

https://doi.org/10.1145/3133956.3133984

Published: 30 October 2017 Publication History

Abstract

Systems for verifiable outsourcing incur costs for a prover, a verifier, and precomputation; outsourcing makes sense when the combination of these costs is cheaper than not outsourcing. Yet, when prior works impose quantitative thresholds to analyze whether outsourcing is justified, they generally ignore prover costs. Verifiable ASICs (VA)---in which the prover is a custom chip---is the other way around: its cost calculations ignore precomputation.

This paper describes a new VA system, called Giraffe; charges Giraffe for all three costs; and identifies regimes where outsourcing is worthwhile. Giraffe's base is an interactive proof geared to data-parallel computation. Giraffe makes this protocol asymptotically optimal for the prover and improves the verifier's main bottleneck by almost 3x, both of which are of independent interest. Giraffe also develops a design template that produces hardware designs automatically for a wide range of parameters, introduces hardware primitives molded to the protocol's data flows, and incorporates program analyses that expand applicability. Giraffe wins even when outsourcing several tens of sub-computations, scales to 500x larger computations than prior work, and can profitably outsource parts of programs that are not worthwhile to outsource in full.

Supplemental Material

MP4 File

Download
2672.39 MB

References

[1]

https://github.com/pepper-project/releases/blob/master/ginger-allspice.tar.gz.

[2]

http://people.cs.georgetown.edu/jthaler/code/code.htm.

[3]

http://people.cs.georgetown.edu/jthaler/TRMPcode.htm.

[4]

https://github.com/pepper-project.

[5]

Things that use Curve25519. https://ianix.com/pub/curve25519-deployment.html.

[6]

E. H. Adelson, C. H. Anderson, J. R. Bergen, P. J. Burt, and J. M. Ogden. Pyramid method in image processing. RCA Engineer, 29(6):33--41, Nov. 1984.

[7]

J. B. Almeida, M. Barbosa, E. Bangerter, G. Barthe, S. Krenn, and S. Z. Béguelin. Full proof cryptography: verifiable compilation of efficient zero-knowledge protocols. In ACM CCS, 2012.

[8]

S. Arora and B. Barak. Computational Complexity: A modern approach. Cambridge University Press, 2009.

[9]

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501--555, May 1998.

Digital Library

[10]

S. Arora and S. Safra. Probabilistic checking of proofs: a new characterization of NP. J. ACM, 45(1):70--122, Jan. 1998.

Digital Library

[11]

R. M. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen, and F. Vercauteren. Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman & Hall/CRC, 2005.

Digital Library

[12]

L. Babai. Trading group theory for randomness. In STOC, May 1985.

Digital Library

[13]

L. Babai, L. Fortnow, L. A. Levin, and M. Szegedy. Checking computations in polylogarithmic time. In STOC, May 1991.

Digital Library

[14]

M. Backes, M. Barbosa, D. Fiore, and R. M. Reischuk. ADSNARK: Nearly practical and privacy-preserving proofs on authenticated data. In IEEE S&P, May 2015.

[15]

M. Backes, D. Fiore, and R. M. Reischuk. Verifiable delegation of computation on outsourced data. In ACM CCS, Nov. 2013.

Digital Library

[16]

E. Bangerter, J. Camenisch, S. Krenn, A. Sadeghi, and T. Schneider. Automatic generation of sound zero-knowledge protocols. IACR Cryptology ePrint Archive, 2008. http://eprint.iacr.org/2008/471.

[17]

E. Ben-Sasson, I. Ben-Tov, A. Chiesa, A. Gabizon, D. Genkin, M. Hamilis, E. Pergament, M. Riabzev, M. Silberstein, E. Tromer, and M. Virza. Computational integrity with a public random string from quasi-linear PCPs. In EUROCRYPT, 2017.

[18]

E. Ben-Sasson, A. Chiesa, C. Garman, M. Green, I. Miers, E. Tromer, and M. Virza. Decentralized anonymous payments from Bitcoin. In IEEE S&P, May 2014.

[19]

E. Ben-Sasson, A. Chiesa, D. Genkin, E. Tromer, and M. Virza. SNARKs for C: Verifying program executions succinctly and in zero knowledge. In CRYPTO, Aug. 2013.

[20]

E. Ben-Sasson, A. Chiesa, D. Genkin, E. Tromer, and M. Virza. TinyRAM architecture specification, v0.991. http://www.scipr-lab.org/system/files/TinyRAM-spec-0.991.pdf, 2013.

[21]

E. Ben-Sasson, A. Chiesa, E. Tromer, and M. Virza. Scalable zero knowledge via cycles of elliptic curves. In CRYPTO, Aug. 2014.

[22]

E. Ben-Sasson, A. Chiesa, E. Tromer, and M. Virza. Succinct non-interactive zero knowledge for a von Neumann architecture. In USENIX Security, Aug. 2014.

Digital Library

[23]

E. Ben-Sasson and M. Sudan. Short PCPs with polylog query complexity. SIAM J. on Comp., 38(2):551--607, May 2008.

Digital Library

[24]

S. Benabbas, R. Gennaro, and Y. Vahlis. Verifiable delegation of computation over large datasets. In CRYPTO, Aug. 2011.

[25]

D. J. Bernstein. Curve25519: new Diffie-Hellman speed records. In PKC, Apr. 2006.

Digital Library

[26]

N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In ITCS, Jan. 2012.

Digital Library

[27]

N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer. Recursive composition and bootstrapping for SNARKs and proof-carrying data. In STOC, 2013.

Digital Library

[28]

U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan. A practical automatic polyhedral parallelizer and locality optimizer. In PLDI, June 2008.

Digital Library

[29]

P. Boulet, A. Darte, G. Silber, and F. Vivien. Loop parallelization algorithms: From parallelism extraction to code generation. Parallel Computing, 24(3--4):421--444, 1998.

[30]

G. Brassard, D. Chaum, and C. Crépeau. Minimum disclosure proofs of knowledge. J. of Comp. and Sys. Sciences, 37(2):156--189, Oct. 1988.

Digital Library

[31]

B. Braun. Compiling computations to constraints for verified computation. UT Austin Honors thesis HR-12-10, Dec. 2012.

[32]

B. Braun, A. J. Feldman, Z. Ren, S. Setty, A. J. Blumberg, and M. Walfish. Verifying computations with state. In SOSP, Nov. 2013.

Digital Library

[33]

S. Campanoni, K. Brownell, S. Kanev, T. M. Jones, G.-Y. Wei, and D. Brooks. HELIX-RC: an architecture-compiler co-design for automatic parallelization of irregular programs. In ISCA, June 2014.

Digital Library

[34]

A. Chiesa, E. Tromer, and M. Virza. Cluster computing in zero knowledge. In EUROCRYPT, Apr. 2015.

[35]

P. Clifford and R. Clifford. Simple deterministic wildcard matching. Information Processing Letters, 101(2):53--54, 2007.

Digital Library

[36]

G. Cormode, M. Mitzenmacher, and J. Thaler. Practical verified computation with streaming interactive proofs. In ITCS, Jan. 2012.

Digital Library

[37]

C. Costello, C. Fournet, J. Howell, M. Kohlweiss, B. Kreuter, M. Naehrig, B. Parno, and S. Zahur. Geppetto: Versatile verifiable computation. In IEEE S&P, May 2015.

[38]

G. Danezis, C. Fournet, M. Kohlweiss, and B. Parno. Pinocchio coin: Building zerocoin from a succinct pairing-based proof system. In Workshop on Language Support for Privacy-enhancing Technologies, Nov. 2013.

Digital Library

[39]

A. Delignat-Lavaud, C. Fournet, M. Kohlweiss, and B. Parno. Cinderella: Turning shabby X.509 certificates into elegant anonymous credentials with the magic of verifiable computation. In IEEE S&P, May 2016.

[40]

D. Fiore, C. Fournet, E. Ghosh, M. Kohlweiss, O. Ohrimenko, and B. Parno. Hash first, argue later: Adaptive verifiable computations on outsourced data. In ACM CCS, Oct. 2016.

Digital Library

[41]

D. Fiore and R. Gennaro. Publicly verifiable delegation of large polynomials and matrix computations, with applications. In ACM CCS, Oct. 2012.

Digital Library

[42]

D. Fiore, R. Gennaro, and V. Pastro. Efficiently verifiable computation on encrypted data. In ACM CCS, Nov. 2014.

Digital Library

[43]

C. Fournet, M. Kohlweiss, G. Danezis, and Z. Luo. ZQL: A compiler for privacy-preserving data processing. In USENIX Security, Aug. 2013.

Digital Library

[44]

C. Fournet, G. Le Guernic, and T. Rezk. A security-preserving compiler for distributed programs: From information-flow policies to cryptographic mechanisms. In ACM CCS, 2009.

Digital Library

[45]

M. Fredrikson and B. Livshits. ZØ: An optimizing distributing zero-knowledge compiler. In USENIX Security, Aug. 2014.

[46]

R. Gennaro, C. Gentry, and B. Parno. Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In CRYPTO, Aug. 2010.

Digital Library

[47]

R. Gennaro, C. Gentry, B. Parno, and M. Raykova. Quadratic span programs and succinct NIZKs without PCPs. In EUROCRYPT, 2013.

[48]

C. Gentry and D. Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions. In STOC, June 2011.

Digital Library

[49]

S. Goldwasser, Y. T. Kalai, and G. N. Rothblum. Delegating computation: Interactive proofs for muggles. J. ACM, 62(4):27:1--27:64, Aug. 2015. Prelim version STOC 2008.

Digital Library

[50]

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

Digital Library

[51]

B. Hoefflinger. ITRS: The international technology roadmap for semiconductors. In Chips 2020. Springer, 2012.

[52]

Y. Ishai, E. Kushilevitz, and R. Ostrovsky. Efficient arguments without short PCPs. In IEEE CCC, June 2007.

Digital Library

[53]

A. Kate, G. M. Zaverucha, and I. Goldberg. Constant-size commitments to polynomials and their applications. In ASIACRYPT, Dec. 2010.

[54]

J. Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In STOC, May 1992.

Digital Library

[55]

D. E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming, chapter 4.6.4. Addison-Wesley, third edition, 1997.

[56]

A. E. Kosba, D. Papadopoulos, C. Papamanthou, M. F. Sayed, E. Shi, and N. Triandopoulos. textscTrueSet: Faster verifiable set computations. In USENIX Security, Aug. 2014.

[57]

C. Liu, M. Hicks, and E. Shi. Memory trace oblivious program execution. In Computer Security Foundations Symposium (CSF), June 2013.

Digital Library

[58]

C. Lund, L. Fortnow, H. J. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. J. ACM, 39(4):859--868, Oct. 1992.

Digital Library

[59]

D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay--a secure two-party computation system. In USENIX Security, Aug. 2004.

Digital Library

[60]

D. Manolescu, B. Beckman, and B. Livshits. Volta: Developing distributed applications by recompiling. IEEE Software, 2008.

Digital Library

[61]

S. Meiklejohn, C. C. Erway, A. Küpccü, T. Hinkle, and A. Lysyanskaya. ZKPDL: a language-based system for efficient zero-knowledge proofs and electronic cash. In USENIX Security, 2010.

[62]

S. Micali. Computationally sound proofs. SIAM J. on Comp., 30(4):1253--1298, 2000.

Digital Library

[63]

P. L. Montgomery. Speeding the Pollard and elliptic curve methods of factorization. Math. of Computation, 48(177):243--264, Jan. 1987.

[64]

A. Naveh and E. Tromer. PhotoProof: Cryptographic image authentication for any set of permissible transformations. In IEEE S&P, May 2016.

[65]

C. Papamanthou, E. Shi, and R. Tamassia. Signatures of correct computation. In IACR TCC, Mar. 2013.

Digital Library

[66]

B. Parno, C. Gentry, J. Howell, and M. Raykova. Pinocchio: Nearly practical verifiable computation. In IEEE S&P, May 2013.

[67]

B. Parno, C. Gentry, J. Howell, and M. Raykova. Pinocchio: Nearly practical verifiable computation. In Communications of the smcpitACM, volume 59, pages 103--112, Feb. 2016.

Digital Library

[68]

J. M. Rabaey, A. P. Chandrakasan, and B. Nikolic. Digital integrated circuits, volume 2. Prentice Hall Englewood Cliffs, 2002.

[69]

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

[70]

P. Sasdrich and T. Güneysu. Efficient elliptic-curve cryptography using Curve25519 on reconfigurable devices. In ARC, Apr. 2014.

[71]

P. Sasdrich and T. Güneysu. Implementing Curve25519 for side-channel--protected elliptic curve cryptography. ACM TRETS, 9(1):3:1--3:15, Nov. 2015.

Digital Library

[72]

S. Setty, A. J. Blumberg, and M. Walfish. Toward practical and unconditional verification of remote computations. In HotOS, May 2011.

Digital Library

[73]

S. Setty, B. Braun, V. Vu, A. J. Blumberg, B. Parno, and M. Walfish. Resolving the conflict between generality and plausibility in verified computation. In EuroSys, Apr. 2013.

Digital Library

[74]

S. Setty, R. McPherson, A. J. Blumberg, and M. Walfish. Making argument systems for outsourced computation practical (sometimes). In NDSS, Feb. 2012.

[75]

S. Setty, V. Vu, N. Panpalia, B. Braun, A. J. Blumberg, and M. Walfish. Taking proof-based verified computation a few steps closer to practicality. In USENIX Security, Aug. 2012.

Digital Library

[76]

A. Shamir. IP = PSPACE. J. ACM, 39(4):869--877, Oct. 1992.

Digital Library

[77]

J. Thaler. Time-optimal interactive proofs for circuit evaluation. In CRYPTO, Aug. 2013. Citations refer to full version: https://arxiv.org/abs/1304.3812.

[78]

J. Thaler. A note on the GKR protocol. http://people.seas.harvard.edu/ jthaler/GKRNote.pdf, 2015.

[79]

J. Thaler, M. Roberts, M. Mitzenmacher, and H. Pfister. Verifiable computation with massively parallel interactive proofs. In USENIX HotCloud Workshop, June 2012.

Digital Library

[80]

Victor Vu. Personal communication, 2013.

[81]

V. Vu, S. Setty, A. J. Blumberg, and M. Walfish. A hybrid architecture for interactive verifiable computation. In IEEE S&P, May 2013.

Digital Library

[82]

R. S. Wahby, M. Howald, S. Garg, abhi shelat, and M. Walfish. Verifiable ASICs. In IEEE S&P, May 2016.

[83]

R. S. Wahby, Y. Ji, A. J. Blumberg, abhi shelat, J. Thaler, M. Walfish, and T. Wies. Full accounting for verifiable outsourcing (extended version). Cryptology ePrint Archive, Report 2017/242, 2017.

[84]

R. S. Wahby, S. Setty, Z. Ren, A. J. Blumberg, and M. Walfish. Efficient RAM and control flow in verifiable outsourced computation. In NDSS, Feb. 2015.

[85]

M. Walfish and A. J. Blumberg. Verifying computations without reexecuting them: from theoretical possibility to near practicality. Communications of the smcpitACM, 58(2):74--84, Feb. 2015.

[86]

S. Williams. Icarus Verilog. http://iverilog.icarus.com.

[87]

S. Zahur and D. Evans. Circuit structures for improved efficiency of security and privacy tools. In IEEE S&P, pages 493--507, May 2013.

[88]

Y. Zhang, D. Genkin, J. Katz, D. Papadopoulos, and C. Papamanthou. vSQL: Verifying arbitrary SQL queries over dynamic outsourced databases. In IEEE S&P, May 2017.

Cited By

Liu TZhang ZZhang YHu WZhang Y(2025)Ceno: Non-uniform, Segment and Parallel Zero-Knowledge Virtual MachineJournal of Cryptology10.1007/s00145-024-09533-238:2Online publication date: 22-Jan-2025
https://doi.org/10.1007/s00145-024-09533-2
Pappas CPapadopoulos DLuo BLiao XXu JKirda ELie D(2024)Sparrow: Space-Efficient zkSNARK for Data-Parallel Circuits and Applications to Zero-Knowledge Decision TreesProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690318(3110-3124)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690318
Lee DShin OCha YLee JYun TKim JOh HNicopoulos CLee S(2024)A Hardware-Based Correct Execution Environment Supporting Virtual MemoryIEEE Access10.1109/ACCESS.2024.344350912(114008-114022)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3443509
Show More Cited By

Index Terms

Full Accounting for Verifiable Outsourcing

Recommendations

Verifiable Computation of Large Polynomials
INTRUST 2014: Revised Selected Papers of the 6th International Conference on Trusted Systems - Volume 9473

Due to the proliferation of powerful cloud service, verifiable computation, which makes a computationally weak client perform intensive computations possible through outsourcing tasks to a powerful server, is attracting increasing attention. The ...
Information Technology Outsourcing in Australia

In Australia, popular discussion of the growing market in outsourcing information technology IT has been spurred by decisions of several large companies and the Australian government to outsource IT operations but there has been little academic research ...
Outsourcing IT: A Governance Guide

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

October 2017

2682 pages

ISBN:9781450349468

DOI:10.1145/3133956

General Chair:
Bhavani Thuraisingham
The University of Texas at Dallas, USA
,
Program Chairs:
David Evans
University of Virginia
,
Tal Malkin
Columbia University
,
Dongyan Xu
Purdue University

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 October 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

CCS '17

Sponsor:

SIGSAC

CCS '17: 2017 ACM SIGSAC Conference on Computer and Communications Security

October 30 - November 3, 2017

Texas, Dallas, USA

Acceptance Rates

CCS '17 Paper Acceptance Rate 151 of 836 submissions, 18%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

42
Total Citations
View Citations
1,243
Total Downloads

Downloads (Last 12 months)204
Downloads (Last 6 weeks)39

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu TZhang ZZhang YHu WZhang Y(2025)Ceno: Non-uniform, Segment and Parallel Zero-Knowledge Virtual MachineJournal of Cryptology10.1007/s00145-024-09533-238:2Online publication date: 22-Jan-2025
https://doi.org/10.1007/s00145-024-09533-2
Pappas CPapadopoulos DLuo BLiao XXu JKirda ELie D(2024)Sparrow: Space-Efficient zkSNARK for Data-Parallel Circuits and Applications to Zero-Knowledge Decision TreesProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690318(3110-3124)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690318
Lee DShin OCha YLee JYun TKim JOh HNicopoulos CLee S(2024)A Hardware-Based Correct Execution Environment Supporting Virtual MemoryIEEE Access10.1109/ACCESS.2024.344350912(114008-114022)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3443509
Balbás DFiore DGonzález Vasco MRobissout DSoriente CMeng WJensen CCremers CKirda E(2023)Modular Sumcheck Proofs with Applications to Machine Learning and Image ProcessingProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623160(1437-1451)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623160
Belling ASoleimanian ABégassat OMeng WJensen CCremers CKirda E(2023)Recursion over Public-Coin Interactive Proof Systems; Faster Hash VerificationProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623078(1422-1436)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623078
Sang YLuo NJudson SChaimberg BAntonopoulos TWang XPiskac RShao ZMeng WJensen CCremers CKirda E(2023)Ou: Automating the Parallelization of Zero-Knowledge ProtocolsProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3616621(534-548)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3616621
Duan HXiang LWang XChu PZhou C(2023)A New Zero Knowledge Argument for General Circuits and Its ApplicationIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.328845418(3906-3920)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TIFS.2023.3288454
Liu LWei P(2023)When MPC in the Head Meets VCInformation Security Practice and Experience10.1007/978-981-99-7032-2_30(507-526)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.1007/978-981-99-7032-2_30
Golovnev ALee JSetty SThaler JWahby R(2023)Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CSAdvances in Cryptology – CRYPTO 202310.1007/978-3-031-38545-2_7(193-226)Online publication date: 20-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-38545-2_7
Ozdemir ABrown FWahby R(2022)CirC: Compiler infrastructure for proof systems, software verification, and more2022 IEEE Symposium on Security and Privacy (SP)10.1109/SP46214.2022.9833782(2248-2266)Online publication date: May-2022
https://doi.org/10.1109/SP46214.2022.9833782
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten