Riad S. Wahby
Ye Ji
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
- https://github.com/pepper-project/releases/blob/master/ginger-allspice.tar.gz.Google Scholar
- http://people.cs.georgetown.edu/jthaler/code/code.htm.Google Scholar
- http://people.cs.georgetown.edu/jthaler/TRMPcode.htm.Google Scholar
- https://github.com/pepper-project.Google Scholar
- Things that use Curve25519. https://ianix.com/pub/curve25519-deployment.html.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- S. Arora and B. Barak. Computational Complexity: A modern approach. Cambridge University Press, 2009. Google ScholarCross Ref
- 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. Google ScholarDigital Library
- S. Arora and S. Safra. Probabilistic checking of proofs: a new characterization of NP. J. ACM, 45(1):70--122, Jan. 1998. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- L. Babai. Trading group theory for randomness. In STOC, May 1985. Google ScholarDigital Library
- L. Babai, L. Fortnow, L. A. Levin, and M. Szegedy. Checking computations in polylogarithmic time. In STOC, May 1991. Google ScholarDigital Library
- 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.Google Scholar
- M. Backes, D. Fiore, and R. M. Reischuk. Verifiable delegation of computation on outsourced data. In ACM CCS, Nov. 2013. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarCross Ref
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google Scholar
- E. Ben-Sasson, A. Chiesa, E. Tromer, and M. Virza. Scalable zero knowledge via cycles of elliptic curves. In CRYPTO, Aug. 2014. Google ScholarCross Ref
- 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.Google ScholarDigital Library
- E. Ben-Sasson and M. Sudan. Short PCPs with polylog query complexity. SIAM J. on Comp., 38(2):551--607, May 2008. Google ScholarDigital Library
- S. Benabbas, R. Gennaro, and Y. Vahlis. Verifiable delegation of computation over large datasets. In CRYPTO, Aug. 2011. Google ScholarCross Ref
- D. J. Bernstein. Curve25519: new Diffie-Hellman speed records. In PKC, Apr. 2006. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer. Recursive composition and bootstrapping for SNARKs and proof-carrying data. In STOC, 2013. Google ScholarDigital Library
- U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan. A practical automatic polyhedral parallelizer and locality optimizer. In PLDI, June 2008. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- B. Braun. Compiling computations to constraints for verified computation. UT Austin Honors thesis HR-12-10, Dec. 2012.Google Scholar
- B. Braun, A. J. Feldman, Z. Ren, S. Setty, A. J. Blumberg, and M. Walfish. Verifying computations with state. In SOSP, Nov. 2013. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- A. Chiesa, E. Tromer, and M. Virza. Cluster computing in zero knowledge. In EUROCRYPT, Apr. 2015. Google ScholarCross Ref
- P. Clifford and R. Clifford. Simple deterministic wildcard matching. Information Processing Letters, 101(2):53--54, 2007. Google ScholarDigital Library
- G. Cormode, M. Mitzenmacher, and J. Thaler. Practical verified computation with streaming interactive proofs. In ITCS, Jan. 2012. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarDigital Library
- D. Fiore and R. Gennaro. Publicly verifiable delegation of large polynomials and matrix computations, with applications. In ACM CCS, Oct. 2012. Google ScholarDigital Library
- D. Fiore, R. Gennaro, and V. Pastro. Efficiently verifiable computation on encrypted data. In ACM CCS, Nov. 2014. Google ScholarDigital Library
- C. Fournet, M. Kohlweiss, G. Danezis, and Z. Luo. ZQL: A compiler for privacy-preserving data processing. In USENIX Security, Aug. 2013.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- M. Fredrikson and B. Livshits. ZØ: An optimizing distributing zero-knowledge compiler. In USENIX Security, Aug. 2014.Google Scholar
- R. Gennaro, C. Gentry, and B. Parno. Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In CRYPTO, Aug. 2010.Google ScholarDigital Library
- R. Gennaro, C. Gentry, B. Parno, and M. Raykova. Quadratic span programs and succinct NIZKs without PCPs. In EUROCRYPT, 2013. Google ScholarCross Ref
- C. Gentry and D. Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions. In STOC, June 2011. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM J. on Comp., 18(1):186--208, 1989. Google ScholarDigital Library
- B. Hoefflinger. ITRS: The international technology roadmap for semiconductors. In Chips 2020. Springer, 2012. Google ScholarCross Ref
- Y. Ishai, E. Kushilevitz, and R. Ostrovsky. Efficient arguments without short PCPs. In IEEE CCC, June 2007. Google ScholarDigital Library
- A. Kate, G. M. Zaverucha, and I. Goldberg. Constant-size commitments to polynomials and their applications. In ASIACRYPT, Dec. 2010. Google ScholarCross Ref
- J. Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In STOC, May 1992.Google ScholarDigital Library
- D. E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming, chapter 4.6.4. Addison-Wesley, third edition, 1997.Google Scholar
- 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.Google Scholar
- C. Liu, M. Hicks, and E. Shi. Memory trace oblivious program execution. In Computer Security Foundations Symposium (CSF), June 2013. Google ScholarDigital Library
- C. Lund, L. Fortnow, H. J. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. J. ACM, 39(4):859--868, Oct. 1992. Google ScholarDigital Library
- D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay--a secure two-party computation system. In USENIX Security, Aug. 2004.Google ScholarDigital Library
- D. Manolescu, B. Beckman, and B. Livshits. Volta: Developing distributed applications by recompiling. IEEE Software, 2008. Google ScholarDigital Library
- 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.Google Scholar
- S. Micali. Computationally sound proofs. SIAM J. on Comp., 30(4):1253--1298, 2000. Google ScholarDigital Library
- P. L. Montgomery. Speeding the Pollard and elliptic curve methods of factorization. Math. of Computation, 48(177):243--264, Jan. 1987. Google ScholarCross Ref
- A. Naveh and E. Tromer. PhotoProof: Cryptographic image authentication for any set of permissible transformations. In IEEE S&P, May 2016.Google Scholar
- C. Papamanthou, E. Shi, and R. Tamassia. Signatures of correct computation. In IACR TCC, Mar. 2013. Google ScholarDigital Library
- B. Parno, C. Gentry, J. Howell, and M. Raykova. Pinocchio: Nearly practical verifiable computation. In IEEE S&P, May 2013.Google Scholar
- 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.Google ScholarDigital Library
- J. M. Rabaey, A. P. Chandrakasan, and B. Nikolic. Digital integrated circuits, volume 2. Prentice Hall Englewood Cliffs, 2002.Google Scholar
- G. N. Rothblum. Delegating Computation Reliably: Paradigms and Constructions. PhD thesis, Massachusetts Institute of Technology, 2009.Google Scholar
- P. Sasdrich and T. Güneysu. Efficient elliptic-curve cryptography using Curve25519 on reconfigurable devices. In ARC, Apr. 2014. Google ScholarCross Ref
- 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.Google ScholarDigital Library
- S. Setty, A. J. Blumberg, and M. Walfish. Toward practical and unconditional verification of remote computations. In HotOS, May 2011.Google ScholarDigital Library
- 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. Google ScholarDigital Library
- S. Setty, R. McPherson, A. J. Blumberg, and M. Walfish. Making argument systems for outsourced computation practical (sometimes). In NDSS, Feb. 2012.Google Scholar
- 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.Google ScholarDigital Library
- A. Shamir. IP = PSPACE. J. ACM, 39(4):869--877, Oct. 1992. Google ScholarDigital Library
- J. Thaler. Time-optimal interactive proofs for circuit evaluation. In CRYPTO, Aug. 2013. Citations refer to full version: https://arxiv.org/abs/1304.3812.Google ScholarCross Ref
- J. Thaler. A note on the GKR protocol. http://people.seas.harvard.edu/ jthaler/GKRNote.pdf, 2015.Google Scholar
- J. Thaler, M. Roberts, M. Mitzenmacher, and H. Pfister. Verifiable computation with massively parallel interactive proofs. In USENIX HotCloud Workshop, June 2012.Google ScholarDigital Library
- Victor Vu. Personal communication, 2013.Google Scholar
- V. Vu, S. Setty, A. J. Blumberg, and M. Walfish. A hybrid architecture for interactive verifiable computation. In IEEE S&P, May 2013. Google ScholarDigital Library
- R. S. Wahby, M. Howald, S. Garg, abhi shelat, and M. Walfish. Verifiable ASICs. In IEEE S&P, May 2016.Google Scholar
- 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.Google Scholar
- 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. Google ScholarCross Ref
- 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.Google Scholar
- S. Williams. Icarus Verilog. http://iverilog.icarus.com.Google Scholar
- S. Zahur and D. Evans. Circuit structures for improved efficiency of security and privacy tools. In IEEE S&P, pages 493--507, May 2013.Google Scholar
- 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.Google Scholar
Index Terms
- Full Accounting for Verifiable Outsourcing
Recommendations
Efficient Techniques for Publicly Verifiable Delegation of Computation
ASIA CCS '16: Proceedings of the 11th ACM on Asia Conference on Computer and Communications SecurityWith the advent of cloud computing, individuals and companies alike are looking for opportunities to leverage cloud resources not only for storage but also for computation. Nevertheless, the reliance on the cloud to perform computation raises the ...
Lighter is Better: A Lighter Multi-client Verifiable Outsourced Computation with Hybrid Homomorphic Encryption
Computer Security – ESORICS 2022AbstractGordon et al. (TCC 2015) systematically studied the security of Multi-client Verifiable Computation (MVC), in which a set of computationally-weak clients outsource the computation of a general function f over their private inputs to an untrusted ...
Practical and Efficient Attribute-Based Encryption with Constant-Size Ciphertexts in Outsourced Verifiable Computation
ASIA CCS '16: Proceedings of the 11th ACM on Asia Conference on Computer and Communications SecurityIn cloud computing, computationally weak users are always willing to outsource costly computations to a cloud, and at the same time they need to check the correctness of the result provided by the cloud. Such activities motivate the occurrence of ...
Comments