Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Mobile Networks and Applications
Published in: Mobile Networks and Applications 3/2017

06-05-2017

A Survey of Verifiable Computation

Authors: Xixun Yu, Zheng Yan, Athanasios V. Vasilakos

Published in: Mobile Networks and Applications | Issue 3/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Internet of Things (IoT) has taken place to motivate various intelligent applications with the data collected by the things”. Meanwhile, Cloud computing offers an efficient and convenient way to store, process and analyze huge amount of data. Because a Cloud Service Provider (CSP) that is employed to store and process user private data is actually not in the trust domains of cloud users, data security becomes a serious issue in cloud computing. One crucial problem in cloud is the cloud data processing result may be incorrect, thus cannot be fully trusted. This calls for research to verify the correctness of data processing at the cloud in order to enhance its trustworthiness, especially for encrypted data processing. At present, various cryptosystems have been proposed to achieve verifiability with different characteristics and quality. However, the literature still lacks a thorough survey to review the current state of art in order to get a comprehensive view of this research field, named verifiable computation. In this paper, we review existing work of verifiable computation by comparing and discussing pros and cons according to performance requirements, highlight open research issues through serious review and analysis and propose a number of research directions in order to guide future research.
previous article Editorial: Mobile Multimedia Communications
next article LTE-EMU: A High Fidelity LTE Cellar Network Testbed for Mobile Video Streaming

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Show more products
Literature
1.
Jing Q, Vasilakos AV, Wan J, Lu J, Qiu D (2014) Security of the internet of things: perspectives and challenges. Wirel Netw 20(8):2481–2501CrossRef
2.
Shu Z, Wan J, Li D, Lin J, Vasilakos AV, Imran M (2016) Security in software-defined networking: threats and countermeasures. Mobile Networks and Applications 21(5):764–775CrossRef
3.
Parno B, Raykova M, Vaikuntanathan V (2012) How to delegate and verify in public: verifiable computation from attribute-based encryption. Proc of the 9th international conference on Theory of Cryptography (TCC’12), Springer Berlin Heidelberg, pp 422–439
4.
Dijk M, Clarke D, Gassend B, Edward Suh G, Devadas S (2006) Speeding up exponentiation using an untrusted computational resource. Journal Designs, Codes and Cryptography 39:253–273MathSciNetCrossRefMATH
5.
Catalano D, Fiore D (2013) Practical homomorphic macs for arithmetic circuits. In: Advances in Cryptology–EUROCRYPT, Springer, pp. 336–352
6.
Gennaro R, Wichs D (2013) Fully homomorphic message authenticators. In: Advances in Cryptology-ASIACRYPT, Springer, pp 301–320
7.
Backes M, Fiore D, Reischuk RM (2013) Verifiable delegation of computation on outsourced data. In: ACM conference on Computer and communications security. ACM, pp 863–874
8.
Boneh D, Freeman DM (2011) Homomorphic signatures for polynomial functions. In: Advances in Cryptology– EUROCRYPT, Springer, pp 149–168
9.
Chung KM, Kalai Y, Vadhan S (2010) Improved delegation of computation using fully homomorphic encryption. In: Advances in Cryptology–CRYPTO, Springer, pp 483–501
10.
Thaler JR (2013) Practical verified computation with streaming interactive proofs. Ph.D. dissertation, Harvard University
11.
Fiore D, Gennaro R (2012) Publicly verifiable delegation of large polynomials and matrix computations, with applications. In: ACM conference on Computer and communications security, ACM, pp 501–512
12.
Parno B, Howell J, Gentry C, Raykova M (2013) Pinocchio: nearly practical verifiable computation. In: IEEE Symposium on Security and Privacy, IEEE, pp 238–252
13.
Papadopoulos S, Cormode G, Deligiannakis A, Garofalakis M (2013) Lightweight authentication of linear algebraic queries on data streams. In: International conference on Management of data, ACM, pp 881–892
14.
Canetti R, Riva B, Rothblum GN (2012) Two protocols for delegation of computation. In: Proceedings of the 6th international conference on information theoretic security, ser. ICITS’12. Springer-Verlag, Berlin pp 37–61
15.
Papamanthou C, Shi E, Tamassia R (2013) Signatures of correct computation. In: Proceedings of the 10th theory of cryptography conference on theory of cryptography, ser. TCC’13. Springer-Verlag, Berlin, pp 222–242
16.
Kate A, Zaverucha GM, Goldberg I (2010) Constant-size commitments to polynomials and their applications. In: Advances in cryptology-ASIACRYPT 2010, Springer, pp 177–194
17.
18.
Blakley G (1979) Safeguarding cryptographic keys. In: Proceedings of the 1979 AFIPS National Computer Conference, AFIPS Press, Monval, pp. 313–317
19.
Mignotte M (1983) How to share a secret. In: Proceedings of the 1982 Conference on cryptography, Springer-Verlag, Berlin, Heidelberg, pp. 371–375
20.
21.
Setty S, McPherson R, Blumberg AJ, Walfish M (2012) Making argument systems for outsourced computation practical (sometimes). In: Pceedings of the ISOC NDSS
22.
Yan Z, Yu XX, Ding WX (2017) Context-aware verifiable cloud computing. IEEE Access 5:2211–2227CrossRef
23.
M. Cafaro and P. Pelle, Space-efficient Verifiable Secret Sharing Using Polynomial Interpolation. IEEE Transactions on Cloud Computing, PP(9), 1–1, 2015.
24.
H. Ma, R. Zhang, Z. Wan, Y. Lu, and S. Lin, “Verifiable and Exculpable Outsourced Attribute-Based Encryption for Access Control in Cloud Computing.” IEEE Transactions on Dependable and Secure Computing, PP(99), 1–1, 2015.
25.
Renjith P, Sabitha S (2013) Verifiable el-gamal re-encryption with authenticity in cloud. Computing, communications and networking technologies (ICCCNT), 2013 fourth international conference on, pp 1–5, 4-6 July 2013
26.
Sun W, Wang B, Cao N, Li M, Lou W, Hou YT, Li H (2014) Verifiable privacy-preserving multi-keyword text search in the cloud supporting similarity-based ranking. IEEE Transactions on Parallel and Distributed Systems 25(11):3025–3035CrossRef
27.
Wang J, Chen X, Huang X, You I, Xiang Y (2015) Verifiable auditing for outsourced database in cloud computing. IEEE Trans Comput 64(11):3293–3303MathSciNetCrossRefMATH
28.
Wen Z, Luo J, Chen H, Meng J, Li X, Li J, A Verifiable Data Deduplication Scheme in Cloud Computing. Intelligent Networking and Collaborative Systems (INCoS), 2014 International conference on, pp 85–90, 10-12, Sept 2014
29.
Xu J, Wen Q, Li W, Jin Z (2016) Circuit Ciphertext-policy attribute-based hybrid encryption with verifiable delegation in cloud computing. IEEE Transactions on Parallel and Distributed Systems 27(1):119–129CrossRef
30.
Yadav H, Dave M (2014) Secure data storage operations with verifiable outsourced decryption for mobile cloud computing. Recent Advances and innovations in Engineering (ICRAIE), pp 1–5, 9-11 may 2014
31.
Guo L, Fang Y, Li M, Li P (2015) Verifiable privacy-preserving monitoring for cloud-assisted mHealth systems. 2015 I.E. conference on computer communications (INFOCOM), pp 1026–1034, April 26 2015-may 1 2015
32.
X. Chen, J. Li, X. Huang, J. Ma, and W. Lou, “Verifiable Computation over Large Database with Incremental Updates.” IEEE Transactions on Computers, PP(99), 1–1, 2016.
33.
Li W, Xue K, Xue Y, Hong J (2016) TMACS: a robust and verifiable threshold multi-authority access control system in public cloud storage. IEEE Transactions on Parallel and Distributed Systems 27(5):1484–1496CrossRef
34.
X. Liu, W. Sun, H. Quan, W. Lou, Y. Zhang, and H. Li, “Publicly Verifiable Inner Product Evaluation over Outsourced Data Streams under Multiple Keys.” IEEE Transactions on Services Computing, PP(99), 1–1, 2016.
35.
Park KW, Han J, Chung J, Park KH (2013) THEMIS: a mutually verifiable billing system for the cloud computing environment. IEEE Trans Serv Comput 6(3):300–313CrossRef
36.
Santos WM, DE Queiroz RJGB, Saraiva CER, Junior GPV (2013) Toward coercion-resistant end-to-end verifiable electronic voting systems. 2013 12th IEEE international conference on trust, security and privacy in computing and communications, pp 1696–1703, 16-18 July 2013
37.
Schiffman J, Sun Y, Vijyakumar H, Jaeger T (2013) Cloud verifier: verifiable auditing service for IaaS clouds. 2013 I.E. Ninth World Congress on Services, pp 239–246, June 28 2013–July 3 2013
38.
Vu V, Setty S, Blumbery AJ, Walfish M (2013) A hybrid architecture for interactive verifiable computation. Security and privacy (SP), 2013 I.E. Symposium on, pp 223–237, 19-22 may 2013
39.
Goldwasser S, Kalai YT, Rothblum GN (2008) Delegating computation: interactive proofs for muggles. In: Proc ACM Symp Theory Comput, pp. 113–122
40.
Lai J, Deng RH, Pang H, Weng J (2014) Verifiable computation on outsourced encrypted data. In: Proc Eur Symp Res Comput Security, pp 273–291
41.
Vu V, Setty S, Blumberg AJ, Walfish M (2013) A hybrid architecture for interactive verifiable computation. In: Proc IEEE Symp Security Privacy, pp 223–237
42.
Zhang L, Safavi-Naini R (2014) Verifiable delegation of computations with storage-verification trade-off. In: Proc 19th Eur Symp res Comput security, pp 112–129
43.
Lai J, Deng RH, Guan C, Weng J (2013) Attribute-based encryption with verifiable outsourced decryption. IEEE Trans Inf Forensics Security 8(8):1343–1354CrossRef
44.
Atallah MJ, Frikken KB (2010) Securely outsourcing linear algebra computations. Proc ACM Symposium on information, computer and communications security (ASIACCS 2010), ACM, pp 48–59
45.
Benjamin D, Atallah MJ (2008) Private and cheating-free outsourcing of algebraic computations. Proc of the 6th Annual Conference on Privacy, Security and Trust (PST ‘08), IEEE Computer Society, pp 240–245
46.
Gennaro R, Gentry C, Parno B (2010) Non-interactive verifiable computation: outsourcing computation to untrusted workers. Proc of the 30th annual conference on Advances in cryptology (CRYPTO’10), Springer Berlin Heidelberg, pp 465–482
47.
Hohenberger S, Lysyanskaya A (2005) How to securely outsource cryptographic computations. Proc of the Second international conference on Theory of Cryptography (TCC’05), Springer Berlin Heidelberg, pp 264–282
48.
Choi SG, Katz J, Kumaresan R, Cid C (2013) Multi-Client non-interactive verifiable computation. Proc of the 10th theory of cryptography conference on Theory of Cryptography (TCC’13), Springer Berlin Heidelberg, pp 499–518
49.
Benabbas S, Gennaro R, Vahlis Y (2011) Verifiable delegation of computation over large datasets. Proc of the 31st annual conference on Advances in cryptology (CRYPTO’11), Springer Berlin Heidelberg, pp 111–131
50.
Papamanthou C, Shi E, Tamassia R (2013) Signatures of correct computation. Proc of the 10th theory of cryptography conference on Theory of Cryptography (TCC’13), Springer Berlin Heidelberg, pp 222–242
51.
Haeberlen A (2010) A case for the accountable cloud. SIGOPS Operating Systems Rev 44:52–57CrossRef
52.
Koeppe F, Schneider J (2010) Do you get what you pay for? Using proof-of-work functions to Verify performance assertions in the cloud. In: Proc. of the IEEE Second Int’l Conf. Cloud computing technology and Science (CloudCom), pp 687–692
53.
Peng K, Bao F (2009) Efficient publicly verifiable secret sharing with correctness, soundness and zk privacy. In: Information security applications (eds) Youm H, Yung M, vol. 5932 of lecture notes in computer Science, pp 118–132, Springer, Berlin Heidelberg
54.
Yan Z, Ding W, Yu X, Zhu H, Deng RH (2016) Deduplication on encrypted big data in cloud. IEEE Transactions on Big Data 2(2):138–150CrossRef
55.
Yan Z, Wang M, Li Y, Vasilakos AV (2016) Encrypted data management with deduplication in cloud computing. IEEE Cloud Computing 3(2):28–35CrossRef
56.
Yang K, Jia X, Ren K (2015) Secure and verifiable policy update outsourcing for big data access control in the cloud. Parallel & Distributed Systems IEEE Transactions on 26(12):3461–3470CrossRef
57.
Qin BD, Deng RH, Liu SL, Ma SQ (2013) Attribute-based encryption with verifiable outsourced decryption. IEEE Transactions on Information Forensics & Security 8(8):1343–1354CrossRef
58.
Chaum D (2004) Secret-ballot receipts: true voter-verifiable elections. IEEE Secur Priv 2(1):38-47
59.
Chaum D, Ryan PYA, Schneider SA (2005) A practical voter-verifiable election scheme. In: Proc of the 10th European Symposium on research in Cumputer Science (ESORICS´05), pp 118–139
60.
Adida B, Rivest RL (2006) Scratch & vote: self-contained paper-based cryptographic voting. WEPS´06: in Proc. of the 5th ACM workshop on privacy in electronic society, New York
61.
Setty S, Braun B, Vu V, Blumberg AJ, Parno B, Walfish M (2013) Resolving the conflict between generality and plausibility in verified computation. In: Proc of the ACM European Conference on Computer Systems (EuroSys), Apr. 2013
62.
Almeida JB, Bangerter E, Barbosa M, Krenn S, Sadeghi A-R, Schneider T (2010) A certifying compiler for zero-knowledge proofs of knowledge based on s-protocols. In: Proc of ESORICS
63.
Meiklejohn S, Erway CC, Küpc A, Hinkle T, Lysyanskaya A (2010) ZKPDL: a language-based system for efficient zero-knowledge proofs and electronic cash. In: Proc of USENIX
64.
Papamanthou C, Shi E, Tamassia R (2011) Publicly verifiable delegation of computation. Cryptology ePrint Archive, report 2011/587
65.
Yao A (1982) Protocols for secure computations. In: Proc of the IEEE Symposium on Foundations of Computer Science, pp 160–164
66.
Yao A (1986) How to generate and exchange secrets. In: Proc of the IEEE Symposium on Foundations of Computer Science, pp 162–167
67.
Setty S, Vu V, Panpalia N, Braun B, Blumberg AJ, Walfish M (2012) Taking proof-based verified computation a few steps closer to practicality. In: Proc. of USENIX Security
68.
Canetti R, Riva B, Rothblum GN (2011) Two 1-round protocols for delegation of computation. Cryptology ePrint Archive, report 2011/518
69.
Gentry C, Wichs D (2011) Separating succinct non-interactive arguments from all falsifiable assumptions. In: Proceedings of the ACM Symposium on Theory of Computing, STOC
70.
Papamanthou C, Tamassia R, Triandopoulos N (2011) Optimal verification of operations on dynamic sets. In: Rogaway P (ed) CRYPTO 2011. LNCS, vol. 6841. Springer, Heidelberg, pp 91–110
71.
Rivest RL, Adleman L, Dertouzos ML (1978) On data banks and privacy homomorphisms. Foundations of Secure Computation, pp 169–180
72.
Cramer R, Damgård I, Schoenmakers B (1994) Proofs of partial knowledge and simplified design of witness hiding protocols. In: Proc of CRYPTO
73.
Backes M, Maffe M, Pecina K (2012) Automated synthesis of privacy preserving distributed applications. In: Proc of ISOC NDSS
74.
Groth J, Sahai A (2008) Efficient non-interactive proof systems for bilinear groups. In: Proc of EUROCRYPT
75.
Rial A, Danezis G (2011) Privacy-preserving smart metering. In: Proc of the ACM WPES
76.
Gentry C (2009) A fully homomorphic encryption scheme. Ph.D. dissertation, Stanford University
77.
Johnson R, Molnar D, Song D, Wagner D (2002) Homomorphic signature schemes. In: CT-RSA 2002. LNCS, vol. 2271, pp 244–262, Springer, Heidelberg
78.
Catalano D, Marcedone A, Puglisi O (2013) Linearly homomorphic structure preserving signatures: new methodologies and applications. IACR Cryptology ePrint Archive 2013:801
79.
Ahn JH, Boneh D, Camenisch J, Hohenberger S, Shelat A, Waters B (2012) Computing on authenticated data. In: TCC 2012. LNCS, vol. 7194, pp 1–20, Springer, Heidelberg
80.
Attrapadung N, Libert B, Peters T (2012) Computing on authenticated data: new privacy definitions and constructions. In: ASIACRYPT 2012, LNCS, vol. 7658, pp 367–385, Springer, Heidelberg
81.
Attrapadung N, Libert B, Peters T (2013) Efficient completely context-hiding quotable and linearly homomorphic signatures. In: PKC 2013. LNCS, vol. 7778, pp 386–404, Springer, Heidelberg
82.
Boneh D, Freeman DM (2011) Homomorphic signatures for polynomial function. In: EUROCRYPT 2011. LNCS, vol. 6632, pp 149–168, Springer, Heidelberg
83.
Libert B, Peters T, Joye M, Yung M (2013) Linearly homomorphic structurepreserving signatures and their applications. In: CRYPTO 2013, Part II. LNCS, vol. 8043, pp 289–307, Springer, Heidelberg
84.
Gennaro R, Wichs D (2013) Fully homomorphic message authenticators. In: ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp 301–320, Springer, Heidelberg
85.
Joo C, Yun A (2013) Homomorphic authenticated encryption secure against chosenciphertext attack. IACR Cryptology ePrint Archive 2013:726
86.
Catalano D, Fiore D (2013) Practical homomorphic MACs for arithmetic circuits. In: EUROCRYPT 2013. LNCS, vol. 7881, pp 336–352, Springer, Heidelberg
87.
Shi E, Chan TH, Rieffel EG, Chow R, Song D (2011) Privacy-preserving aggregation of time-series data. In: NDSS 2011, the internet society, February 2011
88.
Goldwasser S, Gordon SD, Goyal V, Jain A, Katz J, Liu FH, Sahai A, Shi E, Zhou HS (2014) Multi-input functional encryption. In EUROCRYPT 2014, LNCS, vol. 8441, Springer, Heidelberg, pp 578–602
89.
Gordon SD, Katz J, Liu FH, Shi E, Zhou HS (2015) Multi-client verifiable computation with stronger security guarantees. In: 12th theory of cryptography conference, TCC 2015, Proceedings: LNCS 9015, pp 144–68
90.
Sakka MA, Defude B (2012) Towards a scalable semantic provenance management system. Transactions on Large-Scale Data- and Knowledge-Centered Systems VII, Springer Verlag, Berlin, pp 96–127
91.
Sakka MA, Defude B (2012) Scalability issues in designing and implementing semantic provenance management systems. In: Proc. of data Management in Cloud, grid and P2P systems. 5th international conference, globe 2012, Springer Verlag, Berlin, Germany, pp 49–61, 5-6 sept. 2012
92.
Marinho A, Murta L, Werner C et al (2012) ProvManager: a provenance management system for scientific workflows. Concurrency and Computation: Practice and Experience 24(13):1513–1530CrossRef
93.
Buneman P, Chapman A, Cheney J (2006) Provenance management in curated databases. 2006 ACM SIGMOD international conference on Management of Data, Chicago, pp 539–550, 27-29, June 2006
94.
Zheng H, Zhu QH, Wu K (2012) Provenance management for data quality assessment. Journal of Software 7(8):1905–1910CrossRef
95.
Sabaa H, Panda B (2007) data authentication and provenance management. In: Prof of Second IEEE International Conference on Digital Information Management, Piscataway, pp 309–14, Oct. 2007
96.
Li T, Liu L, Zhang XL et al (2014) ProvenanceLens: service provenance management in the cloud. Collaborative computing: networking, applications and Worksharing (CollaborateCom), 2014 international conference on, pp 275–284
97.
Young M (1989) The technical Writer’s handbook. University Science, Mill Valley
Metadata
Title
A Survey of Verifiable Computation
Authors
Xixun Yu
Zheng Yan
Athanasios V. Vasilakos
Publication date
06-05-2017
Publisher
Springer US
Published in
Mobile Networks and Applications / Issue 3/2017
Print ISSN: 1383-469X
Electronic ISSN: 1572-8153
DOI
https://doi.org/10.1007/s11036-017-0872-3

Other articles of this Issue 3/2017

Mobile Networks and Applications 3/2017 Go to the issue

OriginalPaper

Oblique Projection Matching Pursuit

OriginalPaper

Isolating Misbehaving Nodes in MANETs with an Adaptive Trust Threshold Strategy

OriginalPaper

Haze Removal via Edge Weighted Pixel-to-Patch Fusion

OriginalPaper

Joint Resource Block and Power Allocation for Interference Management in Device to Device Underlay Cellular Networks: A Game Theoretic Approach

OriginalPaper

Greedy Block Coordinate Descent under Restricted Isometry Property

Erratum

Erratum to: Editorial: Multimedia in Technology Enhanced Learning