Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR25-072 | 13th June 2025
Rahul Ilango, Alex Lombardi

Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions

We study several problems in the intersection of cryptography and complexity theory based on the following high-level thesis.

1) Obfuscation can serve as a general-purpose *worst-case to average-case reduction*, reducing the existence of various forms of cryptography to corresponding worst-case assumptions.
2) We can therefore hope to overcome ... more >>>


TR25-071 | 2nd June 2025
Chin Ho Lee, Emanuele Viola

Pseudorandom bits for non-commutative programs

Revisions: 1

We obtain new explicit pseudorandom generators for several computational models involving groups. Our main results are as follows:

1. We consider read-once group-products over a finite group $G$, i.e., tests of the form $\prod_{i=1}^n g_{i}^{x_{i}}$ where $g_{i}\in G$, a special case of read-once permutation branching programs. We give generators with ... more >>>


TR25-070 | 2nd June 2025
Halley Goldberg, Valentine Kabanets

Witness Encryption and NP-hardness of Learning

We study connections between two fundamental questions from computer science theory. (1) Is witness encryption in the sense of Garg et al. (2013) possible for NP? That is, given an instance $x$ of an NP-complete language $L$, can one encrypt a secret message with security contingent on the ability to ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint