@article {15081, title = {Proofs of storage from homomorphic identification protocols}, journal = {Advances in Cryptology{\textendash}ASIACRYPT 2009}, year = {2009}, month = {2009///}, pages = {319 - 333}, 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 {\textquoteleft}tags{\textquoteright} on multiple messages can be homomorphically combined to yield a {\textquoteleft}tag{\textquoteright} 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). }, doi = {10.1007/978-3-642-10366-7_19}, author = {Ateniese,G. and Kamara,S. and Katz, Jonathan} }