MarriageTheoremのこと

_ 職場が象の卵案件で修羅場に突入しかけていた。

_ IACR ePrint 2013/683まで確認済み、ECCC 2003年分まで確認済み

_ 気になった論文：Robust Pseudorandom Generators, Yuval Ishai and Eyal Kushilevitz and Xin Li and Rafail Ostrovsky and Manoj Prabhakaran and Amit Sahai and David Zuckerman, http://eprint.iacr.org/2013/671

Let $G:\bits^n\to\bits^m$ be a pseudorandom generator. We say that a circuit implementation of $G$ is {\em $(k,q)$-robust} if for every set $S$ of at most $k$ wires anywhere in the circuit, there is a set $T$ of at most $q|S|$ outputs, such that conditioned on the values of $S$ and $T$ the remaining outputs are pseudorandom. We initiate the study of robust PRGs, presenting explicit and non-explicit constructions in which $k$ is close to $n$, $q$ is constant, and $m>>n$. These include unconditional constructions of robust $r$-wise independent PRGs and small-bias PRGs, as well as conditional constructions of robust cryptographic PRGs.

In addition to their general usefulness as a more resilient form of PRGs, our study of robust PRGs is motivated by cryptographic applications in which an adversary has a local view of a large source of secret randomness. We apply robust $r$-wise independent PRGs towards reducing the randomness complexity of private circuits and protocols for secure multiparty computation, as well as improving the ``black-box complexity'' of constant-round secure two-party computation.