TY - GEN
T1 - Streaming authenticated data structures
T2 - 6th ACM Cloud Computing Security Workshop, CCSW 2014, Held in Conjunction with the 2014 ACM Computer and Communication Security, CCS 2014
AU - Qian, Yi
AU - Zhang, Yupeng
AU - Chen, Xi
AU - Papamanthou, Charalampos
N1 - Publisher Copyright:
Copyright © 2014 by the Association for Computing Machinery, Inc. (ACM).
PY - 2014/11/7
Y1 - 2014/11/7
N2 - In the setting of streaming verifiable computation, a verifier and a prover observe a stream of n elements x1; x2; : : : ; xn and later, the verifier can delegate a computation (e.g., a range search query) to the untrusted prover over the stream. The prover returns the result of the computation and a cryptographic proof for its correctness. To verify the prover's result efficiently, the verifier keeps small local (logarithmic) state, which he updates while observing the stream. The challenge is to enable the verifier to update his local state with no interaction with the prover, while ensuring the prover can compute proofs efficiently. Papamanthou et al. (EUROCRYPT 2013) introduced streaming authenticated data structures (SADS) to address the above problem. Yet their scheme is complex to describe and impractical to implement, mainly due to the use of Ajtai's lattice-based hash function. In this work we present an abstract SADS construction that can use any hash function satisfying properties that we formally define. This leads to a simpler exposition of the fundamental ideas of Papamanthou et al.'s work and to a practical implementation of a streaming authenticated data structure that employs the efficient SWIFFT hash function, which we show to comply with our abstraction. We implement both the EUROCRYPT 2013 construction and our new scheme and report major savings in prover time and public key size.
AB - In the setting of streaming verifiable computation, a verifier and a prover observe a stream of n elements x1; x2; : : : ; xn and later, the verifier can delegate a computation (e.g., a range search query) to the untrusted prover over the stream. The prover returns the result of the computation and a cryptographic proof for its correctness. To verify the prover's result efficiently, the verifier keeps small local (logarithmic) state, which he updates while observing the stream. The challenge is to enable the verifier to update his local state with no interaction with the prover, while ensuring the prover can compute proofs efficiently. Papamanthou et al. (EUROCRYPT 2013) introduced streaming authenticated data structures (SADS) to address the above problem. Yet their scheme is complex to describe and impractical to implement, mainly due to the use of Ajtai's lattice-based hash function. In this work we present an abstract SADS construction that can use any hash function satisfying properties that we formally define. This leads to a simpler exposition of the fundamental ideas of Papamanthou et al.'s work and to a practical implementation of a streaming authenticated data structure that employs the efficient SWIFFT hash function, which we show to comply with our abstraction. We implement both the EUROCRYPT 2013 construction and our new scheme and report major savings in prover time and public key size.
KW - Abstract SADS
KW - GCK hash function
KW - Streaming authenticated data structures
UR - http://www.scopus.com/inward/record.url?scp=84937704977&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84937704977&partnerID=8YFLogxK
U2 - 10.1145/2664168.2664177
DO - 10.1145/2664168.2664177
M3 - Conference contribution
AN - SCOPUS:84937704977
SN - 9781450332392
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 129
EP - 139
BT - CCSW 2014 - Proceedings of the 2014 ACM Cloud Computing Security Workshop, Co-located with CCS 2014
PB - Association for Computing Machinery
Y2 - 7 November 2014
ER -