All reports by Author Chin Ho Lee:

__
TR21-110
| 22nd July 2021
__

Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco Servedio, Emanuele Viola#### Fourier growth of structured $\mathbb{F}_2$-polynomials and applications

__
TR19-017
| 6th February 2019
__

Chin Ho Lee#### Fourier bounds and pseudorandom generators for product tests

__
TR17-167
| 3rd November 2017
__

Chin Ho Lee, Emanuele Viola#### More on bounded independence plus noise: Pseudorandom generators for read-once polynomials

Revisions: 1

__
TR17-090
| 15th May 2017
__

Chin Ho Lee, Emanuele Viola#### The coin problem for product tests

__
TR16-169
| 3rd November 2016
__

Elad Haramaty, Chin Ho Lee, Emanuele Viola#### Bounded independence plus noise fools products

__
TR16-102
| 4th July 2016
__

Ravi Boppana, Johan HÃ¥stad, Chin Ho Lee, Emanuele Viola#### Bounded independence vs. moduli

Revisions: 1

__
TR15-005
| 5th January 2015
__

Chin Ho Lee, Emanuele Viola#### Some limitations of the sum of small-bias distributions

Revisions: 1

__
TR12-157
| 12th November 2012
__

Andrej Bogdanov, Chin Ho Lee#### On the depth complexity of homomorphic encryption schemes

Revisions: 2

__
TR12-156
| 12th November 2012
__

Andrej Bogdanov, Chin Ho Lee#### Limits of provable security for homomorphic encryption

Revisions: 1

Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco Servedio, Emanuele Viola

We analyze the Fourier growth, i.e. the $L_1$ Fourier weight at level $k$ (denoted $L_{1,k}$), of various well-studied classes of "structured" $\mathbb{F}_2$-polynomials. This study is motivated by applications in pseudorandomness, in particular recent results and conjectures due to [CHHL19,CHLT19,CGLSS20] which show that upper bounds on Fourier growth (even at ... more >>>

Chin Ho Lee

We study the Fourier spectrum of functions $f\colon \{0,1\}^{mk} \to \{-1,0,1\}$ which can be written as a product of $k$ Boolean functions $f_i$ on disjoint $m$-bit inputs. We prove that for every positive integer $d$,

\[

\sum_{S \subseteq [mk]: |S|=d} |\hat{f_S}| = O(m)^d .

\]

Our upper bound ...
more >>>

Chin Ho Lee, Emanuele Viola

We construct pseudorandom generators with improved seed length for

several classes of tests. First we consider the class of read-once

polynomials over GF(2) in $m$ variables. For error $\e$ we obtain seed

length $\tilde O (\log(m/\e)) \log(1/\e)$, where $\tilde O$ hides lower-order

terms. This is optimal up to the factor ...
more >>>

Chin Ho Lee, Emanuele Viola

Let $X_{m, \eps}$ be the distribution over $m$ bits $(X_1, \ldots, X_m)$

where the $X_i$ are independent and each $X_i$ equals $1$ with

probability $(1+\eps)/2$ and $0$ with probability $(1-\eps)/2$. We

consider the smallest value $\eps^*$ of $\eps$ such that the distributions

$X_{m,\eps}$ and $X_{m,0}$ can be distinguished with constant

more >>>

Elad Haramaty, Chin Ho Lee, Emanuele Viola

Let $D$ be a $b$-wise independent distribution over

$\{0,1\}^m$. Let $E$ be the ``noise'' distribution over

$\{0,1\}^m$ where the bits are independent and each bit is 1

with probability $\eta/2$. We study which tests $f \colon

\{0,1\}^m \to [-1,1]$ are $\e$-fooled by $D+E$, i.e.,

$|\E[f(D+E)] - \E[f(U)]| \le \e$ where ...
more >>>

Ravi Boppana, Johan HÃ¥stad, Chin Ho Lee, Emanuele Viola

Let $k=k(n)$ be the largest integer such that there

exists a $k$-wise uniform distribution over $\zo^n$ that

is supported on the set $S_m := \{x \in \zo^n : \sum_i

x_i \equiv 0 \bmod m\}$, where $m$ is any integer. We

show that $\Omega(n/m^2 \log m) \le k \le 2n/m + ...
more >>>

Chin Ho Lee, Emanuele Viola

We exhibit $\epsilon$-biased distributions $D$

on $n$ bits and functions $f\colon \{0,1\}^n

\to \{0,1\}$ such that the xor of two independent

copies ($D+D$) does not fool $f$, for any of the

following choices:

1. $\epsilon = 2^{-\Omega(n)}$ and $f$ is in P/poly;

2. $\epsilon = 2^{-\Omega(n/\log n)}$ and $f$ is ... more >>>

Andrej Bogdanov, Chin Ho Lee

We show that secure homomorphic evaluation of any non-trivial functionality of sufficiently many inputs with respect to any CPA secure encryption scheme cannot be implemented by constant depth, polynomial size circuits, i.e. in the class AC0. In contrast, we observe that certain previously studied encryption schemes (with quasipolynomial security) can ... more >>>

Andrej Bogdanov, Chin Ho Lee

We show that public-key bit encryption schemes which support weak homomorphic evaluation of parity or majority cannot be proved message indistinguishable beyond AM intersect coAM via general (adaptive) reductions, and beyond statistical zero-knowledge via reductions of constant query complexity.

Previous works on the limitation of reductions for proving security of ... more >>>