Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with obfuscation:
TR14-106 | 9th August 2014
Craig Gentry

Computing on the edge of chaos: Structure and randomness in encrypted computation

This survey, aimed mainly at mathematicians rather than practitioners, covers recent developments in homomorphic encryption (computing on encrypted data) and program obfuscation (generating encrypted but functional programs). Current schemes for encrypted computation all use essentially the same "noisy" approach: they encrypt via a noisy encoding of the message, they decrypt ... more >>>

TR15-001 | 2nd January 2015
Nir Bitansky, Omer Paneth, Alon Rosen

On the Cryptographic Hardness of Finding a Nash Equilibrium

Revisions: 1

We prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and injective one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which ... more >>>

TR15-187 | 24th November 2015
Nir Bitansky, Vinod Vaikuntanathan

A Note on Perfect Correctness by Derandomization

Revisions: 1

In this note, we show how to transform a large class of erroneous cryptographic schemes into perfectly correct ones. The transformation works for schemes that are correct on every input with probability noticeably larger than half, and are secure under parallel repetition. We assume the existence of one-way functions ... more >>>

TR17-060 | 9th April 2017
Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari

Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)

Revisions: 1

We prove that for every function $G\colon\{0,1\}^n \rightarrow \mathbb{R}^m$, if every output of $G$ is a polynomial (over $\mathbb{R}$) of degree at most $d$ of at most $s$ monomials and $m > \widetilde{O}(sn^{\lceil d/2 \rceil})$, then there is a polynomial time algorithm that can distinguish a vector of the form ... more >>>

TR18-149 | 25th August 2018
Craig Gentry, Charanjit Jutla

Obfuscation using Tensor Products

We describe obfuscation schemes for matrix-product branching programs that are purely algebraic and employ matrix algebra and tensor algebra over a finite field. In contrast to the obfuscation schemes of Garg et al (SICOM 2016) which were based on multilinear maps, these schemes do not use noisy encodings. We prove ... more >>>

ISSN 1433-8092 | Imprint