FOCS 2011
TechTalks from event: FOCS 2011
We will be uploading the videos for FOCS 2011 during the week of Nov 28th 2011. If you find any discrepancy, please let us know by clicking on report error link on talk page. If you did not permit the video to be published and by mistake we have published your talk, please notify us immediately at support AT weyond.com
10A

A Two Prover One Round Game with Strong SoundnessWe show that for any fixed prime $q \geq 5$ and constant $\zeta > 0$, it is NPhard to distinguish whether a two prover one round game with $q^6$ answers has value at least $1\zeta$ or at most $\frac{4}{q}$. The result is obtained by combining two techniques: (i) An Inner PCP based on the {\it point versus subspace} test for linear functions. The test is analyzed Fourier analytically. (ii) The Outer/Inner PCP composition that relies on a certain {\it subcode covering} property for Hadamard codes. This is a new and essentially blackbox method to translate a {\it codeword test} for Hadamard codes to a {\it consistency test}, leading to a full PCP construction. As an application, we show that unless NP has quasipolynomial time deterministic algorithms, theQuadratic Programming Problem is inapproximable within factor $(\log n)^{1/6  o(1)}$.

The Randomness Complexity of Parallel RepetitionConsider a $m$round interactive protocol with soundness error $1/2$. How much extra randomness is required to decrease the soundness error to $\delta$ through parallel repetition? Previous work shows that for \emph{publiccoin} interactive protocols with \emph{unconditional soundness}, $m \cdot O(\log (1/\delta))$ bits of extra randomness suffices. In this work, we initiate a more general study of the above question. \begin{itemize} \item We establish the first derandomized parallel repetition theorem for publiccoin interactive protocols with \emph{computational soundness} (a.k.a. arguments). The parameters of our result essentially matches the earlier works in the informationtheoretic setting. \item We show that obtaining even a sublinear dependency on the number of rounds $m$ (i.e., $o(m) \cdot \log(1/\delta)$) in either the informationtheoretic or computational settings requires proving $\P \neq \PSPACE$. \item We show that nontrivial derandomized parallel repetition for privatecoin protocols is impossible in the informationtheoretic setting, and requires proving $\P \neq \PSPACE$ in the computational setting. \end{itemize}

Privacy Amplification and NonMalleable Extractors Via Character SumsIn studying how to communicate over a public channel with an active adversary, Dodis and Wichs introduced the notion of a nonmalleable extractor. A nonmalleable extractor dramatically strengthens the notion of a strong extractor. A strong extractor takes two inputs, a weaklyrandom $x$ and a uniformly random seed $y$, and outputs a string which appears uniform, even given $y$. For a nonmalleable extractor $nmExt$, the output $nmExt(x,y)$ should appear uniform given $y$ as well as $nmExt(x,A(y))$, where $A$ is an arbitrary function with $A(y) \neq y$. We show that an extractor introduced by Chor and Goldreich is nonmalleable when the entropy rate is above half. It outputs a linear number of bits when the entropy rate is $1/2 + \alpha$, for any $\alpha>0$. Previously, no nontrivial parameters were known for any nonmalleable extractor. To achieve a polynomial running time when outputting many bits, we rely on a widelybelieved conjecture about the distribution of prime numbers in arithmetic progressions. Our analysis involves a character sum estimate, which may be of independent interest. Using our nonmalleable extractor, we obtain protocols for ``privacy amplification": key agreement between two parties who share a weaklyrandom secret. Our protocols work in the presence of an active adversary with unlimited computational power, and have optimal entropy loss. When the secret has entropy rate greater than $1/2$, the protocol follows from a result of Dodis and Wichs, and takes two rounds. When the secret has entropy rate $\delta$ for any constant~$\delta>0$, our new protocol takes $O(1)$ rounds. Our protocols run in polynomial time under the above wellknown conjecture about primes.

Stateless Cryptographic ProtocolsSecure computation protocols inherently involve multiple rounds of interaction among the parties where, typically a party has to keep a state about what has happened in the protocol so far and then \emph{wait} for the other party to respond. We study if this is inherent. In particular, we study the possibility of designing cryptographic protocols where the parties can be completely stateless and compute the outgoing message by applying a single fixed function to the incoming message (independent of any state). The problem of designing stateless secure computation protocols can be reduced to the problem of designing protocols satisfying the notion of resettable computation introduced by Canetti, Goldreich, Goldwasser and Micali (FOCS'01) and widely studied thereafter. The current start of art in resettable computation allows for construction of protocols which provide security only when a \emph{single predetermined} party is resettable. An exception is for the case of the zeroknowledge functionality for which a protocol in which both parties are resettable was recently obtained by Deng, Goyal and Sahai (FOCS'09). The fundamental question left open in this sequence of works is, whether fullyresettable computation is possible, when: \begin{enumerate} \item An adversary can corrupt any number of parties, and \item The adversary can reset any party to its original state during the execution of the protocol and can restart the protocol. \end{enumerate} In this paper, we resolve the above problem by constructing secure protocols realizing \emph{any} efficiently computable multiparty functionality in the plain model under standard cryptographic assumptions. First, we construct a FullyResettable Simulation Sound ZeroKnowledge (ssrsrZK) protocol. Next, based on these ssrsrZK protocols, we show how to compile any semihonest secure protocol into a protocol secure against fully resetting adversaries. Next, we study a seemingly unrelated open question: ``Does there exist a functionality which, in the concurrent setting, is impossible to securely realize using BB simulation but can be realized using NBB simulation?". We resolve the above question in the affirmative by giving an example of such a (reactive) functionality. Somewhat surprisingly, this is done by making a connection to the existence of a fully resettable simulation sound zeroknowledge protocol.

How to Store a Secret on Continually Leaky DevicesWe consider the question of how to store a value secretly on devices that continually leak information about their internal state to an external attacker. If the secret value is stored on a single device, and the attacker can leak even a single predicate of the internal state of that device, then she may learn some information about the secret value itself. Therefore, we consider a setting where the secret value is shared between multiple devices (or multiple components of one device), each of which continually leaks arbitrary adaptively chosen predicates of its individual state. Since leakage is continual, each device must also continually update its state so that an attacker cannot just leak it entirely one bit at a time. In our model, the devices update their state individually and asynchronously, without any communication between them. The update process is necessarily randomized, and its randomness can leak as well. As our main result, we construct a sharing scheme for two devices, where a constant fraction of the internal state of each device can leak in between and during updates. Our scheme has the structure of a publickey encryption, where one share is a secret key and the other is a ciphertext. As a contribution of independent interest, we also get publickey encryption in the continual leakage model, introduced by Brakerski et al. and Dodis et al. (FOCS '10). This scheme tolerates continual leakage on the secret key and the updates, and simplies the recent construction of Lewko, Lewko and Waters (STOC '11). For our main result, we also show how to update the ciphertexts of the encryption scheme so that the message remains hidden even if an attacker interleaves leakage on secret key and ciphertext shares. The security of our scheme is based on the linear assumption in primeorder bilinear groups. We also provide an extension to general access structures realizable by linear secret sharing schemes across many devices. The main advantage of this extension is that the state of some devices can be compromised entirely, while that of the all remaining devices is susceptible to continual leakage. Lastly, we show impossibility of information theoretic sharing schemes in our model, where continually leaky devices update their state individually.