Abstract
Publicly Verifiable Outsourced Computation (PVC) allows weak devices to delegate computations to more powerful servers, and to verify the correctness of results. Delegation and verification rely only on public parameters, and thus PVC lends itself to large multi-user systems where entities need not be registered. In such settings, individual user requirements may be diverse and cannot be realised with current PVC solutions. In this paper, we introduce Hybrid PVC (HPVC) which, with a single setup stage, provides a flexible solution to outsourced computation supporting multiple modes: (i) standard PVC, (ii) PVC with cryptographically enforced access control policies restricting the servers that may perform a given computation, and (iii) a reversed model of PVC which we call Verifiable Delegable Computation (VDC) where data is held remotely by servers. Entities may dynamically play the role of delegators or servers as required.
J. Alderman—Partial funding by the European Commission under project H2020-644024 “CLARUS”, and support from BAE Systems Advanced Technology Centre is gratefully acknowledged.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
These descriptive labels (e.g. field names in a database) allow delegators to select data points to be used in a computation without knowing the data values.
- 2.
- 3.
This restriction was also used in [6] for revocable KP-ABE, and could be removed if an adaptive, indirectly revocable ABE scheme is found.
- 4.
In contrast to prior modes where X was a single data point, F now takes |X| inputs.
- 5.
Either by defining a large enough \(\mathcal {U}_x\) or by hashing strings to elements of the attribute group. Unlike prior schemes [3, 20], we include an identifier of the data X (based on the label \(l({x_{i,j}})\)) in the attribute mapping to specify the data items to be used; alternatively, \(D_i\) could be a long bitstring formed by concatenating each data point, and the labels should identify the attributes corresponding to each data point.
- 6.
Our KDC will act as the trusted KeyGen authority already inherent in ABE schemes.
References
Alderman, J., Janson, C., Cid, C., Crampton, J.: Access control in publicly verifiable outsourced computation. In: Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security, ASIA CCS 2015, New York, pp. 657–662. ACM (2015)
Alderman, J., Janson, C., Cid, C., Crampton, J.: Hybrid publicly verifiable computation. Cryptology ePrint Archive, Report/320, 2015 (2015)
Alderman, J., Janson, C., Cid, C., Crampton, J.: Revocation in publicly verifiable outsourced computation. In: Lin, D., Yung, M., Zhou, J. (eds.) Inscrypt 2014. LNCS, vol. 8957, pp. 51–71. Springer, Heidelberg (2015)
Pasalic, E., Knudsen, E.R. (eds.): Cryptography and Information Security in the Balkans. LNCS, vol. 9540. Springer, Switzerland (2016)
Apon, D., Katz, J., Shi, E., Thiruvengadam, A.: Verifiable oblivious storage. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 131–148. Springer, Heidelberg (2014)
Attrapadung, N., Imai, H.: Attribute-based encryption supporting direct/indirect revocation modes. In: Parker, M.G. (ed.) Cryptography and Coding. LNCS, vol. 5921, pp. 278–300. Springer, Heidelberg (2009)
Backes, M., Barbosa, M., Fiore, D., Reischuk, R.M.: ADSNARK: nearly practical and privacy-preserving proofs on authenticated data. In: IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, May 17–21, 2015, pp. 271–286. IEEE Computer Society (2015)
Backes, M., Fiore, D., Reischuk, R.M.: Verifiable delegation of computation on outsourced data. In: Proceedings of the ACM SIGSAC Conference on Computer & Communications Security, CCS 2013, New York, pp. 863–874. ACM (2013)
Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: Fast reductions from rams to delegatable succinct constraint satisfaction problems: extended abstract. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS 2013, New York, pp. 401–414. ACM (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)
Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 2012, New York, pp. 326–349. ACM (2012)
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)
Choi, S.G., Katz, J., Kumaresan, R., Cid, C.: Multi-client non-interactive verifiable computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 499–518. Springer, Heidelberg (2013)
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)
Fiore, D., Gennaro, R.: Publicly verifiable delegation of large polynomials and matrix computations, with applications. In: Yu, T., Danezis, G., Gligor, V.D. (eds.) The ACM Conference on Computer and Communications Security, CCS 2012, Raleigh, October 16–18, pp. 501–512. ACM (2012)
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)
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)
Ostrovsky, R., Sahai, A., Waters, B.: Attribute-based encryption with non-monotonic access structures. In: Proceedings of the 14th ACM Conference on Computer and Communications Security, CCS 2007, New York, pp. 195–203. ACM (2007)
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)
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)
Shi, J., Lai, J., Li, Y., Deng, R.H., Weng, J.: Authorized keyword search on encrypted data. In: Kutyłowski, M., Vaidya, J. (eds.) ICAIS 2014, Part I. LNCS, vol. 8712, pp. 419–435. Springer, Heidelberg (2014)
van den Hooff, J., Kaashoek, M.F., Zeldovich, N.: Versum: verifiable computations over large public logs. In: Ahn, G., Yung, M., Li, N. (eds.) Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, November 3–7, 2014, pp. 1304–1316. ACM (2014)
Waters, B.: Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 53–70. Springer, Heidelberg (2011)
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)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Alderman, J., Janson, C., Cid, C., Crampton, J. (2016). Hybrid Publicly Verifiable Computation. In: Sako, K. (eds) Topics in Cryptology - CT-RSA 2016. CT-RSA 2016. Lecture Notes in Computer Science(), vol 9610. Springer, Cham. https://doi.org/10.1007/978-3-319-29485-8_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-29485-8_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-29484-1
Online ISBN: 978-3-319-29485-8
eBook Packages: Computer ScienceComputer Science (R0)