Primitives towards verifiable computation: a survey

Abstract

Verifiable computation (VC) paradigm has got the captivation that in real term is highlighted by the concept of third party computation. In more explicate terms, VC allows resource constrained clients/organizations to securely outsource expensive computations to untrusted service providers, while acquiring the publicly or privately verifiable results. Many mainstream solutions have been proposed to address the diverse problems within the VC domain. Some of them imposed assumptions over performed computations, while the others took advantage of interactivity/non-interactivity, zero knowledge proofs, and arguments. Further proposals utilized the powers of probabilistic checkable or computationally sound proofs. In this survey, we present a chronological study and classify the VC proposals based on their adopted domains. First, we provide a broader overview of the theoretical advancements while critically analyzing them. Subsequently, we present a comprehensive view of their utilization in the state of the art VC approaches. Moreover, a brief overviewof recent proof based VC systems is also presented that lifted up the VC domain to the verge of practicality. We use the presented study and reviewed results to identify the similarities and alterations, modifications, and hybridization of different approaches, while comparing their advantages and reporting their overheads. Finally, we discuss implementation of such VC based systems, their applications, and the likely future directions.

Keywords

verifiable computation / cloud computation / interactive / non-interactive / zero knowledge / probabilistic checkable proofs / computationally sound proofs

References

[1] Gennaro R, Gentry C, Parno B. Non-interactive verifiable computing: outsourcing computation to untrusted workers. In: Proceedings of Annual Cryptology Conference. 2010, 465–482

[2] Goldwasser S, Kalai Y T, Rothblum G N. Delegating computation: interactive proofs for muggles. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 2008, 113–122

[3] Anderson D P. Public computing: reconnecting people to science. In: Proceedings of Conference on Shared Knowledge and the Web. 2003, 17–19

[4] Anderson D P. BOINC: a system for public-resource computing and storage. In: Proceedings of the 5th IEEE/ACM International Workshop on Grid Computing. 2004, 4–10

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

[6] Mell P, Grance T. The NIST definition of cloud computing. National Institute of Standards and Technology, 2009, 53(6): 50

[7] Goldwasser S, Micali S, Racko C. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 1989, 18(1): 186–208

[8] Babai L. Trading group theory for randomness. In: Proceedings of the 17th Annual ACM Symposium on Theory of Computing. 1985, 421–429

[9] Babai L, Fortnow L, Levin L A, Szegedy M. Checking computations in polylogarithmic time. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing. 1991, 21–32

[10] Arora S, Safra S. Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM, 1998, 45(1): 70–122

[11] Arora S, Lund C, Motwani R, Sudan M, Szegedy M. Proof verification and the hardness of approximation problems. Journal of the ACM, 1998, 45(3): 501–555

[12] Kilian J. A note on efficient zero-knowledge proofs and arguments. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing. 1992, 723–732

[13] Kilian J. Improved efficient arguments. In: Proceedings of Annual International Cryptology Conference. 1995, 311–324

[14] Micali S. Computationally sound proofs. SIAM Journal on Computing, 2000, 30(4): 1253–1298

[15] Shamir A. IP= PSPACE. Journal of the ACM, 1992, 39(4): 869–877

[16] Lund C, Fortnow L, Karlo H, Nisan N. Algebraic methods for interactive proof systems. Journal of the ACM, 1992, 39(4): 859–868

[17] Chung K M, Kalai Y, Vadhan S. Improved delegation of computation using fully homomorphic encryption. In: Proceedings of Annual Cryptology Conference. 2010, 483–501

[18] Goldwasser S, Sipser M. Private coins versus public coins in interactive proof systems. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing. 1986, 59–68

[19] Ben-Or M, Goldwasser S, Kilian J, Wigderson A. Multi-prover interactive proofs: how to remove intractability assumptions. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing. 1988, 113–131

[20] Babai L, Fortnow L, Lund C. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1991, 1(1): 3–40

[21] Goldreich O, Micali S, Wigderson A. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 1991, 38(3): 690–728

[22] Ben-Or M, Goldreich O, Goldwasser S, Håstad J, Kilian J, Micali S, Rogaway P. Everything provable is provable in zero-knowledge. In: Proceedings of Conference on the Theory and Application of Cryptography. 1988, 37–56

[23] Fortnow L. The complexity of perfect zero-knowledge. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing. 1987, 204–209

[24] Aiello W, Hastad J. Perfect zero-knowledge languages can be recognized in two rounds. In: Proceedings of the 28th Annual Symposium on Foundations of Computer Science. 1987, 439–448

[25] Feige U, Fiat A, Shamir A. Zero-knowledge proofs of identity. Journal of Cryptology, 1988, 1(2): 77–94

[26] Fiat A, Shamir A. How to prove yourself: Practical solutions to identification and signature problems. In: Proceedings of Conference on the Theory and Application of Cryptographic Techniques. 1986, 186–194

[27] Goldreich O, Oren Y. Definitions and properties of zero-knowledge proof systems. Journal of Cryptology, 1994, 7(1): 1–32

[28] Feige U, Shamir A. Zero knowledge proofs of knowledge in two rounds. In: Proceedings of Conference on the Theory and Application of Cryptology. 1989, 526–544

[29] Goldreich O, Kahan A. A How to construct constant-round zero knowledge proof systems for NP. Journal of Cryptology, 1996, 9(3): 167–189

[30] Groth J, Ostrovsky R, Sahai A. Perfect non-interactive zero knowledge for NP. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2006, 339–358

[31] Micali S, Rabin M, Kilian J. Zero-knowledge sets. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science. 2003, 80–91

[32] Feige U, Goldwasser S, Lovász L, Safra S, Szegedy M. Approximating clique is almost NP-complete. In: Proceedings of the 32nd Annual Symposium on Foundations of Computer Science. 1991, 2–12

[33] Kalai Y T, Raz R. Interactive PCP. In: Proceedings of International Colloquium on Automata, Languages, and Programming. 2008, 536–547

[34] Kalai Y T, Raz R. Probabilistically checkable arguments. In: Halevi S, eds. Advances in Cryptology-CRYPTO. Lecture Notes in Computer Science, Vol 5677. Berlin: Springer, 2009, 143–159

[35] Cachin C, Micali S, Stadler M. Computationally private information retrieval with polylogarithmic communication. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques. 1999, 402–414

[36] Bitansky N, Canetti R, Chiesa A, Tromer E. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. 2012, 326–349

[37] Chung K M, Kalai Y T, Liu F H, Raz R. Memory delegation. In: Proceedings of Annual Cryptology Conference. 2011, 151–168

[38] Gentry C. A fully homomorphic encryption scheme. Dissertation for the Doctoral Degree. Stanford: Stanford University, 2009

[39] Barak B, Goldreich O. Universal arguments and their applications. SIAM Journal on Computing, 2008, 38(5): 1661–1694

[40] Goldwasser S, Lin H, Rubinstein A. Delegation of Computation without Rejection Problem from Designated Verifier CS-Proofs. IACR Cryptology ePrint Archive, 2011, 2011: 456

[41] Sadeghi A R. Trusted computing—special aspects and challenges. In: Proceedings of International Conference on Current Trends in Theory and Practice of Computer Science. 2008, 98–117

[42] Wen Y, Lee J, Liu Z, Zheng Q, Shi W, Xu S, Suh T. Multi-processor architectural support for protecting virtual machine privacy in untrusted cloud environment. In: Proceedings of the ACM International Conference on Computing Frontiers. 2013

[43] Seshadri A, Luk M, Shi E, Perrig A, van Doorn L, Khosla P. Pioneer: verifying code integrity and enforcing untampered code execution on legacy systems. ACM SIGOPS Operating Systems Review, 2005, 39(5): 1–16

[44] Parno B, McCune J M, Perrig A. Bootstrapping Trust in Modern Computers. Springer Science & Business Media, 2011

[45] Malkhi D, Reiter M. Byzantine quorum systems. Distributed Computing, 1998, 11(4): 203–213

[46] Canetti R, Riva B, Rothblum G N. Practical delegation of computation using multiple servers. In: Proceedings of the 18th ACM Conference on Computer and Communications Security. 2011, 445–454

[47] Monrose F, Wycko P, Rubin A D. Distributed Execution with Remote Audit. InNDSS, 1999, 99: 3–5

[48] Belenkiy M, Chase M, Erway C C, Jannotti J, Küpçü A, Lysyanskaya A. Incentivizing outsourced computation. In: Proceedings of the 3rd International Workshop on Economics of Networked Systems. 2008, 85–90

[49] Yao A C. How to generate and exchange secrets. In: Proceedings of the 27th Annual Symposium on Foundations of Computer Science. 1986, 162–167

[50] Benabbas S, Gennaro R, Vahlis Y. Verifiable delegation of computation over large datasets. In: Proceedings of Annual Cryptology Conference. 2011, 111–131

[51] Ananth P, Chandran N, Goyal V, Kanukurthi B, Ostrovsky R. Achieving privacy in verifiable computation with multiple servers—without FHE and without pre-processing. In: Proceedings of International Workshop on Public Key Cryptography. 2014, 149–166

[52] Fiore D, Gennaro R, Pastro V. Efficiently verifiable computation on encrypted data. In: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. 2014, 844–855

[53] Ben-Or M, Goldwasser S, Kilian J, Wigderson A. Multi-prover interactive proofs: how to remove intractability assumptions. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing. 1988, 113–131

[54] Setty S T, Vu V, Panpalia N, Braun B, Blumberg A J, Walfish M. Taking proof-based verified computation a few steps closer to practicality. In: Proceedings of USENIX Security Symposium. 2012, 253–268

[55] Cormode G, Mitzenmacher M, Thaler J. Practical verified computation with streaming interactive proofs. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. 2012, 90–112

[56] Setty S, Braun B, Vu V, Blumberg A J, Parno B, Walfish M. Resolving the conflict between generality and plausibility in verified computation. In: Proceedings of the 8th ACM European Conference on Computer Systems. 2013, 71–84

[57] Parno B, Howell J, Gentry C, Raykova M. Pinocchio: nearly practical verifiable computation. In: Proceedings of IEEE Symposium on Security and Privacy. 2013, 238–252

[58] Costello C, Fournet C, Howell J, Kohlweiss M, Kreuter B, Naehrig M, Parno B, Zahur S. Geppetto: versatile verifiable computation. In: Proceedings of IEEE Symposium on Security and Privacy. 2015, 253–270

[59] Ben-Sasson E, Chiesa A, Tromer E, Virza M. Succinct non-interactive zero knowledge for a von Neumann architecture. In: Proceedings of the 23rd USENIX Security Symposium. 2014

[60] Braun B, Feldman A J, Ren Z, Setty S, Blumberg A J, Walfish M. Verifying computations with state. In: Proceedings of the 24th ACM Symposium on Operating Systems Principles. 2013, 341–357

[61] Wahby R S, Setty S T V, Ren Z, Blumberg A J, Walfish M. Efficient RAM and control flow in verifiable outsourced computation. IACR Cryptology ePrint Archive, 2014, 2014: 674

[62] Walfish M, Blumberg A J. Verifying computations without reexecuting them. Communications of the ACM, 2015, 58(2): 74–84

[63] Bennet S Y. Using secure coprocessors. Dissertation for the Doctoral Degree. Pittsburgh: Carnegie Mellon University, 1994

[64] Smith S W, Weingart S. Building a high-performance, programmable secure coprocessor. Computer Networks, 1999, 31(8): 831–860

[65] Vu V, Setty S, Blumberg A J, Walfish M. A hybrid architecture for interactive verifiable computation. In: Proceedings of IEEE Symposium on Security and Privacy. 2013, 223–237

[66] Rothblum G N, Vadhan S, Wigderson A. Interactive proofs of proximity: delegating computation in sublinear time. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing. 2013, 793–802

[67] Goldwasser S, Kalai Y T, Rothblum G N. Delegating computation: interactive proofs for muggles. Journal of the ACM, 2015, 62(4): 27

[68] Blumberg A J, Thaler J, Vu V, Walfish M. Verifiable computation using multiple provers. IACR Cryptology ePrint Archive, 2014, 2014: 846

[69] Goldreich O. Modern Cryptography, Probabilistic Proofs and Pseudorandomness. Springer Science & Business Media, 1998

[70] Goldreich O. Zero-Knowledge twenty years after its invention. IACR Cryptology ePrint Archive, 2002, 2002: 186

[71] Blum M, Feldman P, Micali S. Non-interactive zero-knowledge and its applications. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing. 1988, 103–112

[72] Lapidot D, Shamir A. Publicly verifiable non-interactive zero knowledge proofs. In: Proceedings of Conference on the Theory and Application of Cryptography. 1990, 353–365

[73] Groth J. Short pairing-based non-interactive zero-knowledge arguments. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. 2010, 321–340

[74] Bitansky N, Canetti R, Chiesa A, Tromer E. Recursive composition and bootstrapping for SNARKs and proof-carrying data. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing. 2013, 111–120

[75] Ben-Sasson E, Chiesa A, Tromer E, Virza M. Scalable zero knowledge via cycles of elliptic curves. In: Proceedings of International Cryptology Conference. 2014, 276–294

[76] Chiesa A, Tromer E, Virza M. Cluster computing in zero knowledge. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2015, 371–403

[77] Gennaro R, Gentry C, Parno B, Raykova M. Quadratic span programs and succinct NIZKs without PCPs. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2013, 626–645

[78] Lipmaa H. Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. 2013, 41–60

[79] Fauzi P, Lipmaa H, Zhang B. Efficient modular NIZK arguments from shift and product. In: Proceedings of International Conference on Cryptology and Network Security. 2013, 92–121

[80] Lipmaa H. Almost optimal short adaptive non-interactive zero knowledge. IACR Cryptology ePrint Archive, 2014, 2014: 396

[81] Ishai Y, Kushilevitz E, Ostrovsky R. Efficient arguments without short PCPs. In: Proceedings of the 22nd Annual IEEE Conference on Computational Complexity. 2007, 278–291

[82] Di Crescenzo G, Lipmaa H. Succinct NP proofs from an extractability assumption. In: Proceedings of Conference on Computability in Europe. 2008, 75–185

[83] Xu G, Amariucai G, Guan Y. Delegation of computation with verification outsourcing: curious verifiers. In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing. 2013

[84] Setty S, Blumberg A J, Walfish M. Toward practical and unconditional verification of remote computations. In: Proceedings of the 13th USENIX Conference on Hot Topics in Operating Systems. 2011

[85] Chung K M, Kalai Y, Vadhan S. Improved delegation of computation using fully homomorphic encryption. In: Proceedings of Annual Cryptology Conference. 2010, 483–501

[86] Parno B, Raykova M, Vaikuntanathan V. How to delegate and verify in public: verifiable computation from attribute-based encryption. In: Proceedings of Theory of Cryptography Conference. 2012, 422–439.

[87] Papamanthou C, Shi E, Tamassia R. Signatures of correct computation. In: Sahai A, eds. Theory of Cryptography. Lecture Notes in Computer Science, Vol 7785. Berlin: Springer, 2013, 222–242

[88] Choi S G, Katz J, Kumaresan R, Cid C. Multi-client non-interactive verifiable computation. In: Sahai A, eds. Theory of Cryptography. Lecture Notes in Computer Science, Vol 7785. Berlin: Springer, 2013, 499–518

[89] Apon D, Katz J, Shi E, Thiruvengadam A. Verifiable oblivious storage. In: Proceedings of International Workshop on Public Key Cryptography. 2014, 131–148

[90] Laud P, Pankova A. Verifiable computation in multiparty protocols with honest majority. In: Proceedings of International Conference on Provable Security. 2014, 146–161

[91] Sahai A, Waters B. Fuzzy identity-based encryption. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2005, 457–473

[92] Goyal V, Pandey O, Sahai A, Waters B. Attribute-based encryption for fine-grained access control of encrypted data. In: Proceedings of the 13th ACM Conference on Computer and Communications Security. 2006, 89–98

[93] Alderman J, Janson C, Cid C, Crampton J. Revocation in publicly verifiable outsourced computation. In: Proceedings of International Workshop on Public Key Cryptography. 2014, 51–71

[94] Alderman J, Janson C, Cid C, Crampton J. Access control in publicly verifiable outsourced computation. In: Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security. 2015, 657–662

[95] Alderman J, Janson C, Cid C, Crampton J. Hybrid publicly verifiable computation. In: Proceedings of Cryptographers’ Track at the RSA Conference. 2016, 147–163

[96] Gordon S D, Katz J, Liu F H, Shi E, Zhou H S. Multi-client verifiable computation with stronger security guarantees. In: Proceedings of Theory of Cryptography Conference. 2015, 144–168

[97] Backes M, Fiore D, Reischuk R M. Verifiable delegation of computation on outsourced data. In: Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security. 2013, 863–874

[98] Gennaro R, Wichs D. Fully homomorphic message authenticators. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. 2013, 301–320

[99] Juels A, Kaliski Jr B S. PORs: proofs of retrievability for large files. In: Proceedings of the 14th ACM Conference on Computer and Communications Security. 2007, 584–597

[100] Fiore D, Gennaro R. Publicly verifiable delegation of large polynomials and matrix computations, with applications. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security. 2012, 501–512

[101] Schröder D, Schröder H. Verifiable data streaming. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security. 2012, 953–964

[102] Krupp J, Schröder D, Simkin M, Fiore D, Ateniese G, Nuernberger S. Nearly optimal verifiable data streaming. In: Cheng C M, Chung K M, Persiano G, et al., eds. Public-Key Cryptography – PKC 2016. Lecture Notes in Computer Science, Vol 9614. Berlin: Springer, 2016

[103] Blanton M, Zhang Y, Frikken K B. Secure and verifiable outsourcing of large-scale biometric computations. ACM Transactions on Information and System Security, 2013, 16(3): 11

[104] Li J, Jia C, Li J, Chen X. Outsourcing encryption of attribute-based encryption with MapReduce. In: Proceedings of International Conference on Information and Communications Security. 2012, 191–201

[105] Sahai A, Seyalioglu H, Waters B. Dynamic credentials and cipher text delegation for attribute-based encryption. In: Safavi-Naini R, Canetti R, eds. Advances in Cryptology – CRYPTO 2012. Lecture Notes in Computer Science, Vol 7417. Berlin: Springer, 2012, 199–217

[106] Li J, Huang X, Li J, Chen X, Xiang Y. Securely outsourcing attribute based encryption with checkability. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(8): 2201–2210

[107] Li J, Li X, Wang L, He D, Ahmad H, Niu X. Fuzzy encryption in cloud computation: efficient verifiable outsourced attribute-based encryption. Soft Computing. 2017, 1–8

[108] Carter H, Mood B, Traynor P, Butler K. Secure outsourced garbled circuit evaluation for mobile devices. Journal of Computer Security, 2016, 24(2): 137–180

[109] Carter H, Lever C, Traynor P. Whitewash: outsourcing garbled circuit generation for mobile devices. In: Proceedings of the 30th Annual Computer Security Applications Conference. 2014, 266–275

[110] Chen X, Li J, Ma J, Tang Q, Lou W. New algorithms for secure outsourcing of modular exponentiations. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(9): 2386–2396

[111] Kiraz M S, Uzunkol O. Efficient and verifiable algorithms for secure outsourcing of cryptographic computations. International Journal of Information Security, 2016, 15(5): 519–537

[112] Ben-Sasson E, Chiesa A, Genkin D, Tromer E, Virza M. SNARKs for C: verifying program executions succinctly and in zero knowledge. In: Canetti R, Garay J A, eds. Advances in Cryptology – CRYPTO 2013. Lecture Notes in Computer Science, Vol 8043. Berlin: Springer, 2013, 90–108

[113] Kosba A E, Papadopoulos D, Papamanthou C, Sayed M F, Shi E, Triandopoulos N. TRUESET: faster verifiable set computations. USENIX Security, 2014, 81(84): 153

[114] Thaler J, Roberts M, Mitzenmacher M, Pfister H. Verifiable computation with massively parallel interactive proofs. In: Proceedings of HotCloud. 2012

[115] Thaler J. Time-optimal interactive proofs for circuit evaluation. In: Canetti R, Garay J A, eds. Advances in Cryptology – CRYPTO 2013. Lecture Notes in Computer Science, Vol 8043. Berlin: Springer, 2013, 71–89

[116] Wang L C, LI J, Ahmad H. Challenges of fully homomorphic encryptions for the Internet of things. IEICE Transactions on Information and Systems, 2016, 99(8): 1982–1990

[117] Hong H, Wang L, Ahmad H, Yang Y, Qu Z. Minimum length key in MST cryptosystems. Science China Information Sciences, 2017, 60(5): 05210

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature