Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Gil Segev:

TR16-092 | 3rd June 2016
Gilad Asharov, Alon Rosen, Gil Segev

Indistinguishability Obfuscation Does Not Reduce to Structured Languages

Revisions: 1

We prove that indistinguishability obfuscation (iO) and one-way functions do not naturally reduce to any language within $NP \cap coNP$. This is proved within the framework introduced by Asharov and Segev (FOCS '15) that captures the vast majority of techniques that have been used so far in iO-based constructions.

Our ... more >>>

TR16-059 | 14th April 2016
Alon Rosen, Gil Segev, Ido Shahaf

Can PPAD Hardness be Based on Standard Cryptographic Assumptions?

Revisions: 2

We consider the question of whether average-case PPAD hardness can be based on standard cryptographic assumptions, such as the existence of one-way functions or public-key encryption. This question is particularly well-motivated in light of new devastating attacks on obfuscation candidates and their underlying building blocks, which are currently the only ... more >>>

ISSN 1433-8092 | Imprint