All reports by Author Zvika Brakerski:

__
TR20-137
| 11th September 2020
__

Zvika Brakerski, Yael Tauman Kalai, Raghuvansh Saxena#### Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes

__
TR18-125
| 7th July 2018
__

Zvika Brakerski#### Fundamentals of Fully Homomorphic Encryption – A Survey

__
TR18-056
| 20th March 2018
__

Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel Wichs#### Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing

__
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

__
TR16-077
| 12th May 2016
__

Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai#### Non-Interactive RAM and Batch NP Delegation from any PIR

Revisions: 1

__
TR13-014
| 11th January 2013
__

Zvika Brakerski, Moni Naor#### Fast Algorithms for Interactive Coding

__
TR12-043
| 16th April 2012
__

Zvika Brakerski, Yael Tauman Kalai#### Efficient Interactive Coding Against Adversarial Noise

Revisions: 1

__
TR11-111
| 10th August 2011
__

Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan#### Fully Homomorphic Encryption without Bootstrapping

__
TR11-109
| 9th August 2011
__

Zvika Brakerski, Vinod Vaikuntanathan#### Efficient Fully Homomorphic Encryption from (Standard) LWE

__
TR09-031
| 6th April 2009
__

Zvika Brakerski, Oded Goldreich#### From absolute distinguishability to positive distinguishability

Zvika Brakerski, Yael Tauman Kalai, Raghuvansh Saxena

The field of Interactive Coding studies how an interactive protocol can be made resilient to channel errors. Even though this field has received abundant attention since Schulman's seminal paper (FOCS 92), constructing interactive coding schemes that are both deterministic and efficient, and at the same time resilient to adversarial errors ... more >>>

Zvika Brakerski

A homomorphic encryption scheme is one that allows computing on encrypted data without decrypting it first. In fully homomorphic encryption it is possible to apply any efficiently computable function to encrypted data. We provide a survey on the origins, definitions, properties, constructions and uses of fully homomorphic encryption.

more >>>Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel Wichs

We present a worst case decoding problem whose hardness reduces to that of solving the Learning Parity with Noise (LPN) problem, in some parameter regime. Prior to this work, no worst case hardness result was known for LPN (as opposed to syntactically similar problems such as Learning with Errors). The ... more >>>

Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari

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 >>>

Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai

We present an adaptive and non-interactive protocol for verifying arbitrary efficient computations in fixed polynomial time. Our protocol is computationally sound and can be based on any computational PIR scheme, which in turn can be based on standard polynomial-time cryptographic assumptions (e.g. the worst case hardness of polynomial-factor approximation of ... more >>>

Zvika Brakerski, Moni Naor

Consider two parties who wish to communicate in order to execute some interactive protocol $\pi$. However, the communication channel between them is noisy: An adversary sees everything that is transmitted over the channel and can change a constant fraction of the bits as he pleases, thus interrupting the execution of ... more >>>

Zvika Brakerski, Yael Tauman Kalai

In this work, we study the fundamental problem of constructing interactive protocols that are robust to noise, a problem that was originally considered in the seminal works of Schulman (FOCS '92, STOC '93), and has recently regained popularity. Robust interactive communication is the interactive analogue of error correcting codes: Given ... more >>>

Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan

We present a radically new approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled fully homomorphic encryption schemes (capable of evaluating arbitrary polynomial-size circuits), {\em without Gentry's bootstrapping procedure}.

... more >>>Zvika Brakerski, Vinod Vaikuntanathan

We present a fully homomorphic encryption scheme that is based solely on the (standard) learning with errors (LWE) assumption. Applying known results on LWE, the security of our scheme is based on the worst-case hardness of ``short vector problems'' on arbitrary lattices.

Our construction improves on previous works in two ... more >>>

Zvika Brakerski, Oded Goldreich

We study methods of converting algorithms that distinguish pairs

of distributions with a gap that has an absolute value that is noticeable

into corresponding algorithms in which the gap is always positive.

Our focus is on designing algorithms that, in addition to the tested string,

obtain a ...
more >>>