Optimal Verification of Operations on Dynamic Sets

Explore a 21-minute conference talk from Crypto 2011 on optimal verification of operations on dynamic sets. Delve into the research of Charalampos Papamanthou, Roberto Tamassia, and Nikos Triandopoulos from Brown University, RSA Laboratories, and Boston University. Learn about new authenticated data structures that enable public verification of set operations like intersection, union, subset, and set difference performed by untrusted servers. Discover how these protocols achieve optimal verification, proof, and update complexity using bilinear-map accumulators and accumulation trees. Understand the advantages over existing schemes in terms of communication, verification, and storage costs. Examine applications in keyword search and database query verification. Gain insights into the security basis of these protocols, which relies on the bilinear q-strong Diffie-Hellman assumption.