Characterizing pseudoentropy and simplifying pseudorandom generator constructions

DOI10.1145/2213977.2214051zbMath1286.65008OpenAlexW2171959510MaRDI QIDQ5415518

Colin Jia Zheng, Salil P. Vadhan

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: http://nrs.harvard.edu/urn-3:HUL.InstRepos:12724017

zbMATH Keywords

entropycomputational complexitycryptographymin-max theorempseudorandomnesshardcore lemmakl divergence

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) Measures of information, entropy (94A17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (25)

Pseudoentropy: Lower-Bounds for Chain Rules and Transformations ⋮ A counterexample to the chain rule for conditional HILL entropy ⋮ Security levels in steganography -- insecurity does not imply detectability ⋮ Metric Pseudoentropy: Characterizations, Transformations and Applications ⋮ Nonuniform Indistinguishability and Unpredictability Hardcore Lemmas: New Proofs and Applications to Pseudoentropy ⋮ Modulus Computational Entropy ⋮ Non-adaptive universal one-way hash functions from arbitrary one-way functions ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ On derandomizing Yao's weak-to-strong OWF construction ⋮ Simple constructions from (almost) regular one-way functions ⋮ Computational fuzzy extractors ⋮ On the Complexity of Breaking Pseudoentropy ⋮ Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols ⋮ Pseudorandom generators from regular one-way functions: new constructions with improved parameters ⋮ Counting unpredictable bits: a simple PRG from one-way functions ⋮ On the complexity of constructing pseudorandom functions (especially when they don't exist) ⋮ A direct PRF construction from Kolmogorov complexity ⋮ On central primitives for quantum cryptography with classical communication ⋮ Complexity theory. Abstracts from the workshop held June 2--7, 2024 ⋮ On linear-size pseudorandom generators and hardcore functions ⋮ Unnamed Item ⋮ Simple constructions from (almost) regular one-way functions ⋮ Rate-1, Linear Time and Additively Homomorphic UC Commitments ⋮ Pseudorandom Functions: Three Decades Later ⋮ The Many Entropies in One-Way Functions

This page was built for publication: Characterizing pseudoentropy and simplifying pseudorandom generator constructions