ECCC-Report TR17-084https://eccc.weizmann.ac.il/report/2017/084Comments and Revisions published for TR17-084en-usWed, 06 Dec 2017 08:59:34 +0200
Revision 1
| The Many Entropies in One-Way Functions |
Iftach Haitner,
Salil Vadhan
https://eccc.weizmann.ac.il/report/2017/084#revision1Computational analogues of information-theoretic notions have given rise to some of the most interesting phenomena in the theory of computation. For example, computational indistinguishability, Goldwasser and Micali '84, which is the computational analogue of statistical distance, enabled the bypassing of Shanon's impossibility results on perfectly secure encryption, and provided the basis for the computational theory of pseudorandomness. Pseudoentropy, Haastad, Impagliazzo, Levin, and Luby '99, a computational analogue of entropy, was the key to the fundamental result establishing the equivalence of pseudorandom generators and one-way functions, and has become a basic concept in complexity theory and cryptography.
This tutorial discusses two rather recent computational notions of entropy, both of which can be easily found in any one-way function, the most basic cryptographic primitive. The first notion is next-block pseudoentropy, Haitner, Reingold and Vadhan '13, a refinement of of pseudoentropy that enables simpler and more efficient construction of pseudorandom generators. The second is inaccessible entropy, Haitner, Reingold, Vadhan and Wee '09, which relates to unforgeability and is used to construct simpler and more efficient universal one-way hash functions and statistically hiding commitments.
Wed, 06 Dec 2017 08:59:34 +0200https://eccc.weizmann.ac.il/report/2017/084#revision1
Paper TR17-084
| The Many Entropies in One-Way Functions |
Iftach Haitner,
Salil Vadhan
https://eccc.weizmann.ac.il/report/2017/084Computational analogues of information-theoretic notions have given rise to some of the most interesting phenomena in the theory of computation. For example, computational indistinguishability, Goldwasser and Micali '84, which is the computational analogue of statistical distance, enabled the bypassing of Shanon's impossibility results on perfectly secure encryption, and provided the basis for the computational theory of pseudorandomness. Pseudoentropy, Haastad, Impagliazzo, Levin, and Luby '99, a computational analogue of entropy, was the key to the fundamental result establishing the equivalence of pseudorandom generators and one-way functions, and has become a basic concept in complexity theory and cryptography.
This tutorial discusses two rather recent computational notions of entropy, both of which can be easily found in any one-way function, the most basic cryptographic primitive. The first notion is next-block pseudoentropy, Haitner, Reingold and Vadhan '13, a refinement of of pseudoentropy that enables simpler and more efficient construction of pseudorandom generators. The second is inaccessible entropy, Haitner, Reingold, Vadhan and Wee '09, which relates to unforgeability and is used to construct simpler and more efficient universal one-way hash functions and statistically hiding commitments.
Sat, 06 May 2017 00:48:51 +0300https://eccc.weizmann.ac.il/report/2017/084