TY - GEN
T1 - Proofs of retrievability with public verifiability and constant communication cost in cloud
AU - Yuan, Jiawei
AU - Yu, Shucheng
PY - 2013
Y1 - 2013
N2 - For data storage outsourcing services, it is important to allow data owners to efficiently and securely verify that the storage server stores their data correctly. To address this issue, several proof-of-retrievability (POR) schemes have been proposed wherein a storage server must prove to a verifier that all of a client's data are stored correctly. While existing POR schemes offer decent solutions addressing various practical issues, they either have a non-trivial (linear or quadratic) communication complexity, or only support private verification, i.e., only the data owner can verify the remotely stored data. It remains open to design a POR scheme that achieves both public verifiability and constant communication cost simultaneously. In this paper, we solve this open problem and propose the first POR scheme with public verifiability and constant communication cost: in our proposed scheme, the message exchanged between the prover and verifier is composed of a constant number of group elements; different from existing private POR constructions, our scheme allows public verification and releases the data owners from the burden of staying online. We achieved these by tailoring and uniquely combining techniques such as constant size polynomial commitment and homomorphic linear authenticators. Thorough analysis shows that our proposed scheme is efficient and practical. We prove the security of our scheme based on the Computational Diffie-Hellman Problem, the Strong Diffie-Hellman assumption and the Bilinear Strong Diffie-Hellman assumption.
AB - For data storage outsourcing services, it is important to allow data owners to efficiently and securely verify that the storage server stores their data correctly. To address this issue, several proof-of-retrievability (POR) schemes have been proposed wherein a storage server must prove to a verifier that all of a client's data are stored correctly. While existing POR schemes offer decent solutions addressing various practical issues, they either have a non-trivial (linear or quadratic) communication complexity, or only support private verification, i.e., only the data owner can verify the remotely stored data. It remains open to design a POR scheme that achieves both public verifiability and constant communication cost simultaneously. In this paper, we solve this open problem and propose the first POR scheme with public verifiability and constant communication cost: in our proposed scheme, the message exchanged between the prover and verifier is composed of a constant number of group elements; different from existing private POR constructions, our scheme allows public verification and releases the data owners from the burden of staying online. We achieved these by tailoring and uniquely combining techniques such as constant size polynomial commitment and homomorphic linear authenticators. Thorough analysis shows that our proposed scheme is efficient and practical. We prove the security of our scheme based on the Computational Diffie-Hellman Problem, the Strong Diffie-Hellman assumption and the Bilinear Strong Diffie-Hellman assumption.
KW - cloud storage
KW - constant communication
KW - integrity check
KW - polynomial commitment
KW - proofs of retrievability
KW - public verification
UR - http://www.scopus.com/inward/record.url?scp=84878475706&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84878475706&partnerID=8YFLogxK
U2 - 10.1145/2484402.2484408
DO - 10.1145/2484402.2484408
M3 - Conference contribution
AN - SCOPUS:84878475706
SN - 9781450320672
T3 - Cloud Computing 2013 - Proceedings of the 2013 International Workshop on Security in Cloud Computing
SP - 19
EP - 26
BT - Cloud Computing 2013 - Proceedings of the 2013 International Workshop on Security in Cloud Computing
T2 - 2013 1st International Workshop on Security in Cloud Computing, Cloud Computing 2013
Y2 - 8 May 2013 through 8 May 2013
ER -