Many problems that we'd like to be able to solve with computers seem to be intrinsically hard; there seems to be no way of solving them efficiently. Cryptography is the study of how to leverage these computationally hard problems to control access to information. We design systems for which violating our desired security properties is equivalent to solving one of these intractable problems.
Most of my research has focused on the problem of secure computation: how can we perform arbitrary computations on data without actually seeing the data? What if the data is distributed among many mutually distrusting parties, some of whom might want to undermine the computation?
Contact
 Email: rosulekm@eecs.oregonstate.edu
 Office: KEC 3063
 Phone: (541) 7373617
Students
Current students: Zhangxiang Hu (PhD)
 Brent Carmer (MS)
Publications
Also: DBLP, Google scholar
 FleXOR: Flexible garbling for XOR gates that beats freeXOR

Vladimir Kolesnikov, Payman Mohassel, & Mike Rosulek.
In CRYPTO 2014.
[▾ abstract] [full version] [Aarhus MPC workshop slides]  MultiParty Computation for Polynomials and Branching Programs without Simultaneous Interaction

Dov Gordon, Tal Malkin, Mike Rosulek, & Hoeteck Wee.
In Eurocrypt 2013.
[▾ abstract] [full version]  Evaluating any multivariate polynomial $F(x_1, \ldots, x_n)$ (modulo a large RSA modulus $N$), where the parties each hold an input $x_i$.
 Evaluating any read once branching program over the parties' inputs.
 Characterizing the Cryptographic Properties of Reactive 2Party Functionalities

R. Amzi Jeffs & Mike Rosulek.
In TCC 2013.
[▾ abstract] [author copy of proceedings version]  A Unified Characterization of Completeness and Triviality for Secure Function Evaluation

Hemanta Maji, Manoj Prabhakaran & Mike Rosulek.
In Indocrypt 2012.
[▾ abstract] [proceedings $]  An SFE functionality is complete for security against passive corruptions if and only if it is not simple.
 A deterministic SFE functionality is complete for security against active corruptions if and only if it has a core that is not simple. We conjecture that this characterization extends to randomized SFE as well.
 Must you know the code of f to securely compute f?

Mike Rosulek.
In CRYPTO 2012.
[▾ abstract] [revised/full version] [slides] [▾ video] [proceedings $]  A complete characterization of the 2party tasks which admit such security against semihonest adversaries. The characterization is inspired by notions of autoreducibility from computational complexity theory. From this characterization, we show a class of pseudorandom functions that cannot be securely evaluated (when one party holds the seed and the other holds the input) without "knowing" the code of the function in question. On the positive side, we show a class of functions (related to blind signatures) that can indeed be securely computed without ``knowing'' the code of the function.
 Sufficient conditions for such security against malicious adversaries, also based on autoreducibility. We show that it is not possible to prove membership in the image of a oneway function in zeroknowledge, without "knowing" the code of the oneway function.
 Universal Composability from Essentially Any Trusted Setup

Mike Rosulek.
In CRYPTO 2012.
[▾ abstract] [full version] [slides] [▾ video] [proceedings $]  Complexity of MultiParty Computation Functionalities
 Hemanta Maji, Manoj Prabhakaran, and Mike Rosulek.
Book chapter in Secure MultiParty Computation, eds. M Prabhakaran & A Sahai. IOS Press. 2013.
[▾ abstract] [publisher page] [eprint version]  Which functionalities are securely realizable (or are "trivial"  i.e., can be reduced to any functionality)?
 Which functionalities are "complete"  i.e., those to which any functionality can be reduced?
 More generally, which functionalities are reducible to which? Outside of triviality and completeness, this question is relatively less explored.
 Exploring the Limits of Common Coins Using Frontier Analysis of Protocols

Hemanta Maji, Pichayoot Ouppaphan, Manoj Prabhakaran & Mike Rosulek.
In TCC 2011.
[▾ abstract] [full version] [proceedings]  AttributeBased Signatures

Hemanta Maji, Manoj Prabhakaran & Mike Rosulek.
In CTRSA 2011.
[▾ abstract] [full version] [proceedings $]  A ZeroOne Law for Cryptographic Complexity with Respect to Computational UC Security

Hemanta Maji, Manoj Prabhakaran & Mike Rosulek.
In CRYPTO 2010.
[▾ abstract] [full version] [proceedings]  Cryptographic Complexity Classes and Computational Intractability Assumptions

Hemanta Maji, Manoj Prabhakaran & Mike Rosulek.
In ICS 2010.
[▾ abstract] [full version] [proceedings]  Complexity of Multiparty Computation Problems: The Case of 2Party Symmetric Secure Function Evaluation

Hemanta Maji, Manoj Prabhakaran & Mike Rosulek.
In TCC 2009.
[▾ abstract] [full version] [proceedings]  Towards Robust Computation on Encrypted Data

Manoj Prabhakaran & Mike Rosulek.
In ASIACRYPT 2008.
[▾ abstract] [proceedings] [slides]  Cryptographic Complexity of Multiparty Computation Problems: Classifications and Separations

Manoj Prabhakaran & Mike Rosulek.
In CRYPTO 2008.
[▾ abstract] [full version] [slides] [proceedings]  Homomorphic Encryption with CCA Security

Manoj Prabhakaran & Mike Rosulek.
In ICALP 2008.
[▾ abstract] [full version] [slides] [proceedings $]  Harvesting Credentials in Trust Negotiation as an HonestButCurious Adversary

Lars Olson, Mike Rosulek & Marianne Winslett.
In WPES 2007.
[▾ abstract] [tech report] [proceedings $]  Rerandomizable RCCA Encryption

Manoj Prabhakaran & Mike Rosulek.
In CRYPTO 2007.
[▾ abstract] [full version] [slides] [proceedings]
In this work we present a suite of new, simple and efficient protocols for secure computation in this ``onepass'' model. We give protocols that obtain optimal privacy for the following general tasks:
We present new combinatorial characterizations for 2party reactive functionalities, which we model as finite automata. We characterize the functionalities that have passivesecure protocols, and those which are complete with respect to passive adversaries. Both characterizations are in the informationtheoretic setting.
Finally, we apply our new notions of isomorphism to reduce the problem of characterization of trivial functionalities (i.e., those securely realizable without setups) for the case of general SFE to the same problem for the case of simple symmetric SFE.
In other settings throughout cryptography, blackbox constructions invariably lead to better practical efficiency than comparable nonblackbox constructions. Could secure computation protocols similarly be made more practical by eliminating their dependence on a circuit representation of the target function? Or, in other words, must one know the code of $f$ to securely evaluate $f$?
In this work we initiate the theoretical study of this question. We show the following:
The main technical contribution in this work is an almosttotal characterization of completeness for 2party setups. Our characterization treats setup functionalities as blackboxes, and therefore is the first work to classify completeness of {\em arbitrary setup functionalities} (i.e., randomized, reactive, and having behavior that depends on the global security parameter).
We treat separately the results on twoparty functionalities, for which the cryptographic complexity is much better understood. In particular, we present unified combinatorial characterizations of completeness and triviality for secure function evaluation using notions of isomorphism and the common information functionality (called the kernel) of a given functionality. Beyond completeness and triviality, we also discuss results on general reducibility, and, in the computationally bounded setting, the connection between these reductions and computational hardness assumptions.
We briefly discuss results on reactive functionalities, which are much less studied than nonreactive (secure function evaluation) functionalities. Finally, we conclude with a selection of open problems.
To obtain these impossibility results, we employ a recently developed protocol analysis technique, which we call the {\em frontier analysis}. This involves analyzing carefully defined ``frontiers'' in a weighted tree induced by the protocol's execution (or executions, with various inputs), and establishing various properties regarding one or more such frontiers. We demonstrate the versatility of this technique by employing carefully chosen frontiers to derive the different results. To analyze randomized functionalities we introduce a frontier argument that involves a geometric analysis of the space of probability distributions.
Finally, we relate our results to computational intractability questions. We give an equivalent formulation of the ``cryptomania assumption'' (that there is a semihonest or standalone secure oblivious transfer protocol) in terms of UCsecure reduction among randomized functionalities. Also, we provide an {\em unconditional result} on the uselessness of common randomness, even in the computationally bounded setting.
Our results make significant progress towards understanding the exact power of shared randomness in cryptography. To the best of our knowledge, our results are the first to comprehensively characterize the power of large classes of randomized functionalities.
We give a general framework for constructing ABS schemes, and then show several practical instantiations based on groups with bilinear pairing operations, under standard assumptions. Further, we give a construction which is secure even against a malicious attribute authority, but the security for this scheme is proven in the generic group model. We describe several practical problems that motivated this work, and how ABS can be used to solve them. Also, we show how our techniques allow us to extend GrothSahai NIZK proofs to be simulationextractable and identitybased with low overhead.
In this work we show that under a natural computational assumption (the existence of a protocol for oblivious transfer secure against semihonest adversaries), there is a {\bf zeroone law} for the cryptographic complexity of 2party deterministic functionalities. Namely, {\em every such functionality is either trivial or complete.} No other qualitative distinctions exist among functionalities, under this computational assumption.
While nearly all previous work classifying multiparty computation functionalities has been restricted to the case of secure function evaluation, our results are the first to consider completeness of arbitrary {\em reactive} functionalities, which receive input and give output repeatedly throughout several rounds of interaction. One important technical contribution in this work is to initiate the comprehensive study of the cryptographic properties of reactive functionalities. We model these functionalities as finite automata and develop an automatatheoretic methodology for classifying and studying their cryptographic properties. Consequently, we completely characterize the reactive behaviors that lead to cryptographic nontriviality. Another contribution of independent interest is to optimize the hardness assumption used by Canetti et al.\ (STOC 2002) in showing that the common random string functionality is complete (a result independently obtained by Damg{\aa}rd et al.\ (TCC 2010)).
We first aim to understand the “cryptographic complexity” of various tasks, independent of any computational assumptions. In our framework the cryptographic tasks are modeled as multi party computation functionalities. We consider a universally composable secure protocol for one task given access to another task as the most natural complexity reduction between the two tasks. Some of these cryptographic complexity reductions are unconditional, others are unconditionally impossible, but the vast majority appear to depend on computational assumptions; it is this relationship with computational assumptions that we study.
In our detailed investigation of large classes of 2party functionalities, we find that every reduction we are able to classify turns out to be unconditionally true or false, or else equivalent to the existence of oneway functions (OWF) or of semihonest (equivalently, standalonesecure) oblivious transfer protocols (shOT). This leads us to conjecture that there are only a small finite number of distinct computational assumptions that are inherent among the infinite number of different cryptographic reductions in our framework.
If indeed only a few computational intractability assumptions manifest in this framework, we propose that they are of an extraordinarily fundamental nature, since the framework contains a large variety of cryptographic tasks, and was formulated without regard to any of the prevalent computational intractability assumptions.
Our first main tool is the notion of {\em splittability}, which is an exact characterization of realizability in the UC framework with respect to a large class of communication channel functionalities. Using this characterization, we can rederive all previouslyknown impossibility results as immediate and simple corollaries. We also complete the combinatorial characterization of 2party secure function evaluation initiated by \cite{CanettiKuLi03} and partially extend the combinatorial conditions to the multiparty setting.
Our second main tool is the notion of {\em deviationrevealing} functionalities, which allows us to translate complexity separations in simpler MPC settings (such as the honestbutcurious corruption model) to the standard (malicious) setting. Applying this tool, we demonstrate the existence of functionalities which are neither realizable nor complete, in the unbounded computation model.
Other Projects
 Vamonos
 Browserbased platform for algorithm visualization
 An Annotated Bibliography of Practical Secure Computation
 Reference resource for researchers in secure computation
Professional Activities
Program committees: Other service: IACR communications secretaryOther Writings
 Correspondences regarding cryptography between John Nash and the NSA

Transcribed & typeset by Mike Rosulek.
[▾ abstract] [pdf] [originals]  The Structure of Secure MultiParty Computation

Mike Rosulek.
PhD dissertation, 2009. University of Illinois
[▾ abstract] [singlespaced, hyperref] [official version]  We give the first alternate characterization of secure realizability in the framework of universally composable (UC) security. This is the first characterization in any model to consider completely arbitrary computational tasks and completely arbitrary communication channels.
 The most longstanding class of computational tasks studied are those in which two parties evaluate a deterministic function. For these tasks, we give the first complete, combinatorial characterizations of secure realizability in the passive, standalone, and universally composable security models, against computationally unbounded adversaries.
 Say that a task \G has ``as much cryptographic complexity'' as another task \F if there is a secure protocol for \F that uses access to a secure implementation of \G. We show that there is an infinite hierarchy of tasks with {\em strictly increasing} cryptographic complexities, with respect to computationally unbounded security. We also show that there exist tasks whose cryptographic complexities are incomparable.
 In contrast, we show that under a standard cryptographic assumption, there exist only {\em two} distinct levels of cryptographic complexity with respect to polynomialtime security. Every task either has a trivial protocol using plain communication channels, or is complete (i.e., given access to a secure implementation of this task, there are secure protocols for all other tasks). This is the first result to derive a characterization of completeness for a class of arbitrary {\em interactive} tasks.
 We give a construction of a homomorphic encryption scheme in which the allowed homomorphic operation is as fullfeatured as possible  namely, one can derive a {\em correctlydistributed} encryption of $f(m)$ given an encryption of unknown message $m$, for some functions $f$  yet it is computationally infeasible to generate a ciphertext that is related to other ciphertexts in any other way. Our contributions involve developing new appropriate security definitions as well as new constructions.
 We show that schemes with such powerful security guarantees can be used to build conceptually simple, efficient, UCsecure protocols for verifiable computations on encrypted data. We show protocols for two tasks related to aggregating encrypted data.
These correspondences, recently declassified by the NSA, have been transcribed and typeset in this document.
Other Talks
 Reconciling Nonmalleability and Homomorphic Encryption

Crypto in the Clouds workshop, August 2009.
[slides]
Updated talk at University of Maryland cryptography seminar, January 2012. [slides]  ZeroKnowledge Proofs, with Applications to Sudoku and Where's Waldo
 Educational talk, University of Montana, December 2008. [slides]
 The State of the Art in Program Obfuscation
 UIUC CS theory seminar, September 2006. [slides]
Personal
 My personal website, which contains some of my photography and surprisingly little else.
 My Flickr page, in case you want to see even more of my photography.