Computer Science Theory at Northeastern

Seminar

Click here to subscribe to our mailing list.
Click here to subscribe to our Google Calendar.

Theory Seminar

This semester the theory seminar will be every Wednesday from 12:00-1:30pm in West Village H 366 (map). The Theory Seminar will occur every week whether or not we have a speaker. If we do not have a speaker, we will have short presentations from students or faculty. Write to Jonathan Ullman with suggestions for speakers or food!

Fall Semester, 2017

 Dec 06, 201712:00PM Prashanth Vasudevan, MIT TBA 108 WVG Nov 29, 201712:00PM Ran Cohen, NEU From Fairness to Full Security in Multiparty Computation 366 WVH Abstract In the setting of secure multiparty computation (MPC), a set of mutually distrusting parties wish to jointly compute a function, while guaranteeing the privacy of their inputs and the correctness of the output. An MPC protocol is called fully secure if no adversary can prevent the honest parties from obtaining their outputs. A weaker definition is fairness ensuring that an adversary can prematurely abort the computation only before learning any new information. We present highly efficient transformations from fair computations to fully secure computations, assuming the fraction of honest parties is constant (e.g., 1% of the parties are honest). One application of these transformations is a new coin-flipping protocol, whose round complexity has a super-logarithmic dependency on the security parameter, improving over the linear dependency on the number of parties in Beimel, Omri, and Orlov (Crypto 2010). A second application is a new fully secure protocol for computing the Boolean OR function, with a super-constant round complexity, improving over the protocol of Gordon and Katz (TCC 2009) whose round complexity is linear in the number of corrupted parties. Finally, we prove that for some functions, a super-constant number of invocations of the fair computation is necessary for computing the function in a fully secure manner. This is a joint work with Eran Omri, Iftach Haitner, and Lior Rotem. Nov 15, 201712:00PM Wolfgang Gatterbauer, NEU Oblivious Bounds on the Probability of Boolean Functions 366 WVH Abstract We develop upper and lower bounds for the probability of monotone Boolean functions by treating multiple occurrences of variables as independent and assigning them new individual probabilities. We call this approach "dissociation" and give an exact characterization of optimal oblivious bounds, i.e. when the new probabilities are chosen independent of the probabilities of all other variables. Our motivation comes from the weighted model counting problem (or, equivalently, the problem of computing the probability of a Boolean function), which is #P-hard in general. By performing several dissociations, one can transform a Boolean formula whose probability is difficult to compute, into one whose probability is easy to compute, and which is guaranteed to provide an upper or lower bound on the probability of the original formula by choosing appropriate probabilities for the dissociated variables. Our bounds shed light on the connection between previous relaxation-based and model-based approximations and unify them as concrete choices in a larger design space. We also show how our theory allows a standard relational database management system to both upper and lower bound hard probabilistic queries in guaranteed polynomial time. Based on joint work with Dan Suciu from TODS 2014. Nov 08, 201712:00PM Siyao Guo, NEU The Power of Negations in Cryptography (and more) 366 WVH Abstract We initiate a quantitative study of the power of negations, asking how many negations are required to compute cryptographic primitives. We provide several lower bounds, some of them tight, for various cryptographic primitives and building blocks including one-way permutations, pseudorandom functions, small-bias generators, hard-core predicates, error-correcting codes, and randomness extractors. Among our results, we highlight the following. Unlike one-way functions, one-way permutations cannot be monotone. Pseudorandom functions require $\log n - O(1)$ negations (which is optimal up to the additive term). Error-correcting codes with linear distance require $\log n - O(1)$ negations (again, optimal up to the additive term). In addition, we will mention some recent results in understanding the power of negations from multiple angles including Boolean formulas and property testing. Based on join works with Clément L. Canonne, Elena Grigorescu, Ilan Komargodski, Akash Kumar, Tal Malkin, Igor C. Oliveria, Alon Rosen, and Karl Wimmer. Based on work in Paper 1, Paper 2, and Paper 3. Nov 01, 201712:00PM Theory Lunch - no talk 142 ISEC Oct 25, 201712:00PM Mika Göös, Harvard Monotone Circuit Lower Bounds from Resolution 366 WVH Abstract For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a "lifted" two-party version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols---or, equivalently, that a monotone function associated with F has large monotone circuit complexity. Our result extends to real monotone circuits, which yields new lower bounds for the Cutting Planes proof system. Joint work with Ankit Garg, Pritish Kamath, and Dmitry Sokolov. Oct 18, 201712:00PM Ali Vakilian, MIT Fractional Set Cover in the Streaming Model 366 WVH Abstract We study the Fractional Set Cover problem in the streaming model. That is, we consider the relaxation of the set cover problem over a universe of $n$ elements and a collection of $m$ sets, where each set can be picked fractionally, with a value in $[0, 1]$. We present a randomized $(1+ \epsilon)$-approximation algorithm that makes $p$ passes over the data, and uses $O(\textit{polylog} (m, n, 1/\epsilon)(mn^{(O(1/(p \epsilon))})+ n))$ memory space. The algorithm works in both the set arrival and the edge arrival models. To the best of our knowledge, this is the first streaming result for the fractional set cover problem. We obtain our results by employing the multiplicative weights update framework in the streaming settings. Oct 11, 201712:00PM Matt Dippel + Tanay Mehta Short Talks 366 WVH Oct 04, 201712:00PM Yashvanth Kondi Privacy-Free Garbled Circuits for Formulas: Size Zero and Information-Theoretic 366 WVH Abstract Garbled circuits are of central importance in cryptography, finding widespread application in secure computation, zero-knowledge (ZK) protocols, and verifiable outsourcing of computation to name a few. We are interested in a particular kind of garbling scheme, termed privacy-free in the literature. We show that Boolean formulas can be garbled information-theoretically in the privacy-free setting, producing no ciphertexts at all. Existing garbling schemes either rely on cryptographic assumptions (and thus require cryptographic operations to construct and evaluate garbled circuits), produce garbled circuits of non-zero size, or are restricted to low depth formulaic circuits. Our result has both theoretical and practical implications for garbled circuits as a primitive. On the theory front, our result breaks the known theoretical lower bound of one ciphertext for garbling an AND gate in this setting. As an interesting implication of producing size zero garbled circuits, our scheme scores adaptive security for free. On the practical side, our garbling scheme involves only cheap XOR operations and produces size zero garbled circuits. As a side result, we propose several interesting extensions of our scheme. Namely, we show how to garble threshold and high fan-in gates. An aspect of our garbling scheme that we believe is of theoretical interest is that it does not maintain the invariant that the garbled circuit evaluator must not at any point be in possession of both keys of any wire in the garbled circuit. Sep 27, 201712:00PM Ariel Hamlin SoK: Cryptographically Protected Database Search 366 WVH Abstract Protected database search systems cryptographically isolate the roles of reading from, writing to, and administering the database. This separation limits unnecessary administrator access and protects data in the case of system breaches. Since protected search was introduced in 2000, the area has grown rapidly; systems are offered by academia, start-ups, and established companies. However, there is no best protected search system or set of techniques. Design of such systems is a balancing act between security, functionality, performance, and usability. This challenge is made more difficult by ongoing database specialization, as some users will want the functionality of SQL, NoSQL, or NewSQL databases. This database evolution will continue, and the protected search community should be able to quickly provide functionality consistent with newly invented databases. At the same time, the community must accurately and clearly characterize the tradeoffs between different approaches. To address these challenges, we provide the following contributions: 1) An identification of the important primitive operations across database paradigms. We find there are a small number of base operations that can be used and combined to support a large number of database paradigms. 2) An evaluation of the current state of protected search systems in implementing these base operations. This evaluation describes the main approaches and tradeoffs for each base operation. Furthermore, it puts protected search in the context of unprotected search, identifying key gaps in functionality. 3) An analysis of attacks against protected search for different base queries. 4) A roadmap and tools for transforming a protected search system into a protected database, including an open-source performance evaluation platform and initial user opinions of protected search.