Abstract
Proofs of storage (PoS) are interactive protocols allowing a client to verify that a server faithfully stores a file. Previous work has shown that proofs of storage can be constructed from any homomorphic linear authenticator (HLA). The latter, roughly speaking, are signature/message authentication schemes where ‘tags’ on multiple messages can be homomorphically combined to yield a ‘tag’ on any linear combination of these messages.
We provide a framework for building public-key HLAs from any identification protocol satisfying certain homomorphic properties. We then show how to turn any public-key HLA into a publicly-verifiable PoS with communication complexity independent of the file length and supporting an unbounded number of verifications. We illustrate the use of our transformations by applying them to a variant of an identification protocol by Shoup, thus obtaining the first unbounded-use PoS based on factoring (in the random oracle model).
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: ACM Conference on Computer and Communications Security. ACM, New York (2007)
Ateniese, G., Di Pietro, R., Mancini, L.V., Tsudik, G.: Scalable and efficient provable data possession. In: Proc. 4th Intl. Conf. on Security and Privacy in Communication Netowrks (SecureComm 2008), pp. 1–10. ACM, New York (2008)
Bellare, M., Goldreich, O.: On defining proofs of knowledge. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 390–420. Springer, Heidelberg (1993)
Bowers, K., Juels, A., Oprea, A.: Proofs of retrievability: Theory and implementation. Technical Report 2008/175, Cryptology ePrint Archive (2008)
Dodis, Y., Vadhan, S., Wichs, D.: Proofs of retrievability via hardness amplification. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 109–127. Springer, Heidelberg (2009)
Erway, C., Papamanthou, C., Kupcu, A., Tamassia, R.: Dynamic provable data possession. In: ACM Conf. on Computer and Communications Security (to appear, 2009). Available as Cryptology ePrint Archive, Report 2008/432
Feige, U., Fiat, A., Shamir, A.: Zero knowledge proofs of identity. J. Cryptology 1(2), 77–94 (1988)
Goldreich, O., Kahan, A.: How to construct constant-round zero-knowledge proof systems for NP. J. Cryptology 9(3), 167–190 (1996)
Groth, J.: A verifiable secret shuffle of homomorphic encryptions. Technical Report 2005/246, IACR ePrint Cryptography Archive (2005)
Guillou, L., Quisquater, J.-J.: A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 123–128. Springer, Heidelberg (1988)
Juels, A., Kaliski, B.: PORs: Proofs of retrievability for large files. In: ACM Conference on Computer and Communications Security. ACM, New York (2007)
Lindell, Y.: Parallel coin-tossing and constant-round secure two-party computation. J. Cryptology 16(3), 143–184 (2003)
Naor, M., Rothblum, G.: The complexity of online memory checking. In: IEEE Symposium on Foundations of Computer Science, pp. 573–584. IEEE Computer Society, Los Alamitos (2005)
Shacham, H., Waters, B.: Compact proofs of retrievability. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 90–107. Springer, Heidelberg (2008), Full version http://eprint.iacr.org
Shoup, V.: On the security of a practical identification scheme. J. Cryptology 12(4), 247–260 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ateniese, G., Kamara, S., Katz, J. (2009). Proofs of Storage from Homomorphic Identification Protocols. In: Matsui, M. (eds) Advances in Cryptology – ASIACRYPT 2009. ASIACRYPT 2009. Lecture Notes in Computer Science, vol 5912. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10366-7_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-10366-7_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10365-0
Online ISBN: 978-3-642-10366-7
eBook Packages: Computer ScienceComputer Science (R0)