A small sample of TCC'13 articles

For a larger sample, see my comments re some TCC'13 talks. All articles appear in the proceedings of TCC'13, LNCS 7785.

A Counterexample to the Chain Rule for Conditional HILL Entropy: And What Deniable Encryption Has to Do with It by Stephan Krenn, Krzysztof Pietrzak, and Akshay Wadia

This refers to conditional pseudo-entropy (PE) as defined in HILL. Recall that $X$ has pseudo-entropy at least $k$ if it is computationally indistinguishable from some $X'$ that has (Shannon) entropy $k$. It is shown that $PE[X|Y] > t$ while $PE[X|Y,b]=0$ with $b$ being a random bit. Let $f$ be a one-way function and $h$ be a hard-core of $f$. Consider the following probability space: Then, $PE(X|Y) = \log_2 {{2t}\choose t}$, because given $Y$ we need to present $t$ preimages having the same $h$-value and this value may be arbitrary (since $b$ cannot be approximated based on $Y$). On the other hand, $PE(X|Y,b)=0$, since $Y$ and $b$ determine $X$.

Languages with Efficient Zero-Knowledge PCPs are in SZK by Mohammad Mahmoody and David Xiao

A PCP is called efficient if the proof oracle can be represented by a small circuit (i.e., a circuit of size polynomial in the PCP-input). N.B.: A zero-knowledge PCP (ZKPCP) for a set outside BPP must use proofs of super-polynomial length, and (non-efficient) ZKPCPs for NEXP were shown in [KPT, STOC'97]. An interesting result of [GOVW, TCC12] implies that Quadratic Residuosity has efficient ZK PCPs. The paper's main result is captured in its title, and it leaves open the question of characterizing the class efficient-ZKPCP.

Unprovable Security of Perfect NIZK and Non-interactive Non-malleable Commitments by Rafael Pass

This paper advocates building a hierarchy of assumptions, viewing possible constructions also as assumption alas of a more complex nature. Building on the suggestion of Naor (2003), the author present a taxonomy of assumptions and separates the two primitives in the title from the set of "refutable assumption", where separation is wrt black-box proofs of security. The result also provide an appealing example of natural primitives that are security implemented in the ROM but cannot be proved secure (via a black box reduction) in the standard model.

Invited Talk by Tal Malkin: Secure Computation for Big Data

This talk focuses on secure multi-party computation on huge data, where the underlying computation can be performed in sublinear time (e.g., binary search or any other common data base operation). Using oblivious RAM and standard MPC (see next), such secure computation can be performed with polylogarithmic overhead.

Indeed, a very important result of Ostrovsky and Shoup (1997), which I managed to forget..., is that secure multi-party computation can be implemented with polylogarithmic overhead with respect to the time of a plain RAM computation (rather than w.r.t. to time on a TM). The solution relies on an Oblivious RAM (ORAM) and a secure MPC of the reactive functionality performed by its CPU.

Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy by Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova, and Abhradeep Thakurta

This inspiring work starts by relating ("average case") differential privacy to a Lipschitz condition regarding the utility provided by the algorithm. For an algorithm $A$, and any possible output $z$, define $f_z(x) = \log_2(Prob[A(x)=z])$. Then saying that $A$ has differential privacy $e$ iff for every $z$ the function $f_z$ is $e$-Lipschitz. The next idea is that a privacy preserving mechanism that is designed to allow only questions that preserve privacy (wrt a distribution of databases) may answer a query (presented as a function of the database) iff the corresponding functions are Lipschitz. Hence the role of testing the Lipschitz property. The main result is a transformation that given an arbitrary query translates it to an admissible one, while keeping the admissible ones intact.

Invited Talk by Benny Applebaum: Cryptographic Hardness of Random Local Functions - Survey

The talk touched on a variety of issues regarding the hardness of random local functions, while only mentioning the alternative structured construction of hard local functions by generically compiling hard log-space functions. One concrete motivation for avoiding the latter transformation is it effect on the input/output lengths. Benny pointed out that in the context of local computation there are implications that are not valid in the standard setting (e.g., robustness to linear tests implies robusteness to stronger tests). I would also stress that things we take for granted in the standard setting may not hold in the context of local computation (or may be hard to establish in it): e.g., amplification of the stretch of PRGs.

On the Power of Correlated Randomness in Secure Computation by Yuval Ishai, Eyal Kushilevitz, Sigurd Meldgaard, Claudio Orlandi and Anat Paskin-Cherniavsky

The model of correlated randomness may be viewed as "extending" a simple cryptographic primitive to performing more complex tasks (i.e., general MPC). Alternatively, one may view the correlated randomness as the outcome of a preprocessing stage, which is performed before the actual inputs are available. In any case, this model turns out to be very powerful: It allows for general MPC with communication that is linear in the input length (regardless of the circuit size), and it allows for perfectly secure computation of any unidirectional two-party functionalities (rather than statistically secure computation in which the communication must grow linearly with the security parameter that determines the error). In both results the correlated randomness has exponential length, and it is left open whether this is inherent.

Back to list of Oded's choices.