Bio

I am with the Cryptography group at IBM T.J. Watson on a
Josef Raviv postdoctoral fellowship; Tal Rabin is my mentor at IBM.

Until October 2008, I was a Ph.D. candidate in the Theory of Computation group at MIT; I am very fortunate to have Shafi Goldwasser as my advisor.

I am primarily interested in cryptography, with other interests being distributed algorithms and complexity theory.

Curriculum Vitae [pdf] (a bit outdated)

Program Committees

Seventh IACR Theory of Cryptography Conference TCC 2010, Zurich, Switzerland
Thirtieth International Cryptology Conference CRYPTO 2010, Santa Barbara, California.

Selected Publications

Signature Schemes with Bounded Leakage Resilience
J. Katz and V. Vaikuntanathan
Password-based Authenticated Key-exchange based on Lattices
J. Katz and V. Vaikuntanathan
Round-optimal Password-based Key-exchange
J. Katz and V. Vaikuntanathan
Computing s-t Min-cuts in the Semi-streaming Model
M. Badoiu and A. Sidiropoulos and V. Vaikuntanathan
Public-key Encryption Schemes with Auxiliary Inputs and Applications
Y. Kalai and V. Vaikuntanathan
Simultaneous Hardcore Bits and Cryptography against Memory Attacks
A. Akavia, S. Goldwasser and V. Vaikuntanathan
TCC 2009. [Proceedings Version]
Weak Verifiable Random Functions
Z. Brakerski, S. Goldwasser, G. Rothblum and V. Vaikuntanathan
TCC 2009. [Proceedings Version]
How Efficient Can Memory-Checking Be?
C. Dwork, M. Naor, G. Rothblum and V. Vaikuntanathan
TCC 2009. [Proceedings Version]
Adaptive One-way Functions and Applications
O. Pandey, R. Pass and V. Vaikuntanathan
CRYPTO 2008 [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]
Lattice-based Crypto Papers
- Trapdoors for Hard Lattices, and New Cryptographic Constructions
  C. Gentry, C. Peikert and V. Vaikuntanathan
  STOC 2008 [ps, pdf]
- A Framework for Efficient and Composable Oblivious Transfer
  C. Peikert, V. Vaikuntanathan and B. Waters
  CRYPTO 2008 [ps, pdf]
- Non-Interactive Statistical Zero-knowledge for Lattice Problems
  C. Peikert and V. Vaikuntanathan
  CRYPTO 2008 [pdf]
PSV Papers on Non-malleable Encryption
- 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]
- 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]
The Distributed Computing Papers
- 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]
- 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]
- 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]

Bio

Program Committees

Selected Publications

Lattice-based Crypto Papers

PSV Papers on Non-malleable Encryption

The Distributed Computing Papers

Full List of Publications