| 2010 |
|
Eye for an Eye: On Concurrent Zero-Knowledge in the Timing Model. (TCC 2010)
R. Pass, Wei-Lung D. Tseng, M. Venkitasubramaniam.
(click for abstract)
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).
|
PDF |
|
Private Coins versus Public Coins in Zero-Knowledge Proof Systems. (TCC 2010)
R. Pass, M. Venkitasubramaniam. (click for abstract)
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.
|
PDF |
| 2009 |
|
A Unified Framework for Concurrent Security: Universal Composability
from Stand-alone Non-malleability. (STOC 2009)
H. Lin, R. Pass and M. Venkitasubramaniam. (click for abstract)
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).
|
PDF |
| 2008 |
|
Precise Concurrent Zero Knowledge. (EUROCRYPT 2008)
O. Pandey, R. Pass, A. Sahai, W. Tseng and M. Venkitasubramaniam. (click for abstract)
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.
|
PDF |
|
On Constant-Round Concurrent Zero-Knowledge. (TCC 2008)
R. Pass, M. Venkitasubramaniam. (click for abstract)
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).
|
PDF |
|
Concurrent Non-Malleable Commitments from One-way Functions (TCC 2008)
H. Lin, R. Pass, M. Venkitasubramaniam. (click for abstract)
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.
|
PDF |
| 2007 |
|
An Efficient Parallel Repetition Theorem for Arthur-Merlin Games. (STOC 2007)
R. Pass, A. M. Venkitasubramaniam. (click for abstract)
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).
|
PDF |
|
l-Diversity: Privacy Beyond k-Anonymity. (TKDD 2007)
A. Machanavajjhala, D. Kifer, J.Gehrke and M. Venkitasubramaniam. (click for abstract)
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.
|
PDF |
| 2006 |
|
l-Diversity: Privacy Beyond k-Anonymity. (ICDE 2006)
A. Machanavajjhala, J.Gehrke, D. Kifer and M. Venkitasubramaniam. (click for abstract)
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.
|
PDF |
|
Trusted CVS. (STD3S - ICDE Workshops)
M. Venkitasubramaniam, A. Machanavajjhala, D. Martin and J. Gehrke. (click for abstract)
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.
|
PDF |
| 2004 |
|
On Byzantine Agreement over (2, 3)-Uniform Hypergraphs. (DISC 2004)
D. V. S. Ravikant, M. Venkitasubramaniam, V. Srikanth, K. Srinathan and C. P. Rangan. (click for abstract)
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.
|
PDF |
|
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. (click for abstract)
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.
|
PDF |
