Learning to Reconstruct - Statistical Learning Theory and Encrypted Database Attacks

Explore a groundbreaking presentation on the intersection of statistical learning theory and encrypted database attacks. Delve into the problem of reconstructing encrypted databases from access pattern leakage, and discover how this relates to statistical learning theory. Learn about ε-approximate database reconstruction (ε-ADR) from range query leakage, with attacks that scale only with relative error ε, independent of database size or possible data item values. Investigate the novel concept of ε-approximate order reconstruction (ε-AOR) and understand how it can be achieved with a minimal number of uniformly random range queries. Examine the application of learning theory to PQ-trees and their role in recording ordering constraints. Discover how auxiliary distributions can enhance ε-AOR to achieve ε-ADR, and see real-world examples of accurate database reconstruction with surprisingly few queries. Explore the implications of access pattern leakage for various query classes, including prefix and suffix queries, and understand the general lower bound for all query classes. Finally, learn about the reduction from reconstruction with known or chosen queries to PAC learning, broadening your understanding of this critical area in database security and privacy.