Muthuramakrishnan Venkitasubramaniam
621 Computer Sciences Building
University of Rochester, Rochester, NY 14627-0226

I am an Assistant Professor in the Department of Computer Science at University of Rochester since August 2011. I got my Ph.D in the Computer Science Department at Cornell University under the supervision of Rafael Pass and spent a year as a CI Fellow at NYU and Columbia University. My research interests lie in cryptography, network security and complexity theory. My research is funded by the National Science Foundation and Google Faculty Research Award.


PhD Students

  • Scott Ames (2011 - Present)
  • Mohammad H Faghihi (2016 - Present)

Program Committees

Recent Talks


Publications: (click title for abstract)

Equivocating Yao: Constant-Rounds Adaptively Secure Multiparty Computation in the Plain Model. (STOC 2017)
R. Canetti, O. Poburinnaya, M. Venkitasubramaniam.

Yao's garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable two-message, two-party secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds?

We answer this question in the affirmative. We define a new type of encryption, called functionally equivocal encryption (FEE),and show that when Yao's scheme is implemented with an FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one way function.

Combining our scheme with non-committing encryption, we obtain the first two-message, two-party computation protocol, and the first constant-round multiparty computation protocol, in the plain model, that are secure against semi-honest adversaries who can adaptively corrupt all parties. A number of extensions and applications are described within.


Better Two-Round Adaptive Multi-Party Computation. (PKC 2017)
R. Canetti, O. Poburinnaya, M. Venkitasubramaniam.

The only known two-round multi-party computation protocol that withstands adaptive corruption of all parties is the ingenious protocol of Garg and Polychroniadou [GP] (TCC 15). We present protocols that improve on the GP protocol in a number of ways. First, concentrating on the semi-honest case and taking a different approach than GP, we show a two-round, adaptively secure protocol where:
  • Only a global (i.e., non-programmable) reference string is needed. In contrast, in GP the reference string is programmable, even in the semi-honest case.
  • Only polynomially-secure indistinguishability obfuscation for circuits and injective one way functions are assumed. In GP, sub-exponentially secure IO is assumed.
Second, in the malicious setting, we show how to make the GP protocol have only RAM complexity. For this we construct the first statistically-sound non-interactive Zero-Knowledge scheme with RAM complexity.

Scalable Multi-Party Private Set-Intersection (PKC 2017)
C. Hazay, M. Venkitasubramaniam.

In this work we study the problem of private set-intersection in the multi-party setting and design two protocols with the following improvement compared to prior work. First, our protocols take a new approach of leveraging the 2PC protocol of Freedman, Nissim and Pinkas (Eurocrypt 2004) and minimize the usage of a broadcast channel, where our semi-honest protocol does not make any use of such a channel. In addition, the communication complexity of our protocols scale with the number of parties.

More concretely, (1) our first semi-honest secure protocol with communication complexity that is linear in the input sizes, namely $O(\sum_{i=1}^n m_i)$ where $m_i$ is the size of $P_i$'s input set, whereas the computational overhead is quadratic in the input sizes only for a designated party, and linear for the rest. (2) Our second protocol is proven secure in the malicious setting. This protocol induces communication complexity $O(\sum_{i=1}^2 m_i + n^2)$ where $n$ is the number of parties.

Constant-Round Adaptively Secure Protocols in the Tamper-Proof Hardware Model (PKC 2017)
C. Hazay, A. Polychroniadou, M. Venkitasubramaniam.

Achieving constant-round adaptively secure protocols (where all parties can be corrupted) in the plain model is a notoriously hard problem. Very recently, three works published in TCC 2015 (Dachman-Soled et al., Garg and Polychroniadou, Canetti et al.), solved the problem in the Common Reference String (CRS) model. In this work, we present a constant-round adaptive UC-secure computation protocol for all well-formed functionalities in the tamper-proof hardware model using stateless tokens from only one-way functions. In contrast, all prior works in the CRS model require very strong assumptions, in particular, the existence of indistinguishability obfuscation. As a corollary to our techniques, we present the first adaptively secure protocols in the Random Oracle Model (ROM) with round complexity proportional to the depth of circuit implementing the functionality. Our protocols are secure in the Global Random Oracle Model introduced recently by Canetti, Jain and Scafuro in CCS 2014 that provides strong compositional guarantees. More precisely, we obtain an adaptively secure UC-commitment scheme in the global ROM assuming only one-way functions. In comparison, the protocol of Canetti, Jain and Scafuro achieves only static security and relies on the specific assumption of Discrete Diffie-Hellman assumption (DDH).

Composable Adaptive Secure Protocols without Setup under Polytime Assumptions. (TCC 2016-B)
C. Hazay, M. Venkitasubramaniam.

All previous constructions of general multiparty computation protocols that are secure against adaptive corruptions in the concurrent setting either require some form of setup or non-standard assumptions. In this paper we provide the first general construction of secure multi-party computation protocol without any setup that guarantees composable security in the presence of an adaptive adversary based on standard polynomial-time assumptions. We prove security under the notion of "UC with super-polynomial helpers" introduced by Canetti et al. (FOCS 2010), which is closed under universal composition and implies "super-polynomial-time simulation". Moreover, our construction relies on the underlying cryptographic primitives in a black-box manner.

Next, we revisit the zero-one law for two-party secure functions evaluation initiated by the work of Maji, Prabhakaran and Rosulek (CRYPTO 2010). According to this law, every two-party functionality is either trivial (meaning, such functionalities can be reduced to any other functionality) or complete (meaning, any other functionality can be reduced to these functionalities) in the Universal Composability (UC) framework. As our second contribution, assuming the existence of a simulatable public-key encryption scheme, we establish a zero-one law in the adaptive setting. Our result implies that every two-party non-reactive functionality is either trivial or complete in the UC framework in the presence of adaptive, malicious adversaries.

Composable Security in the Tamper Proof Hardware Model under Minimal Complexity. (TCC 2016-B)
C. Hazay, A. Polychroniadou, M. Venkitasubramaniam.

We put forth a new formulation of tamper-proof hardware in the Global Universal Composable (GUC) framework introduced by Canetti et al. in TCC 2007. Almost all of the previous works rely on the formulation by Katz in Eurocrypt 2007 and this formulation does not fully capture tokens in a concurrent setting. We address these shortcomings by relying on the GUC framework where we make the following contributions:
  • We construct secure Two-Party Computation (2PC) protocols for general functionalities with optimal round complexity and computational assumptions using stateless tokens. More precisely, we show how to realize arbitrary functionalities with GUC security in two rounds under the minimal assumption of One-Way Functions (OWFs). Moreover, our construction relies on the underlying function in a black-box way. As a corollary, we obtain feasibility of Multi-Party Computation (MPC) with GUC-security under the minimal assumption of OWFs. As an independent contribution, we identify an issue with a claim in a previous work by Goyal, Ishai, Sahai, Venkatesan and Wadia in TCC 2010 regarding the feasibility of UC-secure computation with stateless tokens assuming collision-resistant hash-functions (and the extension based only on one-way functions).
  • We then construct a 3-round MPC protocol to securely realize arbitrary functionalities with GUC-security starting from any semi-honest secure MPC protocol. For this construction, we require the so-called one-many commit-and-prove primitive introduced in the original work of Canetti, Lindell, Ostrovsky and Sahai in STOC 2002 that is round-efficient and black-box in the underlying commitment. Using specially designed ``input-delayed'' protocols we realize this primitive (with a 3-round protocol in our framework) using stateless tokens and one-way functions (where the underlying one-way function is used in a black-box way).

On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography (INDOCRYPT 2016)
D. Miller, A. Scrivener, J. Stern, M. Venkitasubramaniam.

Goldreich and Izsak (Theory of Computing, 2012) initiated the research on understanding the role of negations in circuits implementing cryptographic primitives, notably, considering one-way functions and pseudo-random generators. More recently, Guo, Malkin, Oliveira and Rosen (TCC, 2015) determined tight bounds on the minimum number of negations gates (i.e., negation complexity) of a wide variety of cryptographic primitives including pseudo-random functions, error-correcting codes, hardcore-predicates and randomness extractors.

We continue this line of work to establish the following results:
  • First, we determine tight lower bounds on the negation complexity of collision-resistant and target collision-resistant hash-function families.
  • Next, we examine the role of injectivity and surjectivity on the negation complexity of one-way functions. Here we show that,
    • Assuming the existence of one-way injections, there exists a monotone one-way injection. Furthermore, we complement our result by showing that, even in the worst-case, there cannot exist a monotone one-way injection with constant stretch.
    • Assuming the existence of one-way permutations, there exists a monotone one-way surjection.
  • Finally, we show that there exists list-decodable codes with monotone decoders.
In addition, we observe some interesting corollaries to our results.


On the Power of Two-Party Computation. (CRYPTO 2016)
C. Hazay, M. Venkitasubramaniam.

Ishai, Kushilevitz, Ostrovsky and Sahai (STOC 2007, SIAM JoC 2009) introduced the powerful "MPC-in-the-head" technique that provided a general transformation of information-theoretic MPC protocols secure against passive adversaries to a ZK proof in a "black-box" way. In this work, we extend this technique and provide a generic transformation of any semi-honest secure two-party computation (2PC) protocol (with mild adaptive security guarantees) in the so called oblivious-transfer hybrid model to an adaptive ZK proof for any $\mathsf{NP}$-language, in a ``black-box'' way assuming only one-way functions. Our basic construction based on Goldreich-Micali-Wigderson's 2PC protocol yields an adaptive ZK proof with communication complexity proportional to quadratic in the size of the circuit implementing the $\mathsf{NP}$ relation. Previously such proofs relied on an expensive Karp reduction of the $\mathsf{NP}$ language to Graph Hamiltonicity (Lindell and Zarosim (TCC 2009, Journal of Cryptology 2011)). We also improve our basic construction to obtain the first linear-rate adaptive ZK proofs by relying on efficient maliciously secure 2PC protocols. Core to this construction is a new way of transforming 2PC protocols to efficient (adaptively secure) instance-dependent commitment schemes.

As our second contribution, we provide a general transformation to construct a randomized encoding of a function $f$ from any 2PC protocol that securely computes a related functionality (in a black-box way). We show that if the 2PC protocol has mild adaptive security guarantees then the resulting randomized encoding (RE) can be decomposed to an offline/online encoding.

As an application of our techniques, we show how to obtain a ZK proof for any $\mathsf{NP}$ language that is black-box in the underlying one-way function with an "input-delayed" property and without relying on expensive Karp reductions. Namely, the honest prover's algorithm does not require the actual statement to be proved until the last round. We further generalize this to obtain a "commit and prove" protocol with the same property where the prover commits to a witness $w$ in the second message and proves a statement $x$ regarding the witness $w$ in zero-knowledge where the statement is determined only in the last round. This improves previous constructions of Lapidot and Shamir (Crypto 1990) was designed specifically for the Graph Hamiltonicity problem and relied on the underlying primitives in a non-black-box way.


Privacy Enhancement for Interconnected Vehicles via Secure Multiparty Computation. (ITS World Congress 2016)
S. Markandeya, M. Venkitasubramaniam.

Vehicle-to-vehicle communication is wireless transmission of data between vehicles where the goal is to prevent accidents by sharing speed and position data. As has been well established, V2V has the potential to dramatically improve highway safety, however, the same technology raises serious concerns regarding security and privacy of the data being created, collected and shared. In this work, we identify a particular privacy vulnerability of the proposed Security Credential Management System (SCMS) and suggest an alternative mechanism to provide stronger privacy guarantees by using a powerful tool from modern cryptography known as secure multiparty computation.

What Security Can We Achieve in 4-rounds. (SCN 2016)
C. Hazay, M. Venkitasubramaniam.

Katz and Ostrovsky (Crypto 2004) proved that five rounds are necessary for stand-alone general black-box constructions of secure two-party protocols and at least four rounds are necessary if only one party needs to receive the output. Recently, Ostrovsky, Richelson and Scafuro (Crypto 2015) proved optimality of this result by showing how to realize arbitrary functionalities in four rounds where only one party receives the output via a black-box construction (and an extension to five rounds where both parties receive the output). In this paper we study the question of what security is achievable for stand-alone two-party protocols within four rounds.

We first provide a four-round two-party protocol for coin-tossing that achieves $1/p$-simulation security (i.e. simulation fails with probability at most $1/p+\ngl$), in the presence of malicious corruptions. Next, we provide a four-round two-party protocol for general functionalities, where both parties receive the output, that achieves $1/p$-security in the presence of malicious adversaries corrupting one of the parties, and full security in the presence of non-aborting malicious adversaries corrupting the other party.

Next, we provide a three-round oblivious-transfer protocol, that achieves $1/p$--simulation security against arbitrary malicious senders, while simultaneously guaranteeing a meaningful notion of privacy against malicious corruptions of either party.

Finally, we show that the simulation-based security guarantees for our three-round protocols are optimal by proving that 1/p-simulation security is impossible to achieve against both parties in three rounds or less when requiring some minimal guarantees on the privacy of their inputs.

Secure Computation from Millionaires. (ASIACRYPT 2015)
a. shelat, M. Venkitasubramaniam

The standard method for designing a secure computation protocol for function f first transforms f into either a circuit or a RAM program and then applies a generic secure computation protocol that either handles boolean gates or translates the RAM program into oblivious RAM instructions.

In this paper, we show a large class of functions for which a different iterative approach to secure computation results in more efficient protocols. The first such examples of this technique was presented by Aggrawal, Mishra, and Pinkas (J. of Cryptology, 2010) for computing the median; later, Brickell and Shmatikov (Asiacrypt 2005) showed a similar technique for shortest path problems.

We generalize the technique in both of those works and show that it applies to a large class of problems including certain matroid optimizations, sub-modular optimization, convex hulls, and other scheduling problems. The crux of our technique is to securely reduce these problems to secure comparison operations and to employ the idea of gradually releasing part of the output. We then identify conditions under which both of these techniques for protocol design are compatible with achieving simulation-based security in the honest-but-curious and covert adversary models. In special cases such as median, we also show how to achieve malicious security.

On the Black-Box Complexity of UC-Commitments. (ASIACRYPT 2015)
C. Hazay, M. Venkitasubramaniam.

In this work, we study the intrinsic complexity of black-box Universally Composable (UC) secure computation based on general assumptions. We present a thorough study in various corruption modelings while focusing on achieving security in the common reference string (CRS) model. Our results involve the following:
  • Static UC secure computation. Designing the first static UC secure oblivious transfer protocol based on public-key encryption and stand-alone semi-honest oblivious transfer. As a corollary we obtain the first black-box constructions of UC secure computation assuming only two-round semi-honest oblivious transfer.
  • One-sided UC secure computation. Designing adaptive UC secure two-party computation with single corruptions assuming public-key encryption with oblivious ciphertext generation.
  • Adaptive UC secure computation. Designing adaptively secure UC commitment scheme assuming only public-key encryption with oblivious ciphertext generation. As a corollary we obtain the first black-box constructions of adaptive UC secure computation assuming only (trapdoor) simulatable public-key encryption (as well as a variety of concrete assumptions).
We remark that such a result was not known even under non-black-box constructions.

Resettably Sound Zero-Knoweldge Arguments from OWFs - the (semi) Black-Box way. (TCC 2015)
R. Ostrovsy, A. Scafuro, M. Venkitasubramaniam.

We construct a constant-round resettably-sound zero-knowledge argument of knowledge based on black-box use of any one-way function. Resettable-soundness was introduced by Barak, Goldreich, Goldwasser and Lindell (FOCS 01) and is a strengthening of the soundness requirement in interactive proofs demanding that soundness should hold even if the malicious prover is allowed to “reset” and “restart” the verifier. In their work they show that resettably-sound ZK arguments require non-black-box simulation techniques, and also provide the first construction based on the breakthrough simulation technique of Barak (FOCS 01). All known implementations of Barak’s non-black-box technique required non-black-box use of a collision-resistance hash-function (CRHF). Very recently, Goyal, Ostrovsky, Scafuro and Visconti (STOC 14) showed an implementation of Barak’s technique that needs only black-box access to a collision-resistant hash-function while still having a non-black-box simulator. (Such a construction is referred to as semi black-box.) Plugging this implementation in the BGGL’s construction yields the first resettably-sound ZK arguments based on black-box use of CRHFs. However, from the work of Chung, Pass and Seth (STOC 13) and Bitansky and Paneth (STOC13), we know that resettably-sound ZK arguments can be constructed from non-black-box use of any one-way function (OWF), which is the minimal assumption for ZK arguments. Hence, a natural question is whether it is possible to construct resettably-sound zero-knowledge arguments from black-box use of any OWF only. In this work we provide a positive answer to this question thus closing the gap between black-box and non-black-box constructions for resettably-sound ZK arguments.

Concurrent Zero Knowledge, Revisited (Journal of Cryptology, 2014)
R. Pass, W. Tseng, M. Venkitasubramaniam.

We show a parallel-repetition theorem for constant-round Arthur-Merlin Proofs, using an efficient reduction. As a consequence, we show that parallel repetition reduces the soundness-error at an optimal rate (up to a negligible factor) in constant-round public-coin argument systems, and constant-round public-coin proofs of knowledge. The former of these results resolves an open question posed by Bellare, Impagliazzo and Naor (FOCS '97).

Cloud-based Secure Health Monitoring: Optimizing Fully-Homomorphic Encryption for Streaming Algorithms (CCSNA 2014)
A. Page, O. Kocabas, S. Ames, M. Venkitasubramaniam, T. Soyata.

There are many incentives for healthcare providers to shift their datacenters to the cloud. However, privacy of patient health information is a major concern when processing medical data off-site. One possible solution is the use of Fully Homomorphic Encryption (FHE), but this solution is too slow for most applications. We present a technique that increases efficiency and parallelism for certain algorithms under FHE. Through experiments and simulations, we demonstrate that our method yields about 20x speedup in a sample application. This is a significant step towards practical FHE-based medical remote monitoring

4-Round Resettably- Sound Zero Knowledge (TCC 2014)
K. Chung, R. Ostrovsky, R. Pass, M. Venkitasubramaniam, I. Visconti.

While 4-round constructions of zero-knowledge arguments are known based on the existence of one-way functions, constuctions of resettably-sound zero-knowledge arguments require either stronger assumptions (the existence of a fully-homomorphic encryption scheme), or more communication rounds. We close this gap by demonstrating a 4- round resettably-sound zero-knowledge argument for $\mathsf{NP}$ based on the existence of one-way functions.

On Adaptively Secure Protocols (SCN 2014)
M. Venkitasubramaniam

Adaptive security captures the capability of an adversary to adaptively affect a system during the course of its computation based on partial information gathered. In this work, we explore the theoretical complexity of achieving adaptive security in two settings:
  • Adaptive UC-Secure Computation: We provide a round-efficient compiler that transforms any stand-alone semi-honest adaptively secure multiparty computation to adaptive UC-security. Recently, Dana et. al (Asiacrypt 2013) showed how to acheive adaptive UCsecurity in any trusted setup under minimal assumptions. They achieve this by constructing an O(n)-round adaptively secure concurrent non-malleable commitment scheme. The main contribution of our work shows how to achieve the same in O(1)-rounds.
  • Zero-Knowledge with Adaptive Inputs: Lin and Pass in (TCC 2011) gave first constructions of concurrent non-malleable zero-knowledge proofs secure w.r.t. adaptively chosen inputs in the plain model in a restricted setting, namely, where the adversary can only ask for proofs of true (adaptively-chosen) statements. We extend their definition to the fully-adaptive setting and show how to construct a protocol that satisfies this definition. As an independent contribution we provide a simple and direct compilation of any semi-honest secure protocol to a fully concurrently secure protocol under polynomialtime assumptions in the Angel-Based UC-Security.

Adaptive and Concurrent Secure Computation from New Adaptive, Non-Malleable Commitments (Asiacrypt 2013)
D. Dachman-Soled, T. Malkin, M. Raykova, M. Venkitasubramaniam.

We present a unified approach for obtaining general secure computation that achieves adaptive-Universally Composable (UC)-security. Using our approach we essentially obtain all previous results on adaptive concurrent secure computation, both in relaxed models (e.g., quasi-polynomial time simulation), as well as trusted setup models (e.g., the CRS model, the imperfect CRS model). This provides conceptual simplicity and insight into what is required for adaptive and concurrent security, as well as yielding improvements to set-up assumptions and/or computational assumptions in known models. Additionally, we provide the first constructions of concurrent secure computation protocols that are adaptively secure in the timing model, and the non-uniform simulation model. As a corollary we also obtain the first adaptively secure multiparty computation protocol in the plain model that is secure under bounded-concurrency.
Conceptually, our approach can be viewed as an adaptive analogue to the recent work of Lin, Pass and Venkitasubramaniam [STOC '09], who considered only non-adaptive adversaries. Their main insight was that the non-malleability requirement could be decoupled from the simulation requirement to achieve UCsecurity. A main conceptual contribution of this work is, quite surprisingly, that it is still the case even when considering adaptive security.
A key element in our construction is a commitment scheme that satisfies a strong definition of non-malleability. Our new primitive of concurrent equivocal nonmalleable commitments, intuitively, guarantees that even when a man-in-the-middle adversary observes concurrent equivocal commitments and decommitments, the binding property of the commitments continues to hold for commitments made by the adversary. This definition is stronger than previous ones, and may be of independent interest. Previous constructions that satisfy our definition have been constructed in setup models, but either require existence of stronger encryption schemes such as CCA-secure encryption or require independent “trapdoors” provided by the setup for every pair of parties to ensure non-malleability. A main technical contribution of this work is to provide a construction that eliminates these requirements and requires only a single trapdoor.

The Generalized Randomized Iterate and Its Application to New Efficient Constructions of UOWHFs from Regular One-Way Functions (Asiacrypt 2012)
S. Ames, R. Gennaro, M. Venkitasubramaniam.

This paper presents the Generalized Randomized Iterate of a (regular) one-way function f and showthat it can be used to build Universal One-Way Hash Function (UOWHF) families with O(n2) key length. We then show that Shoup's technique for UOWHF domain extension can be used to improve the efficiency of the previous construction. We present the Reusable Generalized Randomized Iterate which consists of k ≥ n + 1 iterations of a regular one-way function composed at each iteration with a pairwise independent hash function, where we only use log k such hash functions, and we "schedule" them according to the same scheduling of Shoup's domain extension technique. The end result is a UOWHF construction from regular one-way functions with an O(n log n) key. These are the first such efficient constructions of UOWHF from regular one-way functions of unknown regularity. Finally we show that the Shoup's domain extension technique can also be used in lieu of derandomization techniques to improve the efficiency of PRGs and of hardness amplification constructions for regular one-way functions.

A Unified Framework for UC from Only OT (Asiacrypt 2012)
H. Lin, R. Pass, M. Venkitasubramaniam.

In [LPV09], the authors presented a unified framework for constructing Universally Composable (UC) secure computation protocols, assuming only enhanced trapdoor permutations. In this work, we weaken the hardness assumption underlying the unified framework to only the existence of a stand-alone secure semi-honest Oblivious Transfer (OT) protocol. The new framwork directly implies new and improved UC feasibility results from only the existence of a semi-honest OT protocol in various models. Since in many models, the existence of UC-OT implies the existence of a semi-honest OT protocol. Furthermore, we show that by relying on a more fine-grained analysis of the unified framework, we obtain concurrently secure computation protocols with super-polynomial-time simulation (SPS), based on the necessary assumption of the existence of a semi-honest OT protocol that can be simulated in super-polynomial times. When the underlying OT protocol has constant rounds, the SPS secure protocols constructed also have constant rounds. This yields the first construction of constant-round secure computation protocols that satisfy a meaningful notions of concurrent security (i.e., SPS security) based on tight assumptions. A notable corollary following from our new unifed framwork is that stand-alone (or bounded-concurrent) password authenticated key-exchange protocols (PAKE) can be constructed from only semi-honest OT protocols; combined with the result of [Nguyen05] that the existence of PAKE protocols implies that of OT, we derive a tight characterization of PAKE protocols.

Towards Non-Black-Box Lower Bounds in Cryptography (TCC 2011)
R. Pass, Wei-Lung D. Tseng, M. Venkitasubramaniam.

We consider average-case strengthenings of the traditional assumption that coNP is not contained in AM. Under these assumptions, we rule out generic and potentially non-black-box constructions of various cryptographic primitives (e.g., one-way permutations, collision-resistant hash-functions, constant-round statistically hiding commitments, and constant-round black-box zero-knowledge proofs for NP) from one-way functions, assuming the security reductions are black-box.

Concurrent Non-Malleable Zero Knowledge Proofs (CRYPTO 2010)
H. Lin, R. Pass, Wei-Lung D. Tseng, M. Venkitasubramaniam.

Concurrent non-malleable zero-knowledge (NMZK) considers the concurrent execution of zero-knowledge protocols in a setting where the attacker can simultaneously corrupt multiple provers and verifiers. Barak, Prabhakaran and Sahai (FOCS’06) recently provided the first construction of a concurrent NMZK protocol without any set-up assumptions. Their protocol, however, is only computationally sound (a.k.a., a concurrent NMZK argument). In this work we present the first construction of a concurrent NMZK proof without any set-up assumptions. Our protocol requires poly(n) rounds assuming one-way functions, or Õ(log n) rounds assuming collision-resistant hash functions. As an additional contribution, we improve the round complexity of concurrent NMZK arguments based on one-way functions (from poly(n) to Õ(log n)), and achieve a near linear (instead of cubic) security reductions. Taken together, our results close the gap between concurrent ZK protocols and concurrent NMZK protocols (in terms of feasibility, round complexity, hardness assumptions, and tightness of the security reduction).

Eye for an Eye: On Concurrent Zero-Knowledge in the Timing Model. (TCC 2010)
R. Pass, Wei-Lung D. Tseng, M. Venkitasubramaniam.

We present new and efficient concurrent zero-knowledge protocols in the timing model. In contrast to earlier work-which through artificially-imposed delays require every protocol execution to run at the speed of the slowest link in the network-our protocols essentially only delay messages based on the actual response time of each verifier (which can be significantly smaller).

Private Coins versus Public Coins in Zero-Knowledge Proof Systems. (TCC 2010)
R. Pass, M. Venkitasubramaniam.

Goldreich-Krawczyk (Siam J of Comp'96) showed that only languages in BPP have constant-round public-coin black-box zero-knowledge protocols. We extend their lower bound to fully black-box" private- coin protocols based on one-way functions. More precisely, we show that only languages in BPPSam-where Sam is a "collision-finding" oracle in analogy with Simon (Eurocrypt'98) and Haitner et. al (FOCS'07)-can have constant-round fully black-box zero-knowledge proofs; the same holds for constant-round fully black-box zero-knowledge arguments with sublinear verifier communication complexity. We also establish nearlinear lower bounds on the round complexity of fully black-box concurrent zero-knowledge proofs (or arguments with sublinear verifier communication) for languages outside BPPSam. The technique used to establish these results is a transformation from private-coin protocols into Sam-relativized public-coin protocols; for the case of fully black-box protocols based on one-way functions, this transformation preserves zero knowledge, round complexity and communication complexity.

A Unified Framework for Concurrent Security: Universal Composability from Stand-alone Non-malleability. (STOC 2009)
H. Lin, R. Pass and M. Venkitasubramaniam.

We present a unified framework for obtaining Universally Composable (UC) protocols by relying on stand-alone secure non-malleable commitments Essentially all results on concurrent secure computation-both in relaxed models (e.g., quasi-polynomial time simulation), or with trusted set-up assumptions (e.g., the CRS model, the imperfect CRS model, or the timing model)-are obtained as special cases of our framework. This not only leads to conceptually simpler solutions, but also to improved set-up assumptions, round-complexity, and computational assumptions. Additionally, this framework allows us to consider new relaxed models of security: we show that UC security where the adversary is a uniform PPT but the simulator is allowed to be a non-uniform PPT (i.e., essentially, traditional UC security, but with a non-uniform reduction) is possible without any trusted set-up. This gives the first results on concurrent secure computation without set-up, which can be used for securely computing ``computationally-sensitive'' functionalities (e.g., data-base queries, ``proof of work''-protocols, or playing bridge on the Internet).

Precise Concurrent Zero Knowledge. (EUROCRYPT 2008)
O. Pandey, R. Pass, A. Sahai, W. Tseng and M. Venkitasubramaniam.

Precise zero knowledge introduced by Micali and Pass (STOC 06) guarantees that the view of any verifier V can be simulated in time closely related to the actual (as opposed to worst-case) time spent by V in the generated view. We provide the first constructions of precise concurrent zero-knowledge protocols. Our constructions have essentially optimal precision; consequently this improves also upon the previously tightest non-precise concurrent zero-knowledge protocols by Kilian and Petrank (STOC 01) and Prabhakaran, Rosen and Sahai (FOCS 02) whose simulators have a quadratic worst-case overhead. Additionally, we achieve a statistically-precise concurrent zero-knowledge property—which requires simulation of unbounded verifiers participating in an unbounded number of concurrent executions; as such we obtain the first (even non-precise) concurrent zero-knowledge protocols which handle verifiers participating in a super-polynomial number of concurrent executions.

On Constant-Round Concurrent Zero-Knowledge. (TCC 2008)
R. Pass, M. Venkitasubramaniam.

Loosely speaking, an interactive proof is said to be zero- knowledge if the view of every "efficient" verifier can be "efficiently" simulated. An outstanding open question regarding zero-knowledge is whether constant-round concurrent zero-knowledge proofs exists for non- trivial languages. We answer this question to the affirmative when mod- eling "efficient adversaries" as probabilistic quasi-polynomial time ma- chines (instead of the traditional notion of probabilistic polynomial-time machines).

Concurrent Non-Malleable Commitments from One-way Functions (TCC 2008)
H. Lin, R. Pass, M. Venkitasubramaniam.

We show the existence of concurrent non-malleable commitments based on the existence of one-way functions. Our proof of security only requires the use of black-box techniques, and additionally provides an arguably simplified proof of the existence of even stand-alone secure non-malleable commitments.

An Efficient Parallel Repetition Theorem for Arthur-Merlin Games. (STOC 2007)
R. Pass, A. M. Venkitasubramaniam.

We show a parallel-repetition theorem for constant-round Arthur-Merlin Games, using an efficient reduction. As a consequence, we show that parallel repetition reduces the soundness-error at an optimal rate (up to a negligible factor) in constant-round public-coin argument systems, and constant-round public-coin proofs of knowledge. The former of these results resolves an open question posed by Bellare, Impagliazzo and Naor (FOCS '97).

l-Diversity: Privacy Beyond k-Anonymity. (TKDD 2007)
A. Machanavajjhala, D. Kifer, J.Gehrke and M. Venkitasubramaniam.

Publishing data about individuals without revealing sensitive information about them is an important problem. In recent years, a new definition of privacy called k-anonymity has gained popularity. In a k-anonymized dataset, each record is indistinguishable from at least k-1 other records with respect to certain "identifying" attributes. In this paper we show using two simple attacks that a k-anonymized dataset has some subtle, but severe privacy problems. First, an attacker can discover the values of sensitive attributes when there is little diversity in those sensitive attributes. This is a known problem. Second, attackers often have background knowledge, and we show that k-anonymity does not guarantee privacy against attackers using background knowledge. We give a detailed analysis of these two attacks and we propose a novel and powerful privacy criterion called l-diversity that can defend against such attacks. In addition to building a formal foundation for l-diversity, we show in an experimental evaluation that l-diversity is practical and can be implemented efficiently.

l-Diversity: Privacy Beyond k-Anonymity. (ICDE 2006)
A. Machanavajjhala, J.Gehrke, D. Kifer and M. Venkitasubramaniam.

Publishing data about individuals without revealing sensitive information about them is an important problem. In recent years, a new definition of privacy called k-anonymity has gained popularity. In a k-anonymized dataset, each record is indistinguishable from at least k-1 other records with respect to certain "identifying" attributes. In this paper we show with two simple attacks that a k-anonymized dataset has some subtle, but severe privacy problems. First, we show that an attacker can discover the values of sensitive attributes when there is little diversity in those sensitive attributes. Second, attackers often have background knowledge, and we show that k-anonymity does not guarantee privacy against attackers using background knowledge. We give a detailed analysis of these two attacks and we propose a novel and powerful privacy definition called l-diversity. In addition to building a formal foundation for l-diversity, we show in an experimental evaluation that l-diversity is practical and can be implemented efficiently.

Trusted CVS. (STD3S - ICDE Workshops)
M. Venkitasubramaniam, A. Machanavajjhala, D. Martin and J. Gehrke.

The CVS (Concurrent Versions System) software is a popular method for recording modifications to data objects, in addition to concurrent access to data in a multi-user environment. In current implementations, all users have to trust that the CVS server performs all user operations as instructed. In this paper, we develop protocols that allow users to verify that the server has been compromised, and that it has performed exactly the users’ operations on the data. We first show that communication between users is necessary to guarantee that users can detect that the server has been compromised. We then propose efficient protocols that fast enable detection of server integrity under CVS workloads. Our techniques also have applications in the outsourcing model where multiple users own a common database maintained by an untrusted third-party vendor.

On Byzantine Agreement over (2, 3)-Uniform Hypergraphs. (DISC 2004)
D. V. S. Ravikant, M. Venkitasubramaniam, V. Srikanth, K. Srinathan and C. P. Rangan.

Byzantine Agreement is possible on a network consists of only unicast channels (i.e. a 2-uniform hypergraph) if and only if n > 3t (Pease et. al. [PSL80]). However, Fitzi and Maurer ([FM00]) show that if, in addition to all unicast channels, there exists local broadcast among every three processes in the network (i.e. a complete (2,3)-uniform hypergraph), n>2t is necessary and sufficient for Byzantine agreement. In this paper, we show that optimum tolerance of n>2t can be achieved even if a substantial fraction of the local broadcast channels are not available. Specifically, we model the network as a (2,3)-uniform hypergraph H = (P,E), where P denotes the set of n processes and E is a set of 2-tuples and/or 3-tuples of processes (edges or 3-hyperedges), wherein each 3-hyperedge represents a local broadcast among the three processes; we obtain a characterization of the hypergraphs on which Byzantine agreement is possible. Using this characterization, we show that for n=2t+1, (2/3t3 + Theta(t2)) 3-hyperedges are necessary and sufficient to enable Byzantine agreement. This settles an open problem raised by Fitzi and Maurer in [FM00]. An efficient protocol is also given whenever Byzantine agreement is possible.

Brief announcement: On the round complexity of distributed consensus over synchronous networks. (PODC 2004)
D. V. S. Ravikant, M. Venkitasubramaniam, V. Srikanth, K. Srinathan and C. P. Rangan.

In a synchronous network, it is well-known that t + 1 rounds are necessary and sufficient to achieve distributed consensus tolerating t stopping faults[2]. In this work, we show that in a network consisting of all k-cast channels, the corresponding number of rounds is floor[(t - 1)/k] + 2.

This material is based upon work supported by the National Science Foundation and Google. Any opinions, findings, and conclusions or recommendations expressed in this publications are those of the author(s) and do not necessarily reflect the views of the National Science Foundation and Google.