International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Manoj Prabhakaran

Affiliation: University of Illinois

Publications

Year
Venue
Title
2019
EUROCRYPT
Uncovering Algebraic Structures in the MPC Landscape 📺
Navneet Agarwal Sanat Anand Manoj Prabhakaran
A fundamental problem in the theory of secure multi-party computation (MPC) is to characterize functions with more than 2 parties which admit MPC protocols with information-theoretic security against passive corruption. This question has seen little progress since the work of Chor and Ishai (1996), which demonstrated difficulties in resolving it. In this work, we make significant progress towards resolving this question in the important case of aggregating functionalities, in which m parties $$P_1,\dots ,P_m$$ P1,⋯,Pm hold inputs $$x_1,\dots ,x_m$$ x1,⋯,xm and an aggregating party $$P_0$$ P0 must learn $$f(x_1,\dots ,x_m)$$ f(x1,⋯,xm).We uncover a rich class of algebraic structures that are closely related to secure computability, namely, “Commuting Permutations Systems” (CPS) and its variants. We present an extensive set of results relating these algebraic structures among themselves and to MPC, including new protocols, impossibility results and separations. Our results include a necessary algebraic condition and slightly stronger sufficient algebraic condition for a function to admit information-theoretically secure MPC protocols.We also introduce and study new models of minimally interactive MPC (called UNIMPC and ), which not only help in understanding our positive and negative results better, but also open up new avenues for studying the cryptographic complexity landscape of multi-party functionalities. Our positive results include novel protocols in these models, which may be of independent practical interest.Finally, we extend our results to a definition that requires UC security as well as semi-honest security (which we term strong security). In this model we are able to carry out the characterization of all computable functions, except for a gap in the case of aggregating functionalities.
2018
PKC
Towards Characterizing Securely Computable Two-Party Randomized Functions
Deepesh Data Manoj Prabhakaran
A basic question of cryptographic complexity is to combinatorially characterize all randomized functions which have information-theoretic semi-honest secure 2-party computation protocols. The corresponding question for deterministic functions was answered almost three decades back, by Kushilevitz [Kus89]. In this work, we make progress towards understanding securely computable randomized functions. We bring tools developed in the study of completeness to bear on this problem. In particular, our characterizations are obtained by considering only symmetric functions with a combinatorial property called simplicity [MPR12].Our main result is a complete combinatorial characterization of randomized functions with ternary output kernels, that have information-theoretic semi-honest secure 2-party computation protocols. In particular, we show that there exist simple randomized functions with ternary output that do not have secure computation protocols. (For deterministic functions, the smallest output alphabet size of such a function is 5, due to an example given by Beaver [Bea89].)Also, we give a complete combinatorial characterization of randomized functions that have 2-round information-theoretic semi-honest secure 2-party computation protocols.We also give a counter-example to a natural conjecture for the full characterization, namely, that all securely computable simple functions have secure protocols with a unique transcript for each output value. This conjecture is in fact true for deterministic functions, and – as our results above show – for ternary functions and for functions with 2-round secure protocols.
2017
JOFC
2016
EUROCRYPT
2016
CRYPTO
2016
TCC
2016
TCC
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
TCC
2015
TCC
2015
PKC
2015
EUROCRYPT
2015
CRYPTO
2014
CRYPTO
2014
EUROCRYPT
2014
TCC
2014
TCC
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2013
CRYPTO
2012
CRYPTO
2011
TCC
2011
CRYPTO
2011
EUROCRYPT
2011
JOFC
2010
CRYPTO
2010
EPRINT
A Zero-One Law for Deterministic 2-Party Secure Computation
Hemanta K. Maji Manoj Prabhakaran Mike Rosulek
We use security in the Universal Composition framework as a means to study the ``cryptographic complexity'' of 2-party secure computation tasks (functionalities). We say that a functionality $F$ {\em reduces to} another functionality $G$ if there is a UC-secure protocol for $F$ using ideal access to $G$. This reduction is a natural and fine-grained way to compare the relative complexities of cryptographic tasks. There are two natural ``extremes'' of complexity under the reduction: the {\em trivial} functionalities, which can be reduced to any other functionality; and the {\em complete} functionalities, to which any other functionality can be reduced. In this work we show that under a natural computational assumption (the existence of a protocol for oblivious transfer secure against semi-honest adversaries), there is a {\bf zero-one law} for the cryptographic complexity of 2-party 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 multi-party 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 automata-theoretic methodology for classifying and studying their cryptographic properties. Consequently, we completely characterize the reactive behaviors that lead to cryptographic non-triviality. 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)).
2009
TCC
2009
TCC
2008
ASIACRYPT
2008
CRYPTO
2008
CRYPTO
2008
EPRINT
Homomorphic Encryption with CCA Security
Manoj Prabhakaran Mike Rosulek
We address the problem of constructing public-key encryption schemes that meaningfully combine useful {\em computability features} with {\em non-malleability}. In particular, we investigate schemes in which anyone can change an encryption of an unknown message $m$ into an encryption of $T(m)$ (as a {\em feature}), for a specific set of allowed functions $T$, but the scheme is ``non-malleable'' with respect to all other operations. We formulate precise definitions that capture these intuitive requirements and also show relationships among our new definitions and other more standard ones (IND-CCA, gCCA, and RCCA). We further justify our definitions by showing their equivalence to a natural formulation of security in the Universally Composable framework. We also consider extending the definitions to features which combine {\em multiple} ciphertexts, and show that a natural definition is unattainable for a useful class of features. Finally, we describe a new family of encryption schemes that satisfy our definitions for a wide variety of allowed transformations $T$, and which are secure under the standard Decisional Diffie-Hellman (DDH) assumption.
2008
EPRINT
Attribute-Based Signatures: Achieving Attribute-Privacy and Collusion-Resistance
Hemanta Maji Manoj Prabhakaran Mike Rosulek
We introduce a new and versatile cryptographic primitive called {\em Attribute-Based Signatures} (ABS), in which a signature attests not to the identity of the individual who endorsed a message, but instead to a (possibly complex) claim regarding the attributes she posseses. ABS offers: * A strong unforgeability guarantee for the verifier, that the signature was produced by a {\em single} party whose attributes satisfy the claim being made; i.e., not by a collusion of individuals who pooled their attributes together. * A strong privacy guarantee for the signer, that the signature reveals nothing about the identity or attributes of the signer beyond what is explicitly revealed by the claim being made. We formally define the security requirements of ABS as a cryptographic primitive, and then describe an efficient ABS construction based on groups with bilinear pairings. We prove that our construction is secure in the generic group model. Finally, we illustrate several applications of this new tool; in particular, ABS fills a critical security requirement in attribute-based messaging (ABM) systems. A powerful feature of our ABS construction is that unlike many other attribute-based cryptographic primitives, it can be readily used in a {\em multi-authority} setting, wherein users can make claims involving combinations of attributes issued by independent and mutually distrusting authorities.
2008
EPRINT
Secure Arithmetic Computation with No Honest Majority
Yuval Ishai Manoj Prabhakaran Amit Sahai
We study the complexity of securely evaluating arithmetic circuits over finite rings. This question is motivated by natural secure computation tasks. Focusing mainly on the case of {\em two-party} protocols with security against {\em malicious} parties, our main goals are to: (1) only make black-box calls to the ring operations and standard cryptographic primitives, and (2) minimize the number of such black-box calls as well as the communication overhead. We present several solutions which differ in their efficiency, generality, and underlying intractability assumptions. These include: \begin{itemize} \item An {\em unconditionally secure} protocol in the OT-hybrid model which makes a black-box use of an arbitrary ring $R$, but where the number of ring operations grows linearly with (an upper bound on) $\log|R|$. \item Computationally secure protocols in the OT-hybrid model which make a black-box use of an underlying ring, and in which the numberof ring operations does not grow with the ring size. The protocols rely on variants of previous intractability assumptions related to linear codes. In the most efficient instance of these protocols, applied to a suitable class of fields, the (amortized) communication cost is a constant number of field elements per multiplication gate and the computational cost is dominated by $O(\log k)$ field operations per gate, where$k$ is a security parameter. These results extend a previous approach of Naor and Pinkas for secure polynomial evaluation ({\em SIAM J.\ Comput.}, 35(5), 2006). \item A protocol for the rings $\mathbb{Z}_m=\mathbb{Z}/m\mathbb{Z}$ which only makes a black-box use of a homomorphic encryption scheme. When $m$ is prime, the (amortized) number of calls to the encryption scheme for each gate of the circuit is constant. \end{itemize} All of our protocols are in fact {\em UC-secure} in the OT-hybrid model and can be generalized to {\em multiparty} computation with an arbitrary number of malicious parties.
2008
EPRINT
Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation
Hemanta Maji Manoj Prabhakaran Mike Rosulek
In symmetric secure function evaluation (SSFE), Alice has an input $x$, Bob has an input $y$, and both parties wish to securely compute $f(x,y)$. We classify these functions $f$ according to their ``cryptographic complexities,'' and show that the landscape of complexity among these functions is surprisingly rich. We give combinatorial characterizations of the SSFE functions $f$ that have passive-secure protocols, and those which are protocols secure in the standalone setting. With respect to universally composable security (for unbounded parties), we show that there is an infinite hierarchy of increasing complexity for SSFE functions, That is, we describe a family of SSFE functions $f_1, f_2, \ldots$ such that there exists a UC-secure protocol for $f_i$ in the $f_j$-hybrid world if and only if $i \le j$. Our main technical tool for deriving complexity separations is a powerful protocol simulation theorem which states that, even in the strict setting of UC security, the canonical protocol for $f$ is as secure as any other protocol for $f$, as long as $f$ satisfies a certain combinatorial characterization. We can then show intuitively clear impossibility results by establishing the combinatorial properties of $f$ and then describing attacks against the very simple canonical protocols, which by extension are also feasible attacks against {\em any} protocol for the same functionality.
2007
CRYPTO
2007
EPRINT
Rerandomizable RCCA Encryption
Manoj Prabhakaran Mike Rosulek
We give the first perfectly rerandomizable, Replayable-CCA (RCCA) secure encryption scheme, positively answering an open problem of Canetti et al. [CRYPTO 2003]. Our encryption scheme, which we call the Double-strand Cramer-Shoup scheme, is a non-trivial extension of the popular Cramer-Shoup encryption. Its security is based on the standard DDH assumption. To justify our definitions, we define a powerful "Replayable Message Posting" functionality in the Universally Composable (UC) framework, and show that any encryption scheme that satisfies our definitions of rerandomizability and RCCA security is a UC-secure implementation of this functionality. Finally, we enhance the notion of rerandomizable RCCA security by adding a receiver-anonymity (or key-privacy) requirement, and show that it results in a correspondingly enhanced UC functionality. We leave open the problem of constructing a scheme that achieves this enhancement.
2007
EPRINT
Statistically Hiding Sets
Manoj Prabhakaran Rui Xue
Abstract: Zero-knowledge set, a primitive introduced by Micali, Rabin, and Kilian (FOCS 2003), enables a prover to commit a set to a verifier, without revealing even the size of the set. Later the prover can give zero-knowledge proofs to convince the verifier of membership/non-membership of elements in/not in the committed set. We present a new primitive called {\em Statistically Hiding Sets} (SHS), similar to zero-knowledge sets, but providing an information theoretic hiding guarantee. This is comparable to relaxing zero-knowledge proofs to {\em witness independent proofs}. More precisely, we continue to use the simulation paradigm for our definition, but do not require the simulator (nor the distinguisher) to be efficient. We present a new scheme for statistically hiding sets, which does not fit into the ``Merkle-tree/mercurial-commitment'' paradigm used for {\em all} zero-knowledge set constructions so far. This not only provides some efficiency gains compared to the best possible schemes in that paradigm, but also lets us provide {\em statistical} hiding, without the prover having to maintain growing amounts of state with each new proof; this is not known to be possible with the previous approach. Our construction is based on an algebraic tool called {\em trapdoor DDH groups} (TDG), introduced recently by Dent and Galbraith (ANTS 2006). Ours is perhaps the first non-trivial application of this tool. However the specific hardness assumptions we associate with TDG are different, and of a strong nature --- strong RSA and a knowledge-of-exponent assumption. Our new knowledge-of-exponent assumption may be of independent interest.
2006
EUROCRYPT
2006
TCC
2006
EPRINT
Concurrent Non-Malleable Zero Knowledge
Boaz Barak Manoj Prabhakaran Amit Sahai
We provide the first construction of a concurrent and non-malleable zero knowledge argument for every language in NP. We stress that our construction is in the plain model with no common random string, trusted parties, or super-polynomial simulation. That is, we construct a zero knowledge protocol $\Pi$ such that for every polynomial-time adversary that can adaptively and concurrently schedule polynomially many executions of $\Pi$, and corrupt some of the verifiers and some of the provers in these sessions, there is a polynomial-time simulator that can simulate a transcript of the entire execution, along with the witnesses for all statements proven by a corrupt prover to an honest verifier. Our security model is the traditional model for concurrent zero knowledge, where the statements to be proven by the honest provers are fixed in advance and do not depend on the previous history (but can be correlated with each other); corrupted provers, of course, can chose the statements adaptively. We also prove that there exists some functionality F (a combination of zero knowledge and oblivious transfer) such that it is impossible to obtain a concurrent non-malleable protocol for F in this model. Previous impossibility results for composable protocols ruled out existence of protocols for a wider class of functionalities (including zero knowledge!) but only if these protocols were required to remain secure when executed concurrently with arbitrarily chosen different protocols (Lindell, FOCS 2003) or if these protocols were required to remain secure when the honest parties' inputs in each execution are chosen adaptively based on the results of previous executions (Lindell, TCC 2004). We obtain an $\Tilde{O}(n)$-round protocol under the assumption that one-to-one one-way functions exist. This can be improved to $\Tilde{O}(k\log n)$ rounds under the assumption that there exist $k$-round statistically hiding commitment schemes. Our protocol is a black-box zero knowledge protocol.
2005
TCC
2005
EPRINT
Concurrent Composition of Secure Protocols in the Timing Model
Yael Kalai Yehuda Lindell Manoj Prabhakaran
In the setting of secure multiparty computation, a set of mutually distrustful parties wish to securely compute some joint function of their inputs. In the stand-alone case, it has been shown that {\em every} efficient function can be securely computed. However, in the setting of concurrent composition, broad impossibility results have been proven for the case of no honest majority and no trusted setup phase. These results hold both for the case of general composition (where a secure protocol is run many times concurrently with arbitrary other protocols) and self composition (where a single secure protocol is run many times concurrently). In this paper, we investigate the feasibility of obtaining security in the concurrent setting, assuming that each party has a local clock and that these clocks proceed at approximately the same rate. We show that under this mild timing assumption, it is possible to securely compute {\em any} multiparty functionality under concurrent \emph{self} composition. We also show that it is possible to securely compute {\em any} multiparty functionality under concurrent {\em general} composition, as long as the secure protocol is run only with protocols whose messages are delayed by a specified amount of time. On the negative side, we show that it is impossible to achieve security under concurrent general composition with no restrictions whatsoever on the network (like the aforementioned delays), even in the timing model.
2005
EPRINT
Resource Fairness and Composability of Cryptographic Protocols
We introduce the notion of {\em resource-fair} protocols. Informally, this property states that if one party learns the output of the protocol, then so can all other parties, as long as they expend roughly the same amount of resources. As opposed to similar previously proposed definitions, our definition follows the standard simulation paradigm and enjoys strong composability properties. In particular, our definition is similar to the security definition in the universal composability (UC) framework, but works in a model that allows any party to request additional resources from the environment to deal with dishonest parties that may prematurely abort. In this model we specify the ideally fair functionality as allowing parties to ``invest resources'' in return for outputs, but in such an event offering all other parties a fair deal. (The formulation of fair dealings is kept independent of any particular functionality, by defining it using a ``wrapper.'') Thus, by relaxing the notion of fairness, we avoid a well-known impossibility result for fair multi-party computation with corrupted majority; in particular, our definition admits constructions that tolerate arbitrary number of corruptions. We also show that, as in the UC framework, protocols in our framework may be arbitrarily and concurrently composed. Turning to constructions, we define a ``commit-prove-fair-open'' functionality and design an efficient resource-fair protocol that securely realizes it, using a new variant of a cryptographic primitive known as ``time-lines.'' With (the fairly wrapped version of) this functionality we show that some of the existing secure multi-party computation protocols can be easily transformed into resource-fair protocols while preserving their security.
2004
EUROCRYPT
2004
EPRINT
Positive Results and Techniques for Obfuscation
Benjamin Lynn Manoj Prabhakaran Amit Sahai
Informally, an obfuscator $\Obf$ is an efficient, probabilistic ``compiler'' that transforms a program $P$ into a new program $\Obf(P)$ with the same functionality as $P$, but such that $\Obf(P)$ protects any secrets that may be built into and used by $P$. Program obfuscation, if possible, would have numerous important cryptographic applications, including: (1) ``Intellectual property'' protection of secret algorithms and keys in software, (2) Solving the long-standing open problem of homomorphic public-key encryption, (3) Controlled delegation of authority and access, (4) Transforming Private-Key Encryption into Public-Key Encryption, and (5) Access Control Systems. Unfortunately however, program obfuscators that work on arbitrary programs cannot exist [Barak et al]. No positive results for program obfuscation were known prior to this work. In this paper, we provide the first positive results in program obfuscation. We focus on the goal of access control, and give several provable obfuscations for complex access control functionalities, in the random oracle model. Our results are obtained through non-trivial compositions of obfuscations; we note that general composition of obfuscations is impossible, and so developing techniques for composing obfuscations is an important goal. Our work can also be seen as making initial progress toward the goal of obfuscating finite automata or regular expressions, an important general class of machines which are not ruled out by the impossibility results of Barak et al. We also note that our work provides the first formal proof techniques for obfuscation, which we expect to be useful in future work in this area.
2004
EPRINT
New Notions of Security: Achieving Universal Composability without Trusted Setup
Manoj Prabhakaran Amit Sahai
We propose a modification to the framework of Universally Composable (UC) security [Canetti'01]. Our new notion, involves comparing the protocol executions with an ideal execution involving ideal functionalities (just as in UC-security), but allowing the environment and adversary access to some super-polynomial computational power. We argue the meaningfulness of the new notion, which in particular subsumes many of the traditional notions of security. We generalize the Universal Composition theorem of [Canetti'01] to the new setting. Then under new computational assumptions, we realize secure multi-party computation (for static adversaries) without a common reference string or any other set-up assumptions, in the new framework. This is known to be impossible under the UC framework.
2002
EPRINT
Concurrent Zero Knowledge Proofs with Logarithmic Round-Complexity
Manoj Prabhakaran Amit Sahai
We consider the problem of constructing Concurrent Zero Knowledge Proofs, in which the fascinating and useful ``zero knowledge'' property is guaranteed even in situations where multiple concurrent proof sessions are executed with many colluding dishonest verifiers. Canetti et al. show that black-box concurrent zero knowledge proofs for non-trivial languages require $\tilde\Omega(\log k)$ rounds where $k$ is the security parameter. Till now the best known upper bound on the number of rounds for NP languages was $\omega(\log^2 k)$, due to Kilian, Petrank and Richardson. We establish an upper bound of $\omega(\log k)$ on the number of rounds for NP languages, thereby closing the gap between the upper and lower bounds, up to a $\omega(\log\log k)$ factor.

Program Committees

TCC 2018 (Program chair)
Crypto 2016
Eurocrypt 2015
Asiacrypt 2013
Crypto 2013
TCC 2011
Asiacrypt 2009
TCC 2009
Asiacrypt 2008
Crypto 2008
TCC 2006