Verifiable Delegation of Computation over Large Datasets - Crypto 2011

Explore a 21-minute conference talk from CRYPTO 2011 on verifiable delegation of computation over large datasets. Delve into the research by Siavosh Benabbas, Rosario Gennaro, and Yevgeniy Vahlis from the University of Toronto, IBM Research, and Columbia University. Learn about the first practical verifiable computation scheme for high degree polynomial functions, applicable to making predictions based on polynomials fitted to large sample sets. Discover how this scheme leads to new solutions for verifiable keyword search and proofs of retrievability. Understand the concept of a verifiable database (VDB) and its implementation based on the hardness of the subgroup membership problem in composite order bilinear groups. Examine topics such as efficient verification, breakthroughs, data structures, delegation techniques, pseudorandom functions, and the technical details of two constructions presented in this talk.

Intro
Background
Efficient Verification
Breakthroughs
Main Result
Data Structure
Work
Delegation
Technical Details
Pseudorandom Function
Verifiable Computation
Trapdoor Efficiency
Two Constructions
Summary