Research and Publications

My Ph.D. dissertation (under the supervision of Shafi Goldwasser at MIT), concerns the area of Zero-Knowledge Protocols. Specifically, my Ph.D. work seeks to deepen our understanding of statistical zero-knowledge proofs through a novel characterization based on complete problems, and explore new challenging security concerns for zero-knowledge protocols that arise in the concurrent setting. Please see the relevant papers below for more detailed information.

Publications

Here I list publications in roughly chronological order of appearance. Note that several papers are currently being updated. For the most current version, please feel free to send me e-mail at sahai -at- cs.princeton.edu.
  1. "Pushing Disks Together - The Continuous Motion Case" (with Marshall Bern). Preliminary version appeared in Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), 1996. Invited to Journal of Computer and System Sciences, special issue for selected papers of STOC 1996 (declined). Journal version appeared in Discrete and Computational Geometry 20:499-514, 1998
  2. "A Complete Promise Problem for Statistical Zero-Knowledge" (with Salil Vadhan). Preliminary version appeared in Proceedings of 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1997. Journal version appeared in Journal of the ACM 50(2): 196-249, 2003. Note: This is an updated version, with significant additions beyond the FOCS version.
  3. "The Power of a Pebble: Exploring and Mapping Directed Graphs" (with Michael Bender, Antonio Fernandez, Dana Ron, and Salil Vadhan). Preliminary version appeared in Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), 1998. Journal version appeared in Information and Computation 176(1):1-21, 2002.
  4. "Honest-Verifier Statistical Zero Knowledge Equals General Statistical Zero Knowledge" (with Oded Goldreich and Salil Vadhan). Preliminary version appeared in Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), 1998. Journal version in preparation.
  5. "Concurrent Zero-Knowledge" (with Cynthia Dwork and Moni Naor). Preliminary version appeared in Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), 1998. Invited to Journal of Computer and System Sciences, special issue for selected papers of STOC 1998 (declined). Accepted to Journal of the ACM, final version in preparation. Note: This version significantly extends the results in the STOC paper.
  6. "Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints" (with Cynthia Dwork). Preliminary version appeared in Proceedings of CRYPTO '98, Springer-Verlag Lecture Notes in Computer Science. Journal version in preparation. Note: Newer version now available.
  7. "Trapdoor Functions and Public-Key Cryptosystems" (with Mihir Bellare, Shai Halevi, and Salil Vadhan). Conference version appeared in Proceedings of CRYPTO '98, Springer-Verlag Lecture Notes in Computer Science .
  8. "Minimizing Wirelength In Zero and Bounded Skew Clock Trees" (with Moses Charikar, Jon Kleinberg, Ravi Kumar, Sridhar Rajagopalan, and Andrew Tomkins). Preliminary version in Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999. Journal version in preparation.
  9. "Manipulating Statistical Difference" (with Salil Vadhan). In Proceedings of the DIMACS Workshop on Randomization Methods in Algorithm Design, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 43:251-270, 1999. American Mathematical Society.
  10. "Multiclass Learning, Boosting, and Error-correcting codes" (with Venkatesan Guruswami). In Proceedings of the Twelfth ACM Conference on Computational Learning Theory (COLT), 1999.
  11. "Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK" (with Oded Goldreich and Salil Vadhan). Conference version appeared in Proceedings of CRYPTO `99, Springer-Verlag Lecture Notes in Computer Science. Journal version in preparation.
  12. "Coding Constructions for Blacklisting Problems without Computational Assumptions" (with Ravi Kumar and Sridhar Rajagopalan). Conference version appeared in Proceedings of CRYPTO `99, Springer-Verlag Lecture Notes in Computer Science. Journal version in preparation.
  13. "Non-Malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization" (with Mihir Bellare). Conference version appeared in Proceedings of CRYPTO `99, Springer-Verlag Lecture Notes in Computer Science.
  14. "Pseudonym Systems" (with Anna Lysanskaya, Ronald L. Rivest, and Stefan Wolf). In Proceedings of SAC '99, Springer-Verlag Lecture Notes in Computer Science.
  15. "Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security" Conference version appeared in Proceedings of 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1999.
  16. "Query Strategies for Priced Information" (with Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon Kleinberg, and Prabhakar Raghavan) Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), 2000. Journal version invited to and appeared in Journal of Computer and System Sciences, Special Issue 64(4): 785-819, 2002.
  17. "Exposure-Resilient Functions and All-Or-Nothing Transforms" (with Ran Canetti, Yevgeniy Dodis, Shai Halevi, and Eyal Kushilevitz) Conference version to appear in Proceedings of EUROCRYPT, 2000.
  18. "Simulation-Sound Non-Interactive Zero Knowledge" Revised manuscript. Work originally done in Summer 2000.
  19. "Combinatorial Feature Selection Problems" (pdf) (with Moses Charikar, Venkatesan Guruswami, Ravi Kumar, and Sridhar Rajagopalan). Proceedings of 41st Annual Symposium on the Foundations of Computer Science, 2000.
  20. "Soft-Decision Decoding of Chinese Remainder Codes" (pdf) (with Venkatesan Guruswami and Madhu Sudan). Proceedings of 41st Annual Symposium on the Foundations of Computer Science, 2000. Journal version in preparation.
  21. "On Perfect and Adaptive Security in Exposure-Resilient Cryptography" (with Yevgeniy Dodis and Adam Smith). Proceedings of EUROCRYPT 2001.
  22. "On the (Im)possibility of Obfuscating Programs" (with Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Salil Vadhan, and Ke Yang). Proceedings of CRYPTO 2001. Journal version in final preparation, to be submitted to Journal of the ACM. Note this is an updated version, with significant additions beyond the CRYPTO version.
  23. "Robust Non-Interactive Zero Knowledge" (with Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, and Giuseppe Persiano). Proceedings of CRYPTO 2001. (This subsumes my manuscript on simulation soundness above, and achieves various extensions of the results in the manuscript.)
  24. "Universally Composable Secure Two-Party and Multi-Party Computation" (with Ran Canetti, Yehuda Lindell, and Rafail Ostrovsky). Proceedings of STOC 2002. Journal version in final preparation. To be submitted to Journal of the ACM. Note this is an updated version, with significant additions beyond the STOC version.
  25. "The Smallest Grammar Problem: Kolmogorov Complexity in Natural Models" (pdf) (with Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, April Rasala, and Abhi Shelat). Proceedings of STOC 2002. Journal version in submission to IEEE Transactions on Information Theory. This version expands beyond the STOC version.
  26. "Concurrent Zero Knowledge with Logarithmic Round Complexity" (pdf) (with Manoj M. Prabhakaran and Alon Rosen). Proceedings of FOCS 2002. Journal version in preparation.
  27. "Dimension Reduction in the L1 Norm" (with Moses Charikar). Proceedings of FOCS 2002. Journal version in preparation.
  28. "A Unified Methodology For Constructing Public-Key Encryption Schemes Secure Against Adaptive Chosen-Ciphertext Attack" (pdf) (with Edith Elkind). Cryptology ePrint Archive: Report 2002/042. In submission.
  29. "Private Circuits: Securing Hardware against Probing Attacks" (with Yuval Ishai and David Wagner). Proceedings of CRYPTO 2003.
  30. Co-Editor of Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003. (with Sanjeev Arora, Klaus Jansen, Jose D. P. Rolim (Eds.)). Princeton, NJ, USA, August 24-26, 2003. Proceedings: Lecture Notes in Computer Science 2764. Springer 2003, ISBN 3-540-40770-7.
  31. "Receiver Anonymity via Incomparable Public Keys" (with Brent Waters and Ed Felten). Proceedings of the 10th ACM Conference on Computer and Communications Security, 2003.
  32. "Frugality in Path Auctions" (with Edith Elkind and Ken Steiglitz). Proceedings of 15th Annual Symposium on Discrete Algorithms (SODA), 2004.