Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with pseudo randomness:
TR01-064 | 10th September 2001
Moni Naor, Omer Reingold, Alon Rosen

Pseudo-Random Functions and Factoring

Factoring integers is the most established problem on which
cryptographic primitives are based. This work presents an efficient
construction of {\em pseudorandom functions} whose security is based
on the intractability of factoring. In particular, we are able to
construct efficient length-preserving pseudorandom functions where
each evaluation requires only a ... more >>>

TR17-084 | 2nd May 2017
Iftach Haitner, Salil Vadhan

The Many Entropies in One-Way Functions

Revisions: 1

Computational 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 ... more >>>

TR18-015 | 25th January 2018
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett

Pseudorandom Generators from Polarizing Random Walks

Revisions: 1 , Comments: 1

We propose a new framework for constructing pseudorandom generators for $n$-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in $[-1,1]^n$. Next, we use a fractional pseudorandom generator as steps of a random walk in $[-1,1]^n$ that ... more >>>

TR18-066 | 8th April 2018
Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma

Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions

In their seminal work, Chattopadhyay and Zuckerman (STOC'16) constructed a two-source extractor with error $\varepsilon$ for $n$-bit sources having min-entropy $poly\log(n/\varepsilon)$. Unfortunately, the construction running-time is $poly(n/\varepsilon)$, which means that with polynomial-time constructions, only polynomially-large errors are possible. Our main result is a $poly(n,\log(1/\varepsilon))$-time computable two-source condenser. For any $k ... more >>>

TR21-166 | 21st November 2021
Lijie Chen, Shuichi Hirahara, Neekon Vafa

Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions

What is a minimal worst-case complexity assumption that implies non-trivial average-case hardness of NP or PH? This question is well motivated by the theory of fine-grained average-case complexity and fine-grained cryptography. In this paper, we show that several standard worst-case complexity assumptions are sufficient to imply non-trivial average-case hardness ... more >>>

TR22-117 | 23rd August 2022
Ronen Shaltiel, Jad Silbak

Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits

Guruswami and Smith (J. ACM 2016) considered codes for channels that are poly-size circuits which modify at most a $p$-fraction of the bits of the codeword. This class of channels is significantly stronger than Shannon's binary symmetric channel (BSC), but weaker than Hamming's channels which are computationally unbounded.
Guruswami and ... more >>>

ISSN 1433-8092 | Imprint