Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOCAL CRYPTOGRAPHY:
Reports tagged with local cryptography:
TR15-045 | 1st April 2015
Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

Minimizing Locality of One-Way Functions via Semi-Private Randomized Encodings

Revisions: 1

A one-way function is $d$-local if each of its outputs depends on at most $d$ input bits. In (Applebaum, Ishai, and Kushilevitz, FOCS 2004) it was shown that, under relatively mild assumptions, there exist $4$-local one-way functions (OWFs). This result is not far from optimal as it is not hard ... more >>>


TR17-063 | 10th April 2017
Benny Applebaum

Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions

The gap-ETH assumption (Dinur 2016; Manurangsi and Raghavendra 2016) asserts that it is exponentially-hard to distinguish between a satisfiable 3-CNF formula and a 3-CNF formula which is at most 0.99-satisfiable. We show that this assumption follows from the exponential hardness of finding a satisfying assignment for *smooth* 3-CNFs. Here smoothness ... more >>>


TR19-011 | 27th January 2019
Benny Applebaum, Eliran Kachlon

Sampling Graphs without Forbidden Subgraphs and Almost-Explicit Unbalanced Expanders

Revisions: 3

We initiate the study of the following hypergraph sampling problem: Sample a $d$-uniform hypergraph over $n$ vertices and $m$ hyperedges from some pseudorandom distribution $\mathcal{G}$ conditioned on not having some small predefined $t$-size hypergraph $H$ as a subgraph. The algorithm should run in $\mathrm{poly}(n)$-time even when the size of the ... more >>>




ISSN 1433-8092 | Imprint