Opening Computational Indistinguishability
Computational Indistinguishability
- Length
- 14 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Probabilistic polynomial time algorithms
Computational indistinguishability is the cryptographic notion that two probability distributions look identical to every efficient algorithm. O'Donnell models adversaries as probabilistic polynomial-time algorithms running on a security parameter. He defines negligible functions as those shrinking faster than the inverse of every polynomial, and ensembles as sequences of random bit strings indexed by that parameter. Indistinguishability is shown to be an equivalence relation preserved under polynomial-time processing. The central proof is the hybrid argument, which carries pairwise indistinguishability across a polynomial-length chain of ensembles to its endpoints. Part 25b of A Theorist's Toolkit at Carnegie Mellon, it follows Pass and Shelat's A Course in Cryptography and assumes probability and asymptotic notation.

Your comment is kept while you sign up.Sign in
Defines negligible advantage for polynomial-time distinguishers, then proves the hybrid argument chaining ensembles.
Computational indistinguishability is the cryptographic notion that two probability distributions look identical to every efficient algorithm. O'Donnell models adversaries as probabilistic polynomial-time algorithms running on a security parameter. He defines negligible functions as those shrinking faster than the inverse of every polynomial, and ensembles as sequences of random bit strings indexed by that parameter. Indistinguishability is shown to be an equivalence relation preserved under polynomial-time processing. The central proof is the hybrid argument, which carries pairwise indistinguishability across a polynomial-length chain of ensembles to its endpoints. Part 25b of A Theorist's Toolkit at Carnegie Mellon, it follows Pass and Shelat's A Course in Cryptography and assumes probability and asymptotic notation.
This lecture
Lecture 80 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.