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
Published in:
Blending FHE-NTRU Keys – The Excalibur Property Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Verifiable Computation for Randomized Algorithm

Authors : Muhua Liu, Ying Wu, Rui Xue

Published in: Progress in Cryptology – INDOCRYPT 2016

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

Verifiable computation enables a computationally weak client to delegate the difficult computation to a more powerful cloud server. When the client receives the returned result, it can verify the correctness of the result. As a new computing model, it has been widely studied. But, the previous works on verifiable computation was restricted to the case where the target function was deterministic.
In this paper, we present a novel definition for verifiable computation supporting randomized algorithms, which allows a resource constrained client to outsource the computation of a randomized algorithm to an untrusted server. We consider a new setting where the random string, as the random input of the randomized algorithm, is generated by the cloud server. In our security definition, it must guarantee that the server can not tamper with the randomness which means that the generated string is indistinguishable with a truly random string. Our construction is based on indistinguishability obfuscation, constrained verifiable random function and functional pseudorandom function.

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
previous chapter CRT-Based Outsourcing Algorithms for Modular Exponentiations
next chapter UC-secure and Contributory Password-Authenticated Group Key Exchange
Appendix
Available only for authorised users
Footnotes
1
It means that for all \(i\in [t]\), \(y_i\ne \bot \), where \(y_i\) is the ith component of the vector \(\hat{\varvec{y}}\).
 
Literature
1.
Alwen, J., Barbosa, M., Farshim, P., Gennaro, R., Gordon, S.D., Tessaro, S., Wilson, D.A.: On the relationship between functional encryption, obfuscation, and fully homomorphic encryption. In: Proceedings of 14th IMA International Conference on Cryptography and Coding, IMACC 2013, Oxford, UK, 17–19 December 2013, pp. 65–84 (2013)
2.
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). doi:10.​1007/​978-3-642-14165-2_​14 CrossRef
3.
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001). doi:10.​1007/​3-540-44647-8_​1 CrossRef
4.
Barbosa, M., Farshim, P.: Delegatable homomorphic encryption with applications to secure outsourcing of computation. In: Dunkelman, O. (ed.) CT-RSA 2012. LNCS, vol. 7178, pp. 296–312. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-27954-6_​19 CrossRef
5.
6.
7.
8.
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). doi:10.​1007/​978-3-642-14623-7_​26 CrossRef
9.
Fiore, D., Gennaro, R.: Publicly verifiable delegation of large polynomials and matrix computations, with applications. In: The ACM Conference on Computer and Communications Security, CCS 2012, Raleigh, NC, USA, 16–18 October 2012, pp. 501–512 (2012)
10.
Fiore, D., Gennaro, R., Pastro, V.: Efficiently verifiable computation on encrypted data. In: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, AZ, USA, 3–7 November 2014, pp. 844–855 (2014)
11.
12.
Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26–29 October 2013, Berkeley, CA, USA, pp. 40–49 (2013)
13.
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). doi:10.​1007/​978-3-642-14623-7_​25 CrossRef
14.
Gentry, C., Halevi, S., Raykova, M., Wichs, D.: Outsourcing private RAM computation. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, 18–21 October 2014, pp. 404–413 (2014)
15.
Goldwasser, S., Gordon, S.D., Goyal, V., Jain, A., Katz, J., Liu, F.-H., Sahai, A., Shi, E., Zhou, H.-S.: Multi-input functional encryption. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 578–602. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-55220-5_​32 CrossRef
16.
Gordon, S.D., Katz, J., Liu, F., Shi, E., Zhou, H.: Multi-client verifiable computation with stronger security guarantees. IACR Cryptol. ePrint Arch. 2015, 142 (2015)MathSciNetMATH
17.
Goyal, V., Jain, A., Koppula, V., Sahai, A.: Functional encryption for randomized functionalities. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 325–351. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46497-7_​13 CrossRef
18.
Komargodski, I., Segev, G., Yogev, E.: Functional encryption for randomized functionalities in the private-key setting from minimal assumptions. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 352–377. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46497-7_​14 CrossRef
19.
20.
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). doi:10.​1007/​978-3-642-28914-9_​24 CrossRef
Metadata
Title
Verifiable Computation for Randomized Algorithm
Authors
Muhua Liu
Ying Wu
Rui Xue
Copyright Year
2016
Book
Progress in Cryptology – INDOCRYPT 2016

Print ISBN: 978-3-319-49889-8

Electronic ISBN: 978-3-319-49890-4

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-49890-4_6

Premium Partner

    Image Credits