Privacy and Security via Randomized Methods (Video: Part 1, Part 2, Part 3, Part 4)
Guy Rothblum (Samsung Research America)
Abstract: Randomness plays a fundamental role in the modern study of cryptography. From the work of Shannon, it was known that randomness is essential to secure communication. Modern cryptography, however, has extended and deepened this understanding. Foundational security notions, such as semantically secure encryption, inherently rely on randomized encryption methods. Computational notions of entropy let us stretch short secret keys to encrypt long messages. Allowing randomization and interaction in proof systems opens new possibilities such proving statements in “zero knowledge”, conveying nothing beyond its validity.
More recently, randomness plays a central role in the study of privacy-preserving data analysis. Statistical analysis of sensitive data may yield valuable results, but it also poses serious threats to individuals’ privacy. Differential privacy uses randomized methods to address these conflicting concerns, and has emerged as a rigorous and powerful framework for privacy-preserving data analysis.
This tutorial will review some prominent examples of the interplay between randomness and security/privacy, with an emphasis on the emerging study of privacy-preserving data analysis using differential privacy.