Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Proofs of Storage from Homomorphic Identification Protocols

Giuseppe Ateniese, Seny Kamara, and Jonathan Katz


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).


Publication typeInproceedings
Published inAdvances in Cryptology - ASIACRYPT '09
SeriesLecture Notes in Computer Science
PublisherSpringer Verlag
> Publications > Proofs of Storage from Homomorphic Identification Protocols