Abstract
In a proof-of-retrievability system, a data storage center convinces a verifier that he is actually storing all of a client’s data. The central challenge is to build systems that are both efficient and provably secure—that is, it should be possible to extract the client’s data from any prover that passes a verification check. In this paper, we give the first proof-of-retrievability schemes with full proofs of security against arbitrary adversaries in the strongest model, that of Juels and Kaliski. Our first scheme, built from BLS signatures and secure in the random oracle model, has the shortest query and response of any proof-of-retrievability with public verifiability. Our second scheme, which builds elegantly on pseudorandom functions (PRFs) and is secure in the standard model, has the shortest response of any proof-of-retrievability scheme with private verifiability (but a longer query). Both schemes rely on homomorphic properties to aggregate a proof into one small authenticator value.
Chapter PDF
Similar content being viewed by others
Keywords
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
Ateniese, G., Burns, R., Curtmola, R., Herring, J., Kissner, L., Peterson, Z., Song, D.: Provable data possession at untrusted stores. In: De Capitani di Vimercati, S., Syverson, P. (eds.) Proceedings of CCS 2007, pp. 598–609. ACM Press, New York (2007)
Ateniese, G., Burns, R., Curtmola, R., Herring, J., Kissner, L., Peterson, Z., Song, D.: Provable data possession at untrusted stores. Cryptology ePrint Archive, Report 2007/202 (2007), http://eprint.iacr.org/ (Version December 7, 2007); (visited February 10, 2008)
Ateniese, G., Di Pietro, R., Mancini, L., Tsudik, G.: Scalable and efficient provable data possession. In: Liu, P., Molva, R. (eds.) Proceedings of SecureComm 2008. ICST (September 2008) (to appear)
Barreto, P., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 319–331. Springer, Heidelberg (2006)
Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. J. Cryptology 17(4), 297–319 (2001); Extended abstract. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–533. Springer, Heidelberg (2001)
Bowers, K.D., Juels, A., Oprea, A.: Proofs of retrievability: Theory and implementation. Cryptology ePrint Archive, Report 2008/175 (2008), http://eprint.iacr.org/
Cramer, R., Hanaoka, G., Hofheinz, D., Imai, H., Kiltz, E., Pass, R., Shelat, A., Vaikuntanathan, V.: Bounded CCA2-secure encryption. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 502–518. Springer, Heidelberg (2007)
Deswarte, Y., Quisquater, J.-J., Saïdane, A.: Remote integrity checking. In: Jajodia, S., Strous, L. (eds.) Proceedings of IICIS 2003. IFIP, vol. 140, pp. 1–11. Kluwer Academic, Dordrecht (2004)
Filho, D., Barreto, P.: Demonstrating data possession and uncheatable data transfer. Cryptology ePrint Archive, Report 2006/150 (2006), http://eprint.iacr.org/
Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. Cryptology ePrint Archive, Report 2006/372 (2006), http://eprint.iacr.org/
Heng, S.-H., Kurosawa, K.: k-resilient identity-based encryption in the standard model. CT-RSA 2004 E89-A.1(1), 39–46 (2006); Originally published at CT-RSA 2004
Juels, A., Kaliski, B.: PORs: Proofs of retrievability for large files. In: De Capitani di Vimercati, S., Syverson, P. (eds.) Proceedings of CCS 2007, pp. 584–597. ACM Press, New York (2007), http://www.rsa.com/rsalabs/staff/bios/ajuels/publications/pdfs/POR-preprint-August07.pdf
Lillibridge, M., Elnikety, S., Birrell, A., Burrows, M., Isard, M.: A cooperative Internet backup scheme. In: Noble, B. (ed.) Proceedings of USENIX Technical 2003. USENIX, pp. 29–41 (June 2003)
Naor, M., Rothblum, G.: The complexity of online memory checking. In: Tardos, E. (ed.) Proceedings of FOCS 2005, pp. 573–584. IEEE Computer Society, Los Alamitos (2005)
Schwarz, T., Miller, E.: Store, forget, and check: Using algebraic signatures to check remotely administered storage. In: Ahamad, M., Rodrigues, L. (eds.) Proceedings of ICDCS 2006. IEEE Computer Society, Los Alamitos (July 2006)
Shacham, H., Waters, B.: Compact proofs of retrievability. Cryptology ePrint Archive, Report 2008/073 (2008), http://eprint.iacr.org/
Shah, M., Swaminathan, R., Baker, M.: Privacy-preserving audit and extraction of digital contents. Cryptology ePrint Archive, Report 2008/186 (2008), http://eprint.iacr.org/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shacham, H., Waters, B. (2008). Compact Proofs of Retrievability. In: Pieprzyk, J. (eds) Advances in Cryptology - ASIACRYPT 2008. ASIACRYPT 2008. Lecture Notes in Computer Science, vol 5350. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-89255-7_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-89255-7_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-89254-0
Online ISBN: 978-3-540-89255-7
eBook Packages: Computer ScienceComputer Science (R0)