All reports by Author Tal Malkin:

__
TR19-055
| 9th April 2019
__

Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo#### Lower Bounds for Oblivious Near-Neighbor Search

__
TR18-040
| 21st February 2018
__

Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan#### Non-Malleable Codes for Small-Depth Circuits

__
TR15-008
| 14th January 2015
__

Igor Carboni Oliveira, Siyao Guo, Tal Malkin, Alon Rosen#### The Power of Negations in Cryptography

Revisions: 1

__
TR03-086
| 1st December 2003
__

Amos Beimel, Tal Malkin#### A Quantitative Approach to Reductions in Secure Computation

Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo

We prove an $\Omega(d \lg n/ (\lg\lg n)^2)$ lower bound on the dynamic cell-probe complexity of statistically $\mathit{oblivious}$ approximate-near-neighbor search (ANN) over the $d$-dimensional Hamming cube. For the natural setting of $d = \Theta(\log n)$, our result implies an $\tilde{\Omega}(\lg^2 n)$ lower bound, which is a quadratic improvement over the ... more >>>

Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e.~$\mathsf{AC^0}$ tampering functions), our codes have codeword length $n = k^{1+o(1)}$ for a $k$-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay ... more >>>

Igor Carboni Oliveira, Siyao Guo, Tal Malkin, Alon Rosen

The study of monotonicity and negation complexity for Boolean functions has been prevalent in complexity theory as well as in computational learning theory, but little attention has been given to it in the cryptographic context. Recently, Goldreich and Izsak (2012) have initiated a study of whether cryptographic primitives can be ... more >>>

Amos Beimel, Tal Malkin

Secure computation is one of the most fundamental cryptographic tasks.

It is known that all functions can be computed securely in the

information theoretic setting, given access to a black box for some

complete function such as AND. However, without such a black box, not

all functions can be securely ...
more >>>