Abstract
With the emergence of cloud computing services, a resource-constrained client can outsource its computationally-heavy tasks to cloud providers. Because such service providers might not be fully trusted by the client, the need to verify integrity of the returned computation result arises. The ability to do so is called verifiable delegation or verifiable outsourcing. Furthermore, the data used in the computation may be sensitive and it is often desired to protect it from the cloud throughout the computation. In this work, we put forward solutions for verifiable outsourcing of matrix multiplications that favorably compare with the state of the art. Our goal is to minimize the cost of verifying the result without increasing overhead associated with other aspects of the scheme. In our scheme, the cost of verifying the result of computation uses only a single modulo exponentiation and the number of modulo multiplications linear in the size of the output matrix. This cost can be further reduced to avoid all cryptographic operations if the cloud is rational. A rational cloud is neither honest nor arbitrarily malicious, but rather economically motivated with the sole purpose of maximizing its monetary reward. We extend our core constructions with several desired features such as data protection, public verifiability, and computation chaining.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Matrix Multiplication
- Security Parameter
- Homomorphic Encryption
- Interactive Proof
- Cryptographic Operation
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
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, Part I. LNCS, vol. 6198, pp. 152–163. Springer, Heidelberg (2010)
Atallah, M., Blanton, M. (eds.): Algorithms and Theory of Computation Handbook. General Concepts and Techniques, vol. I, ch. 17. CRC Press (2009)
Atallah, M., Frikken, K.: Securely outsourcing linear algebra computations. In: ASIACCS, pp. 48–59 (2010)
Atallah, M., Frikken, K., Wang, S.: Private outsourcing of matrix multiplication over closed semi-rings. In: SECRYPT, pp. 136–144 (2012)
Azar, P.D., Micali, S.: Rational proofs. In: STOC, pp. 1017–1028 (2012)
Azar, P.D., Micali, S.: Super efficient rational proofs. In: EC, pp. 29–30 (2013)
Babai, L.: Trading group theory for randomness. In: STOC, pp. 421–429 (1985)
Backes, M., Fiore, D., Reischuk, R.M.: Verifiable delegation of computation on outsourced data. In: CCS, pp. 863–874 (2013)
Ballard, L., Green, M., Medeiros, B., Monrose, F.: Correlation-resistant storage via keyword-searchable encryption. Cryptology ePrint Archive 2005/417 (2005)
Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005)
Bresson, E., Chevassut, O., Pointcheval, D.: Dynamic group diffie-hellman key exchange under standard assumptions. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 321–336. Springer, Heidelberg (2002)
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)
CertiVox. Benchmarks and Subs performance for MIRACL library, https://certivox.org/display/EXT/Benchmarks+and+Subs
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)
Chung, K.-M., Kalai, Y., Vadhan, S.: Improved delegation of computation using fully homomorphic encryption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 483–501. Springer, Heidelberg (2010)
Dodis, Y., Halevi, S., Rabin, T.: A cryptographic solution to a game theoretic problem. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 112–130. Springer, Heidelberg (2000)
Fiore, D., Gennaro, R.: Publicly verifiable delegation of large polynomials and matrix computations, with applications. In: CCS, pp. 501–512 (2012)
Garay, J., Katz, J., Maurer, U., Tackmann, B., Zikas, V.: Rational protocol design: Cryptography against incentive-driven adversaries. In: FOCS, pp. 648–657 (2013)
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)
Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: Interactive proofs for muggles. In: STOC, pp. 113–122 (2008)
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18(1), 186–208 (1989)
Guo, S., Hubáček, S., Rosen, A., Vald, M.: Rational arguments: Single round delegation with sublinear verification. In: ITCS, pp. 523–540 (2014)
Halpern, J., Teague, V.: Rational secret sharing and multiparty computation: Extended abstract. In: STOC, pp. 623–632 (2004)
Johnson, R., Molnar, D., Song, D., Wagner, D.: Homomorphic signature schemes. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, pp. 244–262. Springer, Heidelberg (2002)
Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: STOC, pp. 723–732 (1992)
Kilian, J.: Improved efficient arguments (Preliminary version). In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 311–324. Springer, Heidelberg (1995)
Landerman, J., Pan, V., Sha, X.-H.: On practical algorithms for accelerated matrix mutiplication. Linear Algebra and Its Applications 162–164, 557–588
Micali, S.: CS proofs. In: FOCS, pp. 436–453 (1994)
Mohassel, P.: Efficient and secure delegation of linear algebra. Cryptology ePrint Archive 2011/605 (2011)
Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: Nearly practical verifiable computation. In: IEEE Symposium on Security and Privacy (2013)
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)
Zhang, L.F., Safavi-Naini, R.: Private outsourcing of polynomial evaluation and matrix multiplication using multilinear maps. In: Abdalla, M., Nita-Rotaru, C., Dahab, R. (eds.) CANS 2013. LNCS, vol. 8257, pp. 329–348. Springer, Heidelberg (2013)
Zhang, Y., Blanton, M.: Efficient secure and verifiable outsourcing of matrix multiplications. Cryptology ePrint Archive 2014/133 (2014)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Zhang, Y., Blanton, M. (2014). Efficient Secure and Verifiable Outsourcing of Matrix Multiplications. In: Chow, S.S.M., Camenisch, J., Hui, L.C.K., Yiu, S.M. (eds) Information Security. ISC 2014. Lecture Notes in Computer Science, vol 8783. Springer, Cham. https://doi.org/10.1007/978-3-319-13257-0_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-13257-0_10
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13256-3
Online ISBN: 978-3-319-13257-0
eBook Packages: Computer ScienceComputer Science (R0)