Muthuramakrishnan Venkitasubramaniam 304 Upson Hall Cornell University, Ithaca, NY 14850

I got my Ph.D in the Dept. of Computer Science at Cornell University under the guidance of Rafael Pass.
My research interests lie in cryptography and complexity theory. I am currently pursuing postdoctoral research fellowship at the Courant Institute of Mathematical Sciences under Yevgeniy Dodis. This fall I will be starting as an assistant professor in the Computer Science Department at University of Rochester.
2010  
Eye for an Eye: On Concurrent ZeroKnowledge in the Timing Model. (TCC 2010)
We present new and efficient concurrent zeroknowledge protocols
in the timing model. In contrast to earlier workwhich through
artificiallyimposed delays require every protocol execution to run at the
speed of the slowest link in the networkour 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 ZeroKnowledge Proof Systems. (TCC 2010)
GoldreichKrawczyk (Siam J of Comp'96) showed that only
languages in BPP have constantround publiccoin blackbox zeroknowledge
protocols. We extend their lower bound to fully blackbox" private
coin protocols based on oneway functions. More precisely, we show that
only languages in BPP^{Sam}where Sam is a "collisionfinding" oracle in
analogy with Simon (Eurocrypt'98) and Haitner et. al (FOCS'07)can
have constantround fully blackbox zeroknowledge proofs; the same
holds for constantround fully blackbox zeroknowledge arguments with
sublinear verifier communication complexity. We also establish nearlinear
lower bounds on the round complexity of fully blackbox concurrent
zeroknowledge proofs (or arguments with sublinear verifier communication)
for languages outside BPP^{Sam}.
The technique used to establish these results is a transformation from
privatecoin protocols into Samrelativized publiccoin protocols; for the
case of fully blackbox protocols based on oneway functions, this transformation
preserves zero knowledge, round complexity and communication
complexity.


2009  
A Unified Framework for Concurrent Security: Universal Composability
from Standalone Nonmalleability. (STOC 2009)
We present a unified framework for obtaining Universally Composable (UC)
protocols by relying on standalone secure nonmalleable commitments
Essentially all results on concurrent secure computationboth in relaxed
models (e.g., quasipolynomial time simulation), or with trusted setup
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 setup assumptions,
roundcomplexity, 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 nonuniform PPT (i.e.,
essentially, traditional UC security, but with a nonuniform reduction) is
possible without any trusted setup. This gives the first results on
concurrent secure computation without setup, which can be used for securely
computing ``computationallysensitive'' functionalities (e.g., database
queries, ``proof of work''protocols, or playing bridge on the Internet).


2008  
Precise Concurrent Zero Knowledge. (EUROCRYPT 2008)
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 worstcase) time spent by V in the generated
view. We provide the first constructions of precise concurrent zeroknowledge
protocols. Our constructions have essentially optimal precision; consequently
this improves also upon the previously tightest nonprecise concurrent
zeroknowledge protocols by Kilian and Petrank (STOC 01) and Prabhakaran,
Rosen and Sahai (FOCS 02) whose simulators have a quadratic worstcase
overhead. Additionally, we achieve a statisticallyprecise concurrent
zeroknowledge propertyâ€”which requires simulation of unbounded verifiers
participating in an unbounded number of concurrent executions; as such we
obtain the first (even nonprecise) concurrent zeroknowledge protocols which
handle verifiers participating in a superpolynomial number of concurrent
executions.


On ConstantRound Concurrent ZeroKnowledge. (TCC 2008)
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 zeroknowledge is
whether constantround concurrent zeroknowledge proofs exists for non
trivial languages. We answer this question to the affirmative when mod
eling "efficient adversaries" as probabilistic quasipolynomial time ma
chines (instead of the traditional notion of probabilistic polynomialtime
machines).


Concurrent NonMalleable Commitments from Oneway Functions (TCC 2008)
We show the existence of concurrent nonmalleable commitments based on the
existence of oneway functions. Our proof of security only requires the use of
blackbox techniques, and additionally provides an arguably simplified proof
of the existence of even standalone secure nonmalleable commitments.


2007  
An Efficient Parallel Repetition Theorem for ArthurMerlin Games. (STOC 2007)
We show a parallelrepetition theorem for constantround ArthurMerlin
Games, using an efficient reduction. As a consequence, we show that
parallel repetition reduces the soundnesserror at an optimal rate (up to a
negligible factor) in constantround publiccoin argument systems,
and constantround publiccoin proofs of knowledge. The former of
these results resolves an open question posed by Bellare, Impagliazzo and Naor
(FOCS '97).


lDiversity: Privacy Beyond kAnonymity. (TKDD 2007)
Publishing data about individuals without revealing sensitive information about them is an
important problem. In recent years, a new definition of privacy called kanonymity has gained
popularity. In a kanonymized dataset, each record is indistinguishable from at least k1 other
records with respect to certain "identifying" attributes.
In this paper we show using two simple attacks that a kanonymized 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 kanonymity 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 ldiversity that can defend
against such attacks. In addition to building a formal foundation for ldiversity, we show in an
experimental evaluation that ldiversity is practical and can be implemented efficiently.


2006  
lDiversity: Privacy Beyond kAnonymity. (ICDE 2006)
Publishing data about individuals without revealing sensitive
information about them is an important problem. In
recent years, a new definition of privacy called kanonymity
has gained popularity. In a kanonymized dataset, each
record is indistinguishable from at least k1 other records
with respect to certain "identifying" attributes.
In this paper we show with two simple attacks that a
kanonymized 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 kanonymity 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 ldiversity. In addition to building a formal
foundation for ldiversity, we show in an experimental evaluation
that ldiversity is practical and can be implemented
efficiently.


Trusted CVS. (STD3S  ICDE Workshops)
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 multiuser 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 thirdparty vendor.


2004  
On Byzantine Agreement over (2, 3)Uniform Hypergraphs. (DISC 2004)
Byzantine Agreement is possible on a network consists of only unicast
channels (i.e. a 2uniform 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 2tuples and/or 3tuples of processes
(edges or 3hyperedges), wherein each 3hyperedge 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/3t^{3} + Theta(t^{2})) 3hyperedges 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)
In a synchronous network, it is wellknown 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 kcast channels, the
corresponding number of rounds is floor[(t  1)/k] + 2.
