Bio

at Beit Clore, WIS

I am a Ph.D. candidate in the Theory of Computation group at MIT.
Shafi Goldwasser is my advisor.
My research interests lie in cryptography, distributed algorithms and complexity theory.

Curriculum Vitae [pdf] (a bit outdated)

In Submission/Preparation

Weak Verifiable Random Functions
Z. Brakerski, S. Goldwasser, G. Rothblum and V. Vaikuntanathan
How Efficient Can Memory-Checking Be?
C. Dwork, M. Naor, G. Rothblum and V. Vaikuntanathan
One-way Groups and Applications
S. Hohenberger, D. Molnar, R. Rivest and V. Vaikuntanathan
(permanently in preparation)

Refereed Publications

Non-Interactive Statistical Zero-knowledge for Lattice Problems
C. Peikert and V. Vaikuntanathan
CRYPTO 2008
New-Age Cryptography
R. Pass and V. Vaikuntanathan
CRYPTO 2008
A Framework for Efficient and Composable Oblivious Transfer
C. Peikert, V. Vaikuntanathan and B. Waters
CRYPTO 2008 [ps, pdf]
Trapdoors for Hard Lattices, and New Cryptographic Constructions
C. Gentry, C. Peikert and V. Vaikuntanathan
STOC 2008 [ps, pdf]
Bounded CCA2-Secure Encryption
R. Cramer, G. Hanaoka, D. Hofheinz, H. Imai, E. Kiltz, R. Pass, A. Shelat and V. Vaikuntanathan
Asiacrypt 2007 [Proceedings Version ps, pdf]
Relations Among Notions of Non-Malleability for Encryption
R. Pass, A. Shelat and V. Vaikuntanathan

Since its introduction in the early 90's, the notion of nonmalleability for encryption schemes has been formalized using a number of conceptually different definitional approaches -- most notably, the "semantical" simulation-based approach, and the "pragmatic" indistinguishability-based approach. We provide a full characterization of these approaches and consider their robustness under composition.

Asiacrypt 2007 [Proceedings Version ps, pdf]
Secure Computation from Random Error-Correcting Codes
R. Cramer, H. Chen, S. Goldwasser, R. de Haan and V. Vaikuntanathan

Secure computation consists of protocols for secure arithmetic: secret values are added and multiplied securely by networked processors. The striking feature of secure computation is that security is maintained even in the presence of an adversary who corrupts a quorum of the processors and who exercises full, malicious control over them. One of the fundamental primitives at the heart of secure computation is secret-sharing. Typically, the required secret-sharing techniques build on Shamir's scheme, which can be viewed as a cryptographic twist on the Reed-Solomon error correcting code. In this work we further the connections between secure computation and error correcting codes. We demonstrate that threshold secure computation in the secure channels model can be based on arbitrary codes, in two steps. First we identify sufficient, specialized conditions on a secret sharing scheme in order that it can serve as an essentially seamless replacement of Shamir's scheme in the context of secure computation. Second, we show how arbitrary error correcting codes give rise to such dedicated secret sharing schemes, and we prove various bounds on the relevant achievable parameters. We also analyze high information rate ramp schemes based on arbitrary codes, and in particular we give a new construction based on algebraic geometry codes. Concretely, the consequences of our results on the theory of secure computation include the following. If the field K of interest for the underlying computation is small compared to the size n of the network, say K = F₂, then, a communication overhead is incurred in existing approaches as |K| > n due to Shamir's scheme. Our results alleviate this and allow, for instance, constant size fields K as opposed to linear size, while corruption tolerance t is at most an (arbitrary) constant fraction of n away from optimal. Such a (small) loss is unavoidable over sub-linear size fields due to impossibility results from combinatorics. Our results hold in the broadcast model of Rabin and Ben-Or, and complement recent results from CRYPTO 2006, where a class of dedicated algebraic geometric secret sharing schemes was introduced that enable low-communication threshold multi-party computation over small (e.g. constant) size fields in the zero-error/perfect security/active adversary model of Ben-Or, Goldwasser and Wigderson (BGW). Our general theory can be extended so as to encompass those results from CRYPTO 2006 as well.
Eurocrypt 2007 [Proceedings Version ps, pdf]
Securely Obfuscating Re-encryption
Susan Hohenberger, Guy Rothblum, abhi shelat, and Vinod Vaikuntanathan

We present a positive obfuscation result for a traditional cryptographic functionality. This positive result stands in contrast to well-known negative impossibility results [1] for general obfuscation and recent negative impossibility and improbability [2] results for obfuscation of many cryptographic functionalities.

Whereas other positive obfuscation results in the standard model apply to very simple point functions, our obfuscation result applies to the significantly more complicated and widely-used re-encryption functionality. This functionality takes a ciphertext for message m encrypted under Alice's public key and transforms it into a ciphertext for the same message m under Bob's public key.

To overcome impossibility results and to make our results meaningful for cryptographic functionalities, our scheme satisfies a definition of obfuscation which incorporates more security-aware provisions.

[1] Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In CRYPTO '01, volume 2139 of LNCS, pages 1-18, 2001.

[2] Shafi Goldwasser and Yael Tauman Kalai. On the impossibility of obfuscation with auxiliary input. In FOCS '05, pages 553-562, 2005.
Theory of Cryptography Conference TCC 2007
Invited to the Journal of Cryptology [Full Version ps, pdf]
Fault-tolerant Distributed Computing in Full-Information Networks
S. Goldwasser, E. Pavlov and V. Vaikuntanathan

In this paper, we use random-selection protocols in the full-information model to solve classical problems in distributed computing. Our main results are the following:

1. An O(log n)-round randomized Byzantine Agreement (BA) protocol in a synchronous full-information network tolerating t < n/(3+ε) faulty players (for any constant ε>0). As such, our protocol is asymptotically optimal in terms of fault-tolerance.

2. An O(1)-round randomized BA protocol in a synchronous full-information network tolerating t = O(n/(log n)^1.58) faulty players.

3. A compiler that converts any randomized protocol Π_in designed to tolerate t fail-stop faults, where the source of randomness of Π_in is an SV-source, into a protocol Π_out that tolerates min(t, n/3) Byzantine faults. If the round-complexity of Π_in is r, that of Π_out is O(r log* n).

Central to our results is the development of a new tool, "audited protocols". Informally "auditing" is a transformation that converts any protocol that assumes built-in broadcast channels into one that achieves a slightly weaker guarantee, without assuming broadcast channels.

We regard this as a tool of independent interest, which could potentially find applications in the design of simple and modular randomized distributed algorithms.

FOCS 2006 [Proceedings Version ps, pdf]
Construction of a Non-Malleable Encryption Scheme From Any Semantically Secure One
R. Pass, A. Shelat and V. Vaikuntanathan

There are several candidate semantically secure encryption schemes, yet in many applications, non-malleability of encryptions is crucial. We show how to transform any semantically secure encryption scheme into one that non-malleable for arbitrarily many messages.
Crypto 2006 [Proceedings Version ps, pdf]
Byzantine Agreement in the Full-Information Model in O(log n) Rounds
M. Ben-Or, E. Pavlov and V. Vaikuntanathan

We present a randomized Byzantine Agreement (BA) protocol with an expected running time of O(log n) rounds, in a synchronous full-information network of n players. For any constant ε > 0, the constructed protocol tolerates t non-adaptive Byzantine faults, as long as n ≥ (4+ε)t. In the full-information model, no restrictions are placed on the computational power of the faulty players or the information available to them. In particular, the faulty players may be infinitely powerful, and they can observe all communication among the honest players.

This constitutes significant progress over the best known randomized BA protocol in the same setting which has a round-complexity of Θ(t/log n) rounds, and answers an open problem posed by Chor and Dwork.
STOC 2006 [Proceedings Version ps, pdf]
Distributed Computing With Imperfect Randomness
S. Goldwasser, M. Sudan and V. Vaikuntanathan

Randomness is a critical resource in many computational scenarios, enabling solutions where deterministic ones are elusive or even provably impossible. However, the randomized solutions to these tasks assume access to a source of unbiased, independent coins. Physical sources of randomness, on the other hand, are rarely unbiased and independent although they do seem to exhibit somewhat imperfect randomness. This gap in modeling questions the relevance of current randomized solutions to computational tasks. Indeed, there has been substantial investigation of this issue in complexity theory in the context of the applications to efficient algorithms and cryptography.

In this paper, we seek to determine whether imperfect randomness, modeled appropriately, is "good enough" for distributed algorithms. Namely, can we do with imperfect randomness all that we can do with perfect randomness, and with comparable efficiency? We answer this question in the affirmative, for the problem of Byzantine agreement. We construct protocols for Byzantine agreement in a variety of scenarios (synchronous or asynchronous networks, with or without private channels), in which the players have imperfect randomness. Our solutions are essentially as efficient as the best known randomized protocols, despite the defects in the randomness.

DISC 2005 [Proceedings Version ps, pdf]
Broadcast in Radio Networks in the Presence of Byzantine Faults
V. Vaikuntanathan

In PODC '04, Koo [3] presented a protocol that achieves broadcast in a radio network tolerating (roughly) r²/2 Byzantine faults (where r is the transmission range in the radio network). We prove that the simple protocol of [3] indeed tolerates r²/√2 faults. We also consider a generalization of the model of [3] to account for missing nodes in the network, and provide a fairly general sufficient condition for broadcast.

[3] Chiu-Yuen Koo. Broadcast in radio networks tolerating byzantine adversarial behavior. In PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, pages 275-282. ACM Press, 2004.
PODC 2005 [Full Version ps, pdf]
Information Leak in the Chord Lookup Protocol
C.W. O'Donnell and V. Vaikuntanathan

In Peer-to-peer (P2P) systems, it is often essential that connected systems (nodes) relay messages which did not originate locally, on to the greater network. As a result, an intermediate node may be able to determine a large amount of information about the system, such as the querying tendencies of other nodes. This represents an inherent security issue in P2P networks. Therefore, we ask the following question: Through the observation of the network traffic in a P2P network, what kind of information can an adversarial node learn about another node in the same network? In this paper, we study this question in the case of a specific P2P system - Chord [4]. We also study the effects of the parameters of Chord (such as finger-table size) and the various enhancements to Chord (such as location caching and data caching) on the amount of information leaked.

[4] I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internetapplications. IEEE Transactions on Networking, 11, 2003.
P2P 2004 [Proceedings Version ps, pdf]
Distributed Consensus in the Presence of Sectional Faults
A. Aiyer, I. Sanketh, K. Srinathan, V. Vaikuntanathan and C. Pandu Rangan

Consider a synchronous network of n players, each with a local input. The goal of distributed consensus is to globally agree on one of the valid inputs even if some non-trivial subset of the players are faulty. By valid input, we mean the input of any non-faulty player. Extant results in Byzantine agreement literature capture the behaviour of faulty players in an "all-or-nothing" fashion. For instance, a (Byzantine) faulty player is completely unconstrained and could behave differently with different players. This leads to a gross underestimation of the achievable fault-tolerance. In this work, we propose a fault-model that considerably improves the estimation of fault-tolerance and helps capture real-life scenarios better. For instance, if two (honest) players were part of the same LAN (which is essentially a broadcast network), it is impossible for a external faulty player to behave differently with these two players (though the faulty player may behave with "equal" malice with both these players!). Among our results, we introduce the sectional fault-model that is more general and can capture practical scenarios not captured by any extant model. We provide a complete characterization of the tolerable faults and present efficient protocols to achieve consensus. We remark that the results of this paper strictly generalize the extant characterizations of fault-tolerance. For example, consider a network of four players P₁, P₂, P₃ and P₄, under the corrupting influence of a Byzantine adversary given by the adversary structure A = {(P₁, P₂), (P₂, P₃), (P₄)}. Agreement is impossible in such a scenario, since the three sets from A cover the player set. However, it would be evident from our results that consensus in the above scenario was indeed possible if (and only if) the players P₁, P₃ and P₄ belonged to a single LAN in the network!
PODC 2003 [Proceedings Version ps, pdf]
Efficient Perfectly Secure Communication over Synchronous Networks
K. Srinathan, V. Vaikuntanathan and C. Pandu Rangan

We consider the problem of perfectly secure communication: Given a k-connected synchronous 2-way network, the sender S wants to send a message to the receiver T such that the intermediate players get no information about the message transmitted and T receives the message correctly. In [5] it was proved that perfect communication between all pairs of nodes (players) is possible iff t < k/2, where up to t among the set of k players could be actively corrupt. Further, they provide protocols with optimum fault-tolerance that communicate O(k²tl) bits for an l-bit secret message. This work improves the bit-complexity to O(max(k²log t, kl)) bits.

[5] D. Dolev, C. Dwork, O. Waarts, and M. Yung. Perfectly secure message transmission. JACM, 40(1):17-47, 1993.
PODC 2003 [Proceedings Version ps, pdf]
On the Power of Computational Secret Sharing
V. Vaikuntanathan, A. Narayanan, K. Srinathan, C. Pandu Rangan and K. Kim

Secret sharing is a very important primitive in cryptography and distributed computing. In this work, we consider computational secret sharing (CSS) which provably allows a smaller share size (and hence greater efficiency) that its information theoretic counterparts. Extant CSS schemes result in succinct share-size and are in a few cases, like threshold access structures, optimal. However, in general, they are not efficient (share-size not polynomial in the number of players n), since the either assume efficient perfect schemes for the given access structure (as in [6]) or make use of exponential (in n) amount of public information (like in [7]). In this paper, our goal is to explore other classes of access structures that admit effificent CSS, without making any other assumptions. We construct efficient CSS schemes for every structure in monotone P. As of now, most of the efficient information-theoretic schemes known are for access structures in algebraic NC². Monotone P and algebraic NC² are not comparable in the sense that one does does not include the other. Thus our work leads to secret sharing schemes for a new class of access structures. In the second part of the paper, we introduce the notion of secret sharing with a semi-trusted third party, and prove that in this relaxed model efficient CSS schemes exist for a wider class of acess structures, namely monotone NP.

[6] H. Krawczyk. Secret sharing made short. In CRYPTO '93, LNCS, pp. 136-146, 1993.

[7] Cachin. On-line secret sharing. In IMA: IMA Conference on Cryptography and Coding, LNCS lately (earlier: Cryptography and Coding II, Clarendon Press, 1992), 1995.
Indocrypt 2003 [Proceedings Version ps, pdf]