Abstract
We are interested in this problem: a verifier, with a small and reliable storage, wants to periodically check whether a remote server is keeping a large file x. A dishonest server, by adapting the challenges and responses, tries to discard partial information of x and yet evades detection. Besides the security requirements, there are considerations on communication, storage size and computation time. Juels et al. [10] gave a security model for Proof of Retrievability (\(\mathcal{POR}\)) system. The model imposes a requirement that the original x can be recovered from multiple challenges-responses. Such requirement is not necessary in our problem. Hence, we propose an alternative security model for Remote Integrity Check (\(\mathcal{RIC}\)). We study a few schemes and analyze their efficiency and security. In particular, we prove the security of a proposed scheme HENC. This scheme can be deployed as a \(\mathcal{POR}\) system and it also serves as an example of an effective \(\mathcal{POR}\) system whose “extraction” is not verifiable. We also propose a combination of the RSA-based scheme by Filho et al. [7] and the ECC-based authenticator by Naor et al. [12], which achieves good asymptotic performance. This scheme is not a \(\mathcal{POR}\) system and seems to be a secure \(\mathcal{RIC}\). In-so-far, all schemes that have been proven secure can also be adopted as \(\mathcal{POR}\) systems. This brings out the question of whether there are fundamental differences between the two models. To highlight the differences, we introduce a notion, trap-door compression, that captures a property on compressibility.
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
Androutsellis-Theotokis, S., Spinellis, D.: A survey of peer-to-peer content distribution technologies. ACM Comput. Surv. 36(4), 335–371 (2004)
Ateniese, G., Burns, R., Curtmola, R., Herring, J., Kissner, L., Peterson, Z., Song, D.: Provable data possession at untrusted stores. In: ACM conf. on Computer and Communications Security, pp. 598–609 (2007)
Batten, C., Barr, K., Saraf, A., Treptin, S.: pStore: A secure peer-to-peer backup system. LCS Technical Memo 632, MIT Laboratory for Computer Science (2001)
Blum, M., Evans, W., Gemmell, P., Kannan, S., Naor, M.: Checking the correctness of memories. In: IEEE Sym. on Foundations of Comp. Sci, pp. 90–99 (1991)
Bowers, K.D., Juels, A., Oprea, A.: Proofs of retrievability: Theory and implementation. Cryptology ePrint Archive, Report 2008/175 (2008)
Chang, E.-C., Mukhopadhyay, S., Xu, J.: Remote integrity check without the original. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, p. 2007. Springer, Heidelberg (manuscript submitted, 2007), http://www.comp.nus.edu.sg/~changec/publications/remote.pdf
Filho, D., Barreto, P.: Demonstrating data possession and uncheatable data transfer. Cryptology ePrint Archive, Report 2006/150 (2006)
Harnik, D., Naor, M.: On the Compressibility of NP Instances and Cryptographic Applications. In: IEEE Sym. on Foundations of Comp. Sci, pp. 719–728 (2006)
Johnson, R., Molnar, D., Song, D.X., Wagner, D.: Homomorphic Signature Schemes. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, pp. 244–262. Springer, Heidelberg (2002)
Juels, A., Kaliski Jr., B.S.: Pors: proofs of retrievability for large files. In: ACM conf. on Computer and Communications Security, pp. 584–597 (2007)
Li, J., Dabek, F.: F2F: reliable storage in open networks. In: Intern. Workshop on Peer-to-Peer Systems (2006)
Naor, M., Rothblum, G.N.: The Complexity of Online Memory Checking. In: IEEE Symp. on Foundations of Comp. Sci., pp. 573–584 (2005)
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)
Shacham, H., Waters, B.: Compact proofs of retrievability. Cryptology ePrint Archive, Report 2008/073 (2008), http://eprint.iacr.org/
Suh, G.E., Clarke, D., Gasend, B., van Dijk, M., Devadas, S.: Efficient memory integrity verification and encryption for secure processors. In: IEEE/ACM Int. Sym. on Microarchitecture, pp. 339–350 (2003)
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
Chang, EC., Xu, J. (2008). Remote Integrity Check with Dishonest Storage Server. In: Jajodia, S., Lopez, J. (eds) Computer Security - ESORICS 2008. ESORICS 2008. Lecture Notes in Computer Science, vol 5283. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-88313-5_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-88313-5_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-88312-8
Online ISBN: 978-3-540-88313-5
eBook Packages: Computer ScienceComputer Science (R0)