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). |
Year | DOI | Venue |
---|---|---|
2009 | 10.1007/978-3-642-10366-7_19 | ASIACRYPT |
Keywords | Field | DocType |
linear combination,unbounded-use pos,publicly-verifiable pos,identification protocol,public-key hla,certain homomorphic property,homomorphic identification protocols,interactive protocol,homomorphic linear authenticator,file length,public-key hlas,public key,message authentication,communication complexity | Randomized algorithm,Linear combination,Homomorphic encryption,Message authentication code,Computer science,Random oracle,Theoretical computer science,Communication complexity,Mathematical proof,Security parameter | Conference |
Volume | ISSN | Citations |
5912 | 0302-9743 | 120 |
PageRank | References | Authors |
4.00 | 16 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Giuseppe Ateniese | 1 | 4380 | 254.66 |
Seny Kamara | 2 | 1394 | 61.67 |
Jonathan Katz | 3 | 7579 | 347.97 |