Homomorphic Linear Authentication Schemes for Proofs of Retrievability

In a proof of retrievability (POR) system, interactive POR protocols are executed between a storage server and clients, so that clients can be convinced that their data is available at the storage server, ready to be retrieved when needed. In an interactive POR protocol, clients initiate challenges to the server, and the server feedbacks responses to clients with input of the stored data. Retrievability means that it should be possible for a client to extract the his/her data from the server´s valid responses. An essential step-stone leading to retrievability is server´s unforgeability of valid responses, i.e, any server coming up valid responses to a client´s challenges is actually storing the client´s data with overwhelming probability. Unforgeability can be achieved with authentication schemes like MAC, Digital Signature, etc. With homomorphic linear authentication schemes, the authenticators can be aggregated into one tag for the challenges, hence reducing the communication complexity. In this paper, we explore some new homomorphic linear authenticator schemes in POR to provide unforgeability. Compared with the recent work of Shacham and Waters, our scheme enjoys the same shortest responses, but reduces the local storage from O(s) to O(1).