ECCC-Report TR22-032https://eccc.weizmann.ac.il/report/2022/032Comments and Revisions published for TR22-032en-usWed, 02 Mar 2022 09:42:04 +0200
Paper TR22-032
| Incompressiblity and Next-Block Pseudoentropy |
Noam Mazor,
Iftach Haitner,
Jad Silbak
https://eccc.weizmann.ac.il/report/2022/032A distribution is k-incompressible, Yao [FOCS ’82], if no efficient compression scheme compresses it to less than k bits. While being a natural measure, its relation to other computational analogs of entropy such as pseudoentropy, Hastad, Impagliazzo, Levin, and Luby [SICOMP 99], and to other cryptographic hardness assumptions, was unclear.
We advance towards a better understating of this notion, showing that a k-incompressible distribution has (k?2) bits of next-block pseudoentropy, a refinement of pseudoentropy introduced by Haitner, Reingold, and Vadhan [SICOMP ’13]. We deduce that a samplable distribution X that is (H(X) + 2)-incompressible, implies the existence of one-way functions.Wed, 02 Mar 2022 09:42:04 +0200https://eccc.weizmann.ac.il/report/2022/032