Kevin D. Bowers
ABSTRACT
We introduce HAIL (High-Availability and Integrity Layer), a distributed cryptographic system that allows a set of servers to prove to a client that a stored file is intact and retrievable. HAIL strengthens, formally unifies, and streamlines distinct approaches from the cryptographic and distributed-systems communities. Proofs in HAIL are efficiently computable by servers and highly compact---typically tens or hundreds of bytes, irrespective of file size. HAIL cryptographically verifies and reactively reallocates file shares. It is robust against an active, mobile adversary, i.e., one that may progressively corrupt the full set of servers. We propose a strong, formal adversarial model for HAIL, and rigorous analysis and parameter choices. We show how HAIL improves on the security and efficiency of existing tools, like Proofs of Retrievability (PORs) deployed on individual servers. We also report on a prototype implementation.
- Amazon.com. Amazon simple storage service (Amazon S3), 2009. Referenced 2009 at aws.amazon.com/s3.Google Scholar
- G. Ateniese, R. Burns, R. Curtmola, J. Herring, L. Kissner, Z. Peterson, and D. Song. Provable data possession at untrusted stores. In 14th ACM CCS, pages 598--609, 2007. Google ScholarDigital Library
- G. Ateniese, R. Di Pietro, L. V. Mancini, and G. Tsudik. Scalable and efficient provable data possession, 2008. IACR ePrint manuscript 2008/114.Google Scholar
- J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway. UMAC: Fast and secure message authentication. In CRYPTO, volume 1666 of LNCS, pages 216--233, 1999. Google ScholarDigital Library
- K. D. Bowers, A. Juels, and A Oprea. HAIL: A high-availability and integrity layer for cloud storage, 2008. IACR ePrint manuscript 2008/489.Google Scholar
- K. D. Bowers, A. Juels, and A Oprea. Proofs of retrievability: Theory and implementation, 2008. IACR ePrint manuscript 2008/175.Google Scholar
- C. Cachin, K. Kursawe, A. Lysyanskaya, and R. Strobl. Asynchronous verifiable secret sharing and proactive cryptosystems. In 9th ACM CCS, pages 88--97, 2002. Google ScholarDigital Library
- C. Cachin and S. Tessaro. Asynchronous verifiable information dispersal. In 24th IEEE SRDS, pages 191--202, 2005. Google ScholarDigital Library
- L. Carter and M. Wegman. Universal hash functions. Journal of Computer and System Sciences, 18(3), 1979.Google Scholar
- R. Curtmola, O. Khan, and R. Burns. Robust remote data checking. In 4th ACM StorageSS, pages 63--68, 2008. Google ScholarDigital Library
- R. Curtmola, O. Khan, R. Burns, and G. Ateniese. MR--PDP: Multiple-replica provable data possession. In 28th IEEE ICDCS, pages 411--420, 2008. Google ScholarDigital Library
- Y. Dodis, S. Vadhan, and D. Wichs. Proofs of retrievability via hardness amplification. In 6th IACR TCC, volume 5444 of LNCS, pages 109--127, 2009. Google ScholarDigital Library
- C. Erway, A. Kupcu, C. Papamanthou, and R. Tamassia. Dynamic provable data possession. In 16th ACM CCS, 2009. To appear. Google ScholarDigital Library
- M. Etzel, S. Patel, and Z. Ramzan. SQUARE HASH: Fast message authentication via optimized universal hash functions. In CRYPTO, volume 1666 of LNCS, pages 234--251, 1999. Google ScholarDigital Library
- D.L.G. Filho and P.S.L.M. Barreto. Demonstrating data possession and uncheatable data transfer, 2006. IACR eArchive 2006/150.Google Scholar
- J. A. Garay, R. Gennaro, C. Jutla, and T. Rabin. Secure distributed storage and retrieval. Theoretical Computer Science, 243(1--2):363--389, 2000. Google ScholarDigital Library
- G. R. Goodson, J. J. Wylie, G. R. Ganger, and M. K. Reiter. Efficient byzantine-tolerant erasure-coded storage. In 34th IEEE DSN, pages 135--144, 2004. Google ScholarDigital Library
- P. Gopalan, R.J. Lipton, and Y.Z. Ding. Error correction against computationally bounded adversaries, 2004. Manuscript.Google Scholar
- S. Halevi and H. Krawczyk. MMH: Software message authentication in the Gbit/second rates. In Fast Software Encryption, volume 1267 of LNCS, pages 172--189, 1997. Google ScholarDigital Library
- J. Hendricks, G. R. Ganger, and M. K. Reiter. Verifying distributed erasure-coded data. In 26th ACM PODC, pages 139--146, 2007. Google ScholarDigital Library
- A. Herzberg, M. Jakobsson, H. Krawczyk, and M. Yung. Proactive public key and signature systems. In 4th ACM CCS, pages 100--110, 1997. Google ScholarDigital Library
- A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung. Proactive secret sharing, or: How to cope with perpetual leakage. In CRYPTO, volume 1963 of LNCS, pages 339--352, 1995. Google ScholarDigital Library
- A. Juels and B. Kaliski. PORs: Proofs of retrievability for large files. In 14th ACM CCS, pages 584--597, 2007. Google ScholarDigital Library
- H. Krawczyk. LFSR-based hashing and authentication. In CRYPTO, volume 839 of LNCS, pages 129--139, 1994. Google ScholarDigital Library
- M. Lillibridge, S. Elnikety, A. Birrell, M. Burrows, and M. Isard. A cooperative Internet backup scheme. In USENIX Annual Technical Conference, pages 29--41, 2003. Google ScholarDigital Library
- S. Micali, C. Peikert, M. Sudan, and D. Wilson. Optimal error correction against computationally bounded noise. In TCC, pages 1--16. Google ScholarDigital Library
- M. Naor and G. N. Rothblum. The complexity of online memory checking. In 46th IEEE FOCS, pages 573--584, 2005. Google ScholarDigital Library
- W. Nevelsteen and B. Preneel. Software performance of universal hash functions. In EUROCRYPT, volume 1233 of LNCS, pages 24--41, 1997. Google ScholarDigital Library
- J. S. Plank, J. Luo, C. D. Schuman, L. Xu, and Z. W. O'Hearn. A performance evaluation and examination of open-source erasure coding libraries for storage. In 7th USENIX FAST, pages 253--265, 2009. Google ScholarDigital Library
- P. Rogaway. Bucket hashing and its application to fast message authentication. In CRYPTO, volume 963 of LNCS, pages 29--42, 1995. Google ScholarDigital Library
- T. J. E. Schwarz and E. L. Miller. Store, forget, and check: Using algebraic signatures to check remotely administered storage. In 26th IEEE ICDCS, page 12, 2006. Google ScholarDigital Library
- H. Shacham and B. Waters. Compact proofs of retrievability. In ASIACRYPT, volume 5350 of LNCS, pages 90--107, 2008. Google ScholarDigital Library
- M. A. Shah, M. Baker, J. C. Mogul, and R. Swaminathan. Auditing to keep online storage services honest. In 11th USENIX HotOS, pages 1--6, 2007. Google ScholarDigital Library
- V. Shoup. On fast and provably secure message authentication based on universal hashing. In CRYPTO, volume 1109 of LNCS, pages 313--328, 1996. Google ScholarDigital Library
- M. Wegman and L. Carter. New hash functions and their use in authentication and set equality. Journal of Computer and System Sciencies, 22(3):265--279, 1981.Google ScholarCross Ref
Index Terms
- HAIL: a high-availability and integrity layer for cloud storage
Recommendations
Proofs of retrievability: theory and implementation
CCSW '09: Proceedings of the 2009 ACM workshop on Cloud computing securityA proof of retrievability (POR) is a compact proof by a file system (prover) to a client (verifier) that a target file F is intact, in the sense that the client can fully recover it. As PORs incur lower communication complexity than transmission of F ...
Towards efficient proofs of retrievability
ASIACCS '12: Proceedings of the 7th ACM Symposium on Information, Computer and Communications SecurityProofs of Retrievability (POR) is a cryptographic formulation for remotely auditing the integrity of files stored in the cloud, without keeping a copy of the original files in local storage. In a POR scheme, a user Alice backups her data file together ...
Proofs of retrievability with public verifiability and constant communication cost in cloud
Cloud Computing '13: Proceedings of the 2013 international workshop on Security in cloud computingFor data storage outsourcing services, it is important to allow data owners to efficiently and securely verify that the storage server stores their data correctly. To address this issue, several proof-of-retrievability (POR) schemes have been proposed ...
Comments