可验证授权计算研究综述

doi:10.11896/j.issn.1002-137X.2015.11.001

摘要/Abstract

摘要： 为了解决外包数据和授权计算的安全性问题,近年来可验证授权计算理论又重新受到人们的关注和青睐。文中重点描述了在不可信环境下可验证授权计算技术是如何解决外包数据和授权计算的可验证性问题,并给出了可验证授权计算方案的形式化定义。首先采用不同分类方法对现有研究方案进行总结与归纳,指出现有研究方案的特点、所采用关键技术及不足之处；然后从功能和性能两个方面对方案进行对比分析；最后结合应用热点,从不同应用方向展望了该领域的研究趋势和发展前景。

关键词: 可验证授权计算,云计算,安全外包数据,同态加密,同态认证码,可认证数据结构

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

孙奕,陈性元,杜学绘,徐建. 可验证授权计算研究综述[J]. 计算机科学, 2015, 42(11): 1-7. https://doi.org/10.11896/j.issn.1002-137X.2015.11.001

SUN Yi, CHEN Xing-yuan, DU Xue-hui and XU Jian. Survey on Verifiable Delegation of Computation[J]. Computer Science, 2015, 42(11): 1-7. https://doi.org/10.11896/j.issn.1002-137X.2015.11.001

参考文献

[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

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed