Unifying computational entropies via Kullback-Leibler divergence
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2019
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916479547473920 |
|---|---|
| author | Agrawal, Rohit Chen, Yi-Hsiu Horel, Thibaut Vadhan, Salil |
| author_facet | Agrawal, Rohit Chen, Yi-Hsiu Horel, Thibaut Vadhan, Salil |
| contents | We introduce hardness in relative entropy, a new notion of hardness for search problems which on the one hand is satisfied by all one-way functions and on the other hand implies both next-block pseudoentropy and inaccessible entropy, two forms of computational entropy used in recent constructions of pseudorandom generators and statistically hiding commitment schemes, respectively. Thus, hardness in relative entropy unifies the latter two notions of computational entropy and sheds light on the apparent "duality" between them. Additionally, it yields a more modular and illuminating proof that one-way functions imply next-block inaccessible entropy, similar in structure to the proof that one-way functions imply next-block pseudoentropy (Vadhan and Zheng, STOC '12). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1902_11202 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Unifying computational entropies via Kullback-Leibler divergence Agrawal, Rohit Chen, Yi-Hsiu Horel, Thibaut Vadhan, Salil Cryptography and Security Computational Complexity We introduce hardness in relative entropy, a new notion of hardness for search problems which on the one hand is satisfied by all one-way functions and on the other hand implies both next-block pseudoentropy and inaccessible entropy, two forms of computational entropy used in recent constructions of pseudorandom generators and statistically hiding commitment schemes, respectively. Thus, hardness in relative entropy unifies the latter two notions of computational entropy and sheds light on the apparent "duality" between them. Additionally, it yields a more modular and illuminating proof that one-way functions imply next-block inaccessible entropy, similar in structure to the proof that one-way functions imply next-block pseudoentropy (Vadhan and Zheng, STOC '12). |
| title | Unifying computational entropies via Kullback-Leibler divergence |
| topic | Cryptography and Security Computational Complexity |
| url | https://arxiv.org/abs/1902.11202 |