Muthuramakrishnan Venkitasubramaniam Contact 621 Computer Sciences Building University of Rochester, Rochester, NY 146270226 Mail: muthuv@cs.rochester.edu 
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.
Teaching
PhD Students
Program Committees
Recent Talks
Visitors
Publications: (click title for abstract)
Equivocating Yao: ConstantRounds Adaptively Secure
Multiparty Computation in the Plain Model. (STOC 2017) Yao's garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable twomessage, twoparty 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 noncommitting encryption, we obtain the first twomessage, twoparty computation protocol, and the first constantround multiparty computation protocol, in the plain model, that are secure against semihonest adversaries who can adaptively corrupt all parties. A number of extensions and applications are described within. 

Better TwoRound Adaptive MultiParty Computation.
(PKC 2017)
The only known tworound multiparty 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 semihonest case and taking a different approach than GP, we show a tworound, adaptively secure protocol where:


Scalable MultiParty Private SetIntersection (PKC 2017)
In this work we study the problem of private setintersection in the multiparty 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 semihonest 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 semihonest 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. 

ConstantRound Adaptively Secure Protocols in the TamperProof Hardware Model (PKC 2017)
Achieving constantround 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 (DachmanSoled et al., Garg and Polychroniadou, Canetti et al.), solved the problem in the Common Reference String (CRS) model. In this work, we present a constantround adaptive UCsecure computation protocol for all wellformed functionalities in the tamperproof hardware model using stateless tokens from only oneway 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 UCcommitment scheme in the global ROM assuming only oneway functions. In comparison, the protocol of Canetti, Jain and Scafuro achieves only static security and relies on the specific assumption of Discrete DiffieHellman assumption (DDH).


Composable Adaptive Secure Protocols without Setup
under Polytime Assumptions. (TCC 2016B)
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 nonstandard assumptions. In this paper we provide the first general construction of secure multiparty computation protocol without any setup that guarantees composable security in the presence of an adaptive adversary based on standard polynomialtime assumptions. We prove security under the notion of "UC with superpolynomial helpers" introduced by Canetti et al. (FOCS 2010), which is closed under universal composition and implies "superpolynomialtime simulation". Moreover, our construction
relies on the underlying cryptographic primitives in a blackbox manner.
Next, we revisit the zeroone law for twoparty secure functions evaluation initiated by the work of Maji, Prabhakaran and Rosulek (CRYPTO 2010). According to this law, every twoparty 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 publickey encryption scheme, we establish a zeroone law in the adaptive setting. Our result implies that every twoparty nonreactive 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
2016B)
We put forth a new formulation of tamperproof 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:


On Negation Complexity of Injections, Surjections and CollisionResistance in Cryptography (INDOCRYPT 2016)
Goldreich and Izsak (Theory of Computing, 2012) initiated the research on understanding the role of negations in circuits implementing cryptographic primitives, notably, considering oneway functions and pseudorandom 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 pseudorandom functions, errorcorrecting codes, hardcorepredicates and randomness extractors.
We continue this line of work to establish the following results:

PDF


On the Power of TwoParty Computation. (CRYPTO
2016)
Ishai, Kushilevitz, Ostrovsky and Sahai (STOC 2007, SIAM JoC 2009) introduced the powerful "MPCinthehead" technique that provided a general transformation of informationtheoretic MPC protocols secure against passive adversaries to a ZK proof in a "blackbox" way. In this work, we extend this technique and provide a generic transformation of any semihonest secure twoparty computation (2PC) protocol (with mild adaptive security guarantees) in the so called oblivioustransfer hybrid model to an adaptive ZK proof for any $\mathsf{NP}$language, in a ``blackbox'' way assuming only oneway functions. Our basic construction based on GoldreichMicaliWigderson'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 linearrate 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) instancedependent 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 blackbox 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 blackbox in the underlying oneway function with an "inputdelayed" 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 zeroknowledge 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 nonblackbox way. 
PDF


Privacy Enhancement for Interconnected Vehicles via Secure Multiparty Computation. (ITS World Congress 2016)
Vehicletovehicle 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 4rounds. (SCN
2016)
Katz and Ostrovsky (Crypto 2004) proved that five rounds are necessary for standalone general blackbox constructions of secure twoparty 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 blackbox 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 standalone twoparty protocols within four rounds.
We first provide a fourround twoparty protocol for cointossing 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 fourround twoparty 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 nonaborting malicious adversaries corrupting the other party. Next, we provide a threeround oblivioustransfer 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 simulationbased security guarantees for our threeround protocols are optimal by proving that 1/psimulation 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)
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, submodular 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 simulationbased security in the honestbutcurious and covert adversary models. In special cases such as median, we also show how to achieve malicious security. 

On the BlackBox Complexity of UCCommitments.
(ASIACRYPT 2015)
In this work, we study the intrinsic complexity of blackbox 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:


Resettably Sound ZeroKnoweldge Arguments from OWFs
 the (semi) BlackBox way. (TCC 2015)
We construct a constantround resettablysound zeroknowledge argument of knowledge based on blackbox use of any oneway function. Resettablesoundness 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 resettablysound ZK arguments require nonblackbox simulation techniques, and also provide the first construction based on the breakthrough simulation technique of Barak (FOCS 01). All known implementations of Barak’s nonblackbox technique required nonblackbox use of a collisionresistance hashfunction (CRHF).
Very recently, Goyal, Ostrovsky, Scafuro and Visconti (STOC 14) showed an implementation of Barak’s technique that needs only blackbox access to a collisionresistant hashfunction while still having a nonblackbox simulator. (Such a construction is referred to as semi blackbox.) Plugging this implementation in the BGGL’s construction yields the first resettablysound ZK arguments based on blackbox use of CRHFs.
However, from the work of Chung, Pass and Seth (STOC 13) and Bitansky and Paneth (STOC13), we know that resettablysound ZK arguments can be constructed from nonblackbox use of any oneway function (OWF), which is the minimal assumption for ZK arguments. Hence, a natural question is whether it is possible to construct resettablysound zeroknowledge arguments from blackbox use of any OWF only. In this work we provide a positive answer to this question thus closing the gap between blackbox and nonblackbox constructions for resettablysound ZK arguments.


Concurrent Zero Knowledge, Revisited (Journal
of Cryptology, 2014)
We show a parallelrepetition theorem for constantround ArthurMerlin Proofs, 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).


Cloudbased Secure Health Monitoring: Optimizing FullyHomomorphic Encryption for Streaming Algorithms (CCSNA 2014)
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 offsite. 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 FHEbased medical remote
monitoring


4Round Resettably
Sound Zero Knowledge (TCC 2014)
While 4round constructions of zeroknowledge arguments
are known based on the existence of oneway functions, constuctions of
resettablysound zeroknowledge arguments require either stronger assumptions
(the existence of a fullyhomomorphic encryption scheme), or
more communication rounds. We close this gap by demonstrating a 4
round resettablysound zeroknowledge argument for $\mathsf{NP}$ based on the
existence of oneway functions.


On Adaptively Secure Protocols (SCN 2014)
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 and Concurrent Secure Computation from
New Adaptive, NonMalleable Commitments (Asiacrypt 2013)
We present a unified approach for obtaining general secure computation that achieves adaptiveUniversally Composable (UC)security. Using our
approach we essentially obtain all previous results on adaptive concurrent secure computation, both in relaxed models (e.g., quasipolynomial 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 setup 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 nonuniform simulation model. As a corollary we also obtain the first adaptively secure multiparty computation protocol in the plain model that is secure under boundedconcurrency.
Conceptually, our approach can be viewed as an adaptive analogue to the recent work of Lin, Pass and Venkitasubramaniam [STOC '09], who considered only nonadaptive adversaries. Their main insight was that the nonmalleability 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 nonmalleability. Our new primitive of concurrent equivocal nonmalleable commitments, intuitively, guarantees that even when a maninthemiddle 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 CCAsecure encryption or require independent “trapdoors” provided by the setup for every pair of parties to ensure nonmalleability. A main technical contribution of this work is to provide a construction that eliminates these requirements and requires only a single trapdoor. 

This paper presents the Generalized Randomized Iterate of a (regular) oneway function f and showthat it can be used to build Universal OneWay Hash Function (UOWHF) families with O(n^{2}) 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 oneway 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 oneway functions with an O(n log n) key. These are the first such efficient constructions of UOWHF from regular oneway 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 oneway functions.


A Unified Framework for UC from Only OT (Asiacrypt 2012)
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 standalone secure semihonest Oblivious Transfer (OT) protocol. The new framwork directly implies new and improved UC feasibility results from only the existence of a semihonest OT protocol in various models. Since in many models, the existence of UCOT implies the existence of a semihonest OT protocol.
Furthermore, we show that by relying on a more finegrained analysis of the unified framework, we obtain concurrently secure computation protocols with superpolynomialtime simulation (SPS), based on the necessary assumption of the existence of a semihonest OT protocol that can be simulated in superpolynomial times. When the underlying OT protocol has constant rounds, the SPS secure protocols constructed also have constant rounds. This yields the first construction of constantround 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 standalone (or boundedconcurrent) password authenticated keyexchange protocols (PAKE) can be constructed from only semihonest 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 NonBlackBox Lower Bounds in Cryptography (TCC 2011)
We consider averagecase strengthenings of the traditional assumption that coNP is not contained in AM. Under these assumptions, we rule out generic and potentially


Concurrent NonMalleable Zero Knowledge Proofs (CRYPTO 2010)
Concurrent nonmalleable zeroknowledge (NMZK) considers the concurrent execution of zeroknowledge protocols in a setting where the attacker can simultaneously corrupt multiple provers and veriﬁers. Barak, Prabhakaran and Sahai (FOCS’06) recently provided the ﬁrst construction of a concurrent NMZK protocol without any setup assumptions. Their protocol, however, is only computationally sound (a.k.a., a concurrent NMZK argument). In this work we present the ﬁrst construction of a concurrent NMZK proof without any setup assumptions. Our protocol requires poly(n) rounds assuming oneway functions, or Õ(log n) rounds assuming collisionresistant hash functions. As an additional contribution, we improve the round complexity of concurrent NMZK arguments based on oneway 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 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.


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).


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.


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.


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.


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.

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.