TY - GEN
T1 - Optimal verification of operations on dynamic sets
AU - Papamanthou, Charalampos
AU - Tamassia, Roberto
AU - Triandopoulos, Nikos
PY - 2011
Y1 - 2011
N2 - We study the design of protocols for set-operation verification, namely the problem of cryptographically checking the correctness of outsourced set operations performed by an untrusted server over a dynamic collection of sets that are owned (and updated) by a trusted source. We present new authenticated data structures that allow any entity to publicly verify a proof attesting the correctness of primitive set operations such as intersection, union, subset and set difference. Based on a novel extension of the security properties of bilinear-map accumulators as well as on a primitive called accumulation tree, our protocols achieve optimal verification and proof complexity (i.e., only proportional to the size of the query parameters and the answer), as well as optimal update complexity (i.e., constant), while incurring no extra asymptotic space overhead. The proof construction is also efficient, adding a logarithmic overhead to the computation of the answer of a set-operation query. In contrast, existing schemes entail high communication and verification costs or high storage costs. Applications of interest include efficient verification of keyword search and database queries. The security of our protocols is based on the bilinear q-strong Diffie-Hellman assumption.
AB - We study the design of protocols for set-operation verification, namely the problem of cryptographically checking the correctness of outsourced set operations performed by an untrusted server over a dynamic collection of sets that are owned (and updated) by a trusted source. We present new authenticated data structures that allow any entity to publicly verify a proof attesting the correctness of primitive set operations such as intersection, union, subset and set difference. Based on a novel extension of the security properties of bilinear-map accumulators as well as on a primitive called accumulation tree, our protocols achieve optimal verification and proof complexity (i.e., only proportional to the size of the query parameters and the answer), as well as optimal update complexity (i.e., constant), while incurring no extra asymptotic space overhead. The proof construction is also efficient, adding a logarithmic overhead to the computation of the answer of a set-operation query. In contrast, existing schemes entail high communication and verification costs or high storage costs. Applications of interest include efficient verification of keyword search and database queries. The security of our protocols is based on the bilinear q-strong Diffie-Hellman assumption.
UR - http://www.scopus.com/inward/record.url?scp=80051963720&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80051963720&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22792-9_6
DO - 10.1007/978-3-642-22792-9_6
M3 - Conference contribution
AN - SCOPUS:80051963720
SN - 9783642227912
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 91
EP - 110
BT - Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Proceedings
T2 - 31st Annual International Cryptology Conference, CRYPTO 2011
Y2 - 14 August 2011 through 18 August 2011
ER -