Computer Science ›› 2015, Vol. 42 ›› Issue (11): 1-7.doi: 10.11896/j.issn.1002-137X.2015.11.001

    Next Articles

Survey on Verifiable Delegation of Computation

SUN Yi, CHEN Xing-yuan, DU Xue-hui and XU Jian   

  • Online:2018-11-14 Published:2018-11-14

Abstract: In order to resolve safety issue of outsourcing data and verifiable delegation of computation,the theory of veri-fiable computation starts to draw public’s attention recently.This paper illustrated how verifiable delegation of computation technique resolves above verifiability issues and provided formal definition of verifiable computation.This is the first time to summarize and induce current schemes from different classification methods,and illustrate key techniques and deficiency.Then this paper compared and analyzed these schemes from two aspects of function and performance.Finally,combined with the application hotspots,we forecasted tendency and development perspective in this research area from different application directions.

Key words: Verifiable delegation of computation,Cloud computing,Secure data outsourcing,Homomorphic encryption,Homomorphic MACs,Authenticated data structures

[1] Benabbas S,Gennaro R,Vahlis Y.Verifiable delegation of computation over large datasets[M]∥Advances in Cryptology-CRYPTO2011,Springer,2011:111-131
[2] Monrose F,Wyckoff P,Rubin A.Distributed execution with remote audit[C]∥Proc.of ISOC NDSS.1999
[3] Du W,Goodrich M T.Searching for high-value rare events with uncheatable grid computing[C]∥ACNS.2005:122-137
[4] Castro M,Liskov B.Practical Byzantine fault tolerance and proactive recovery[J].ACM Trans.on Comp.Sys., 2002,20(4):398-461
[5] Carbunar B,Sion R.Uncheatable reputation for distributed computation markets[C]∥Financial Cryptography.2006:96-110
[6] Seshadri A,Luk M,Shi E,et al.Pioneer:Verifying integrity and guaranteeing execution of code on legacy platforms [C]∥Proc.of the ACM SOSP.2005
[7] Parno B,McCune J M,Perrig A.Bootstrapping Trust in Modern Computers[M].Springer,2011:35-50
[8] Chung K M,Kalai Y,Vadhan S P.Improved delegation of computation using fully homomorphic encryption[C]∥CRYP-TO 2010.LNCS 6223,2010:483-501
[9] Gennaro R,Gentry C,Parno B.Non-interactive verifiable com-puting:Outsourcing computation to untrusted workers[C]∥CRYPTO 2010.LNCS 6223,2010:465-482
[10] Chen X,Li J,Susilo W.Efficient Fair Conditional Payments for Outsourcing Computations[J].IEEE Transactions on Information Forensics and Security,2012,7(6):1687-1694
[11] Ma X,Zhang F,Li J.Verifiable Evaluation of Private Polynomia-ls[C]∥2013 Fourth International Conference on Emerging Intelligent Data and Web Technologies (EIDWT).2013:451-458
[12] Gentry C.A fully homomorphic encryption scheme[D].Stanford University,2009
[13] Micali S.Computationally sound proofs[J].SIAM J.Comput,2000,30(4):1253-1298
[14] Goldwasser S,Kalai Y T,Rothblum G N.Delegating computation:Interactive proofs for muggles[C]∥STOC.2008
[15] Gentry C,Wichs D.Separating succinct non-interactive argu-ments from all falsifiable assumptions[C]∥Fortnow L,Vadhan S P.eds.43rd ACM STOC.San Jose,California,USA:ACM Press,2011:99-108
[16] Bitansky N,Canetti R,Chiesa A,et al.From extractable collision resistance to succinct non-interactive arguments of knowledge,and back again[C]∥Proceedings of the 3rd Symposium on Innovations in Theoretical Computer Science(ITCS’12).2012
[17] Thaler J.Practical verified computation with streaming interactive proofs[D].Harvard University,2013
[18] Vu V,Setty S,Blumberg A,et al.A hybrid architecture for interactive verifiable computation[C]∥IEEE Symposium on Security and Privacy.2013:223-237
[19] Gentry C,Halevi S,Smart N.Homomorphic evaluation of theAES circuit[C]∥CRYPTO.2012
[20] Johnson R,Molnar D,Song D X,et al.Homomorphic signature schemes[M]∥Preneel B.ed.CT-RSA 2002,volume 2271 of LNCS.San Jose,CA,USA.Springer,2002:244-262
[21] Boneh D,Freeman D M.Homomorphic signatures for polynomial functions[C]∥Paterson K G.ed.EUROCRYPT 2011,vo-lume 6632 of LNCS.Tallinn,Estonia,Springer,Berlin,Germany,2011:149-168
[22] Gennaro R,Wichs D.Fully homomorphic message authentica-tors.http://eprint.iacr.org/
[23] Catalano D,Fiore D.Practical homomorphic MACs for arithmetic circuits[C]∥Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques(Eurocrypt ’13).2013:336-352
[24] Micali S.CS proofs[C]∥35th FOCS.Santa Fe,New Mexico,1994:436-453
[25] Chung K-M,Kalai Y T,Liu F-H,et al.Memory delegation[C]∥Rogaway P.ed.CRYPTO 2011,volume 6841 of LNCS.Santa Barbara,CA,USA, Springer,Berlin,Germany,2011:151-168
[26] Thaler J,Roberts M,Mitzenmacher M,et al.Verifiable computation with massively parallel interactive proofs[C]∥USENIX HotCloud Workshop.2012:22
[27] Setty S,McPherson R,Blumberg A J,et al.Making argument systems for outsourced computation practical (sometimes) [C]∥NDSS.2012
[28] Arora S,Lund C,Motwani R,et al.Proof verification and the hardness of approximation problems[J].J.ACM,1998,45(3):14-23
[29] Parno B,Howell J,Gentry C,et al.Pinocchio:Nearly Practical Verifiable Computation[C]∥2013 IEEE Symposium on Security and Privacy (SP).2013:238-252
[30] Papamanthou C,Shi E,Tamassia R.Publicly verifiable delegation of computation.http://eprint.iacr.org/2011/587
[31] Fiore D,Gennaro R.Publicly verifiable delegation of large polynomials and matrix computations,with applications[C]∥2012 ACM Conference on Computer and Communication Security.2012
[32] Backes M,Fiore D,Reischuk R M.Verifiable delegation of computation on outsourced data[C]∥2013 ACM Conference on Computer and Communication Security.ACM Press,2013:273-291
[33] Parno B,Raykova M,Vaikuntanathan V.How to delegate and verify in public:Verifiable computation from attribute-based encryption[C]∥Cramer R.ed.TCC 2012,volume 7194 of LNCS.Taormina,Sicily,Italy,Springer,Berlin,Germany,2012:422-439
[34] Naor M,Nissim K.Certificate revocation and certificate update[J].IEEE Journal on Selected Areas in Communications,2000,18(4):561-570
[35] Merkle R C.A certified digital signature [C]∥Brassard G.ed.Proc.CRYPTO’89,volume 435 of LNCS.Springer-Verlag,1990:218-238
[36] Goodrich M T,Tamassia R.Efficient authenticated dictionaries with skip lists and commutative hashing.http://www.cs.brown.edu/cgc/stms/papers/hashskip.pdf
[37] Devanbu P,Gertz M,Martel C,et al.Authentic third-party data publication[C]∥Fourteenth IFIP 11.3 Conference on Database Security.2000
[38] Martel C,Nuckolls G,Devanbu P,et al.A general model for authenticated data structures[J].Algorithmica,2004,9(1):21-41
[39] Goodrich M T,Tamassia R,Triandopoulos N.Efficient Authenticated Data Structures for Graph Connectivity and Geometric Search Problems[J].Algorithmica,2011,60:505-552
[40] Papamanthou C,Tamassia R,Triandopoulos N.Optimal Au-thentication of Operations on Dynamic Sets.http://eprint.iacr.org/
[41] Li Ling.Reserch on some issues of data security in cloud computing services[D].University of Science and Technology of China,2012
[42] Schroeder D,Schroeder H.Verifiable Data Streaming[C]∥Proceedings of the 2012 ACM Conference on Computer and Communications Security(ACM 2012).2012:953-964

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!