Computational Analogues of Entropy 2/3
143 views · Published 14 April 2016 · 48:19 · Indexed 1 November 2026
Channel: Institut Henri Poincaré · 2016 · Science & Technology
By Iftach Haitner (Tel Aviv University) & Leo Reyzin (Boston University) Abstract: If you see a cryptographic hash of my password, how can I quantify your uncertainty about the password? Entropy – a traditional measure of uncertainty – is of little help: conditioned on your knowledge of the hash value, the distribution of my passwords has small support, and yet your knowledge should not of be of much help to you in guessing my password. Conversely, if you see a cryptographic hash of a long document, how can you quantify my certainty about the document? Entropy is again of little help: there are many possible documents that hash to the same value, and yet you can be fairly certain that I know at most one of them. Computational analogues of entropy provide answers to these questions and enable a host of cryptographic applications. In fact, the right notion of entropy and a toolbox of lemmas can make for beautifully simple proofs. This talk will survey some of the notions, lemmas, and applications.
More from this channel
-
29:47
10 ans du Groupe Calcul : Histoire du Calcul - Introduction
-
52:14
Gauss, Jacobi, Seidel, Richardson, Krylov: the Invention of Iterative Methods
-
55:33
Les "invariants arithmétiques" de H. Poincaré
-
1:08:53
Henri Poincaré, a founding father of the modern theory of PDEs
-
57:13
Sympletic topology from Poincaré to Gromov
-
57:35
Structural Realism, Then and Now
-
46:26
Poincaré inequalities in probability and geometric analysis
-
1:02:05
On the contributions of Henri Poincaré to modern geophysics...