nach oben

Cluster Computing

Erschienen in:

16.05.2020

Multi-matrix verifiable computation

verfasst von: Yan He, Liang Feng Zhang

Erschienen in: Cluster Computing | Ausgabe 1/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The problem of securely outsourcing computation to cloud servers has attracted a large amount of attention in recent years. The verifiable computation of Gennaro, Gentry, Parno (Crypto’10) allows a client to verify the server’s computation of a function with substantially less time than performing the outsourced computation from scratch. In a multi-function model (Parno, Raykova, Vaikuntanathan; TCC’12) of verifiable computation, the process of encoding function and the process of preparing input are decoupled such that any client can freely submit a computation request on its input, without having to generate an encoding of the function in advance. In this paper, we propose a multi-matrix verifiable computation scheme that allows the secure outsourcing of the matrix functions over a finite field. Our scheme is outsourceable. When it is used to outsource m linear functions, the scheme is roughly m times faster and has less communication cost than the previously best known scheme by Fiore and Gennaro (CCS’12), both in the client-side computation and in the server-side computation. We also show the cost saving with detailed implementations.

Vorheriger Artikel BDDT: use blockchain to facilitate IoT data transactions

Nächster Artikel MapReduce FCM clustering set algorithm

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Agrawal, S., Boneh, D.: Homomorphic MACs: MAC-based integrity for network coding. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol. 5536, pp. 292–305. Springer, Heidelberg (2009)

Applebaum, B., Ishai, Y., Kushilevitz, E.: From secrecy to soundness: efficient verification via secure computation. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 152–163. Springer, Heidelberg (2010)

Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45(1), 70–122 (1998)MathSciNetCrossRef

Assuncao, M.D., Costanzo, A., Buyya, R.: A cost-benefit analysis of using cloud computing to extend the capacity of clusters. Clust. Comput. 13(3), 335–347 (2010)CrossRef

Babai, L.: Trading group theory for randomness. In: STOC, pp. 421–429 (1985)

Backes, M., Barbosa, M., Fiore, D., Reischuk, R.M.: ADSNARK: Nearly Practical and Privacy-Preserving Proofs on Authenticated Data. In: 2015 IEEE Symposium on Security and Privacy

Backes M., Fiore D., Reischuk R.M.: Verifiable delegation of computation on outsourced data. In: Sadeghi A.-R., Gligor V.D., Yung M. (eds.) ACM CCS 13, pp. 863–874. ACM Press (2013)

Benabbas, S., Gennaro, R., Vahlis, Y.: Verifiable delegation of computation over large datasets. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 111–131. Springer, Heidelberg (2011)

Ben-Sasson, E., Chiesa, A., Genkin, D. Tromer, E.: ‘SNARKs for C: Verifying program executions succinctly and in zero knowledge’. In: Advances in Cryptology-CRYPTO 2013, Santa Barbara, pp. 90–108 (2013)

10.

Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: ‘Succinct non-interactive zero knowledge for a von Neumann architecture’, In: 23rd USENIX Security Symposium, pp. 781–796, San Diego (2014)

11.

Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: ITCS, pp. 326–349 (2012)

12.

Boneh, D., Freeman, D.M.: Homomorphic signatures for polynomial functions. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 149–168. Springer, Heidelberg (2011)

13.

Boneh, D., Freeman, D.M., Katz, J., Waters, B.: Signing a linear subspace: signature schemes for network coding. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 68–87. Springer, Heidelberg (2009)

14.

Braun, B., Feldman, A, J., Ren, Z., et al.: Verifying computations with state. In: 24th ACM Symposium on Operating Systems Principles. Farminton, pp. 341–357 (2013)

15.

Meyer, Carl: Matrix Analysis and Applied Linear Algebra Book and Solutions Manual, vol. 2, Society for Industrial and Applied Mathematics (2000)

16.

Catalano, D., Fiore, D.: Practical homomorphic MACs for arithmetic circuits. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 336–352. Springer, Heidelberg (2013)

17.

Catalano, D., Fiore, D., Gennaro, R., Vamvourellis, K.: Algebraic (Trapdoor) One-way functions and their applications. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 680–699. Springer, Heidelberg (2013)

18.

Chapman, C., Emmerich, W., Marquez, F.G., Clayman, S., Galis, A.: Software architecture definition for on-demand cloud provisioning. Clust. Comput. 15(2), 79–100 (2012)CrossRef

19.

Chaum, D., Pedersen, T.P.: Wallet databases with observers. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 89–105. Springer, Heidelberg (1993)

20.

Chen, X., Huang, X., Li, J., Ma, J., Lou, W., Wong, D.S.: New algorithms for secure outsourcing of large-scale systems of linear equations. IEEE Trans. Inf. Forensics Secur. 10(1), 69–78 (2015)CrossRef

21.

Cheng, T.Y., Jia, X.: Compressive traffic monitoring in hybrid SDN. IEEE J. Selected Areas Commun. 36(12), 2731–2743 (2018)CrossRef

22.

Chung, K.-M., Kalai, Y.T., Liu, F.-H., Raz, R.: Memory Delegation. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 151–168. Springer, Heidelberg (2011)

23.

Chung, K.-M., Kalai, Y., Vadhan, S.P.: Improved delegation of computation using fully homomorphic encryption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 483–501. Springer, Heidelberg (2010)

24.

Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. In: 3rd Innovations in Theoretical Computer Science Conference, Cambridge, pp. 90–112 (2012)

25.

Fiore, D., Gennaro, R.: Publicly verifiable delegation of large polynomials and matrix computations, with applications. In: Yu, T., Danezis, G., Gligor, V.D. (eds.) ACM CCS 2012, pp. 501–512. ACM Press (2012)

26.

Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: outsourcing computation to untrusted workers. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 465–482. Springer, Heidelberg (2010)

27.

Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626–645. Springer, Heidelberg (2013)

28.

Gennaro, R., Wichs, D.: Fully homomorphic message authenticators. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8270, pp. 301–320. Springer, Heidelberg (2013)

29.

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC 2009, pp. 169–178. ACM, New York (2009)

30.

Seber, George A.F., Lee, Alan J.: Linear Regression Analysis, vol. 936. Wiley, Hoboken (2012)MATH

31.

Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Fortnow, L., Vadhan, S.P. (eds.) 43rd ACM STOC, pp. 99–108. ACM Press (2011)

32.

Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 113– 122. ACM Press (2008)

33.

Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems (extended abstract). In: STOC, pp. 291–304 (1985)

34.

Golle, P., Mironov, I.: Uncheatable distributed computations. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 425–440. Springer, Heidelberg (2001)

35.

Gorbunov, S., Vaikuntanathan, V., Wichs, D.: Leveled fully homomorphic signatures from standard lattices. In: STOC, pp. 469–477 (2015)

36.

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 CCS, pp. 89–98 (2006)

37.

Hohenberger, S., Lysyanskaya, A.: How to securely outsource cryptographic computations. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 264–282. Springer, Heidelberg (2005)

38.

Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: STOC, pp. 723–732 (1992)

39.

Kilian, J.: Improved efficient arguments. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 311–324. Springer, Heidelberg (1995)

40.

Lei, X., Liao, X., Huang, T., Heriniaina, F.: Achieving security, robust cheating resistance, and high-efficiency for outsourcing large matrix multiplication computation to a malicious cloud. Inf. Sci. 280, 205–217 (2014)CrossRef

41.

Lei, X., Liao, X., Huang, T., Li, H.: Cloud computing service: the case of large matrix determinant computation. IEEE Trans. Serv. Comput. 8(5), 688–700 (2015)CrossRef

42.

Lei, X., Liao, X., Huang, T., Li, H., Hu, C.: Outsourcing large matrix inversion computation to a public cloud. IEEE Trans. Cloud Comput. 1, 78–87 (2013)

43.

Mohammadi, Mehdi, Raahemi, Bijan, Akbari, Ahmad, Nassersharif, Babak, Moeinzadeh, Hossein: Improving linear discriminant analysis with artificial immune system-based evolutionary algorithms. Inform. Sci. 189, 219–232 (2012)CrossRef

44.

Mell, P., Grance, T.: The NIST Definition of Cloud Computing, pp. 145–800. NIST, Special Publication, Gaithersburg (2011)

45.

Micali, S.: CS proofs. In: FOCS, pp. 436–453 (1994)

46.

Naor, M., Pinkas, B.: Oblivious polynomial evaluation. SIAM J. Comput. 35(5), 1254–1281 (2006)MathSciNetCrossRef

47.

Papamanthou, C., Shi, E., Tamassia, R.: Signatures of correct computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 222–242. Springer, Heidelberg (2013)

48.

Parno, B., Howell, J., Gentry, C., et al.: Pinocchio: nearly practical verifiable computation, security and privacy. pp. 238–252. Berkeley (2013)

49.

Parno, B., Raykova, M., Vaikuntanathan, V.: How to delegate and verify in public: verifiable computation from attribute-based encryption. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 422–439. Springer, Heidelberg (2012)

50.

Gonzalez, R.C., Woods, R.E.: Digital Image Processing, 3rd edn. Prentice-Hall, Inc., Upper Saddle River (2006)

51.

Sahai, A., Waters, B.: Fuzzy identity-based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457–473. Springer, Heidelberg (2005)

52.

Gibson, Sarah F.F., Mirtich, Brian: A survey of deformable modeling in computer graphics, Technical Report TR-97-19 (1997)

53.

Setty, S., Braun, B., Vu, V., et al.: Resolving the conflict between generality and plausibility in verified computation. In: 8th ACM European Conference on Computer Systems, pp. 71–84. Czech Republic, Prague (2013)

54.

Setty, S., McPherson, R., Blumberg, A. J., Walfish, M.: Making argument systems for outsourced computation practical (sometimes). In: NDSS Symposium 2012, San Diego, pp. 17 (2012)

55.

Setty, S., Vu, V., Panpalia, N., et al.: Taking proof-based verified computation a few steps closer to practicality. In: 21st USENIX Security Symposium, pp. 253–268. Bellevue (2012)

56.

Tao, R., Meng, X.Y., Wang, Y.: Image encryption with multiorders of fractional Fourier transforms. IEEE Trans. Inf. Forensic. Secur. 5(4), 734–738 (2010)CrossRef

57.

Thaler, J.: Time-optimal interactive proofs for circuit evaluation. In: Advances in Cryptology-CRYPTO 2013, Santa Barbara, pp. 71–89 (2013)

58.

Thaler, J., Roberts, M., Mitzenmacher, M., et al.: Verifiable computation with massively parallel interactive proofs. In: 4th USENIX Workshop on Hot Topics in Cloud Computing, pp. 22–28, Boston (2012)

59.

Vu, V., Setty, S., Blumberg, A.J., Walfish, M.: A hybrid architecture for interactive verifiable computation, Security and Privacy, pp. 223–237. San Francisco (2013)

60.

Wahby, R.S., Setty, S., Ren, Z., Blumberg, A.J., Walfish, M.: Efficient RAM and control flow in verifiable outsourced computation. The 2015 Network and Distributed System Security. San Diego (2015)

61.

Wu, Y., Liu, M., Xue, R., Zhang, R.: Attribute-based multi-function verifiable computation. Future Gener. Comput. Syst. 78, 995–1004 (2018)CrossRef

62.

Zhu, Z.L., Zhang, W., Wong, K.W., Yu, H.: A chaos-based symmetric image encryption scheme using a bit-level permutation. Inform. Sci. 181(6), 1171–1186 (2011)CrossRef

Titel: Multi-matrix verifiable computation
verfasst von: Yan He
Liang Feng Zhang
Publikationsdatum: 16.05.2020
Verlag: Springer US
Erschienen in: Cluster Computing / Ausgabe 1/2021
Print ISSN: 1386-7857
Elektronische ISSN: 1573-7543
DOI: https://doi.org/10.1007/s10586-020-03116-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2021

Collective periodic pattern discovery for understanding human mobility

SDN-based server clusters with dynamic load balancing and performance improvement

Retraction Note to: Mobile network intrusion detection for IoT system based on transfer learning algorithm

Energy-saving traffic scheduling in backbone networks with software-defined networks

Blockchain technology in supply chain management: an empirical study of the factors affecting user adoption/acceptance

Resource provisioning using workload clustering in cloud computing environment: a hybrid approach

Premium Partner