Research and Publications

(Above: A wordle representing the titles of my papers, updated August 2009.)

Please email me for further details regarding any of the papers below.

To Appear:

"On the (Im)possibility of Obfuscating Programs" (with Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Salil Vadhan, and Ke Yang). Journal of the ACM. (accepted pending minor revision)
[pdf]

“Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy” (with Yi Deng and Vipul Goyal). Proceedings of FOCS 2009. (to appear)

“Extracting Correlations” (with Yuval Ishai, Eyal Kushilevtiz, and Rafail Ostrovsky). Proceedings of FOCS 2009. (to appear)

2009

"Zero-Knowledge from Secure Multiparty Computation" (with Yuval Ishai, Eyal Kushilevitz, and Rafail Ostrovsky). SIAM Journal on Computing, Special Issue for STOC 2007. Volume 39, Issue 3, pp. 1121-1152 (2009)
[pdf]

“Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems” (with Benny Applebaum, David Cash, and Chris Peikert). Proceedings of CRYPTO 2009.
[pdf]

“Resettably Secure Computation” (with Vipul Goyal). Proceedings of Proceedings of EUROCRYPT 2009.

“Secure Arithmetic Computation with No Honest Majority” (with Yuval Ishai and Manoj Prabhakaran). Proceedings of TCC 2009.
[pdf]

2008

“Black-Box Accountable Authority Identity-Based Encryption” (with Vipul Goyal, Steve Lu, and Brent Waters). Proceedings of ACM Conference on Computer and Communications Security, 2008.

“Founding Cryptography on Oblivious Transfer—Efficiently” (with Yuval Ishai and Manoj Prabhakaran). Proceedings of CRYPTO 2008.

“Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products” (with Jonathan Katz and Brent Waters). Proceedings of EUROCRYPT 2008.

“Precise Concurrent Zero Knowledge” (with Omkant Pandey, Rafael Pass, Wei-Lung Dustin Tseng, and Muthuramakrishnan Venkitasubramaniam). Proceedings of EUROCRYPT 2008.

“Efficient Non-interactive Proof Systems for Bilinear Groups” (with Jens Groth). Proceedings of EUROCRYPT 2008.

“New Constructions for UC Secure Computation Using Tamper-Proof Hardware” (with Nishanth Chandran and Vipul Goyal). Proceedings of EUROCRYPT 2008.

“Bounded Ciphertext Policy Attribute Based Encryption” (with Vipul Goyal, Abhishek Jain, and Omkant Pandey). Proceedings of ICALP 2008.

“Computing on Encrypted Data”. Invited Talk and Paper. Proceedings of ICISS 2008.

“Cryptography with Constant Computational Overhead” (with Yuval Ishai, Eyal Kushilevitz, and Rafail Ostrovsky). Proceedings of STOC 2008.

“Improved Algorithms for Optimal Embeddings” (with Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, and Mohammad Ali Safari). ACM Transactions on Algorithms 4(4), 2008.

2007

“Attribute-Based Encryption with Non-Monotonic Access Structures” (with Rafail Ostrovsky and Brent Waters). Proceedings of ACM Conference on Computer and Communications Security, 2007.

“Concurrent Statistical Zero-Knowledge Arguments for NP from One Way Functions” (with Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky). Proceedings of ASIACRYPT 2007.

“Covert Multi-Party Computation” (with Nishanth Chandran, Vipul Goyal, and Rafail Ostrovsky). Proceedings of FOCS 2007.

“Private Locally Decodable Codes” (with Rafail Ostrovsky and Omkant Pandey). Proceedings of ICALP 2007.

“Ring Signatures of Sub-linear Size Without Random Oracles” (with Nishanth Chandran and Jens Groth). Proceedings of ICALP 2007.

“Ciphertext-Policy Attribute-Based Encryption” (with John Bethencourt and Brent Waters). Proceedings of IEEE Symposium on Security and Privacy, 2007.

“Zero-Knowledge from Secure Multiparty Computation” (with Yuval Ishai, Eyal Kushilevitz, and Rafail Ostrovsky). Proceedings of STOC 2007.

2006

“Attribute-Based Encryption for Fine-Grained Access Control of Encrypted Data” (with Vipul Goyal, Omkant Pandey, and Brent Waters). Proceedings of ACM Conference on Computer and Communications Security, 2006.

“Non-Interactive Zaps and New Techniques for NIZK” (with Jens Groth and Rafail Ostrovsky). Proceedings of CRYPTO 2006.

“Private Circuits II: Keeping Secrets in Tamperable Circuits” (with Yuval Ishai, Manoj Prabhakaran, and David Wagner). Proceedings of EUROCRYPT 2006.

“Perfect Non-interactive Zero Knowledge for NP” (with Jens Groth and Rafail Ostrovsky). Proceedings of EUROCRYPT 2006.

“Sequential Aggregate Signatures and Multisignatures Without Random Oracles” (with Steve Lu, Rafail Ostrovsky, Hovav Shacham, and Brent Waters). Proceedings of EUROCRYPT 2006.

“Fully Collusion Resistant Traitor Tracing with Short Ciphertexts and Private Keys” (with Dan Boneh and Brent Waters). Proceedings of EUROCRYPT 2006.

“Cryptography from Anonymity” (with Yuval Ishai, Eyal Kushilevitz, and Rafail Ostrovsky). Proceedings of FOCS 2006.

“Concurrent Non-Malleable Zero Knowledge” (with Boaz Barak and Manoj Prabhakaran). Proceedings of FOCS 2006.

“Concurrent Zero Knowledge Without Complexity Assumptions” (with Daniele Micciancio, Shien Jin Ong, and Salil Vadhan). Proceedings of TCC 2006.

2005

“Fuzzy Identity-Based Encryption” (with Amit Sahai and Brent Waters). Proceedings of EUROCRYPT 2005.

“How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation” (with Boaz Barak). Proceedings of FOCS 2005.

“Relaxing Environmental Security: Monitored Functionalities and Client-Server Computation” (with Manoj Prabhakaran). Proceedings of TCC 2005.

“The Smallest Grammar Problem” (with Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, and Abhi Shelat). IEEE Transactions on Information Theory 51(7), 2005.

2004

“Positive Results and Techniques for Obfuscation” (with Ben Lynn and Manoj Prabhakaran). Proceedings of EUROCRYPT 2004.

“On the (Im)possibility of Cryptography with Imperfect Randomness” (with Yevgeniy Dodis, Shien Jin Ong, and Manoj Prabhakaran). Proceedings of FOCS 2004.

“Secure Protocols for Complex Tasks in Complex Environments” Invited Talk and Paper. Proceedings of INDOCRYPT 2004.

“Frugality in Path Auctions” (with Edith Elkind and Kenneth Steiglitz). Proceedings of SODA 2004.

“New Notions of Security: Achieving Universal Composability Without Trusted Setup” (with Manoj Prabhakaran). Proceedings of STOC 2004.

“Batch Codes and Their Applications” (with Yuval Ishai, Eyal Kushilevitz, and Rafail Ostrovsky). Proceedings of STOC 2004.

“Concurrent Zero-Knowledge” (with Cynthia Dwork and Moni Naor). Journal of the ACM 51(6), 2004.

“Minimizing Wirelength in Zero and Bounded Skew Clock Trees” (with Moses Charikar, Jon M. Proceedings of Kleinberg, Ravi Kumar, Sridhar Rajagopalan, and Andrew Tomkins). SIAM J. Proceedings of Discrete Math. 17(4), 2004.

2003

Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (with Sanjeev Arora, Klaus Jansen, and José D. Rolim, editors). Proceedings of 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.

“Receiver Anonymity via Incomparable Public Keys” (with Brent Waters and Edward Felten). Proceedings of ACM Conference on Computer and Communications Security, 2003.

“Private Circuits: Securing Hardware against Probing Attacks” (with Yuval Ishai and David Wagner). Proceedings of CRYPTO 2003.

“A Complete Problem for Statistical Zero Knowledge” (with Salil Vadhan). Journal of the ACM 50(2), 2003.

2002

“Concurrent Zero Knowledge with Logarithmic Round-Complexity” (with Manoj Prabhakaran and Alon Rosen). Proceedings of FOCS 2002.

“Dimension Reduction in the \ell _1 Norm” (with Moses Charikar). Proceedings of FOCS 2002.

“Universally Composable Two-Party and Multi-Party Secure Computation” (with Ran Canetti, Yehuda Lindell, and Rafail Ostrovsky). Proceedings of STOC 2002.

[pdf] Full version available here: [pdf]

“Approximating the smallest grammar: Kolmogorov complexity in natural models” (with Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, April Rasala, and abhi shelat). Proceedings of STOC 2002.

“The Power of a Pebble: Exploring and Mapping Directed Graphs” (with Michael Bender, Antonio Fernández, Dana Ron, and Salil Vadhan). Information and Computation 176(1), 2002.

“Query Strategies for Priced Information” (with Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon Kleinberg, and Prabhakar Raghavan). JCSS 64(4), 2002.

2001

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

[pdf] Full version available here: [pdf]

“Robust Non-interactive Zero Knowledge” (with Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, and Giuseppe Persiano). Proceedings of CRYPTO 2001.

“On Perfect and Adaptive Security in Exposure-Resilient Cryptography” (with Yevgeniy Dodis and Adam Smith). Proceedings of EUROCRYPT 2001.

2000

“Exposure-Resilient Functions and All-or-Nothing Transforms” (with Ran Canetti, Yevgeniy Dodis, Shai Halevi and Eyal Kushilevitz). Proceedings of EUROCRYPT 2000.

"Soft-Decision Decoding of Chinese Remainder Codes” (with Venkatesan Guruswami and Madhu Sudan). Proceedings of FOCS 2000.

“Combinatorial Feature Selection Problems” (with Moses Charikar, Venkatesan Guruswami, Ravi Kumar, and Sridhar Rajagopalan). Proceedings of FOCS 2000.

“Query Strategies for Priced Information” (with Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon Kleinberg, and Prabhakar Raghavan). Proceedings of STOC 2000.

1999

“Multiclass Learning, Boosting, and Error-Correcting Codes” (with Venkatesan Guruswami). Proceedings of COLT 1999.

“Can Statistical Zero Knowledge Be Made Non-interactive? or On the Relationship of SZK and NISZK” (with Oded Goldreich and Salil Vadhan). Proceedings of CRYPTO 1999.

“Non-Malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization” (with Mihir Bellare). Proceedings of CRYPTO 1999.

“Coding Constructions for Blacklisting Problems Without Computational Assumptions” (with Ravi Kumar and Sridhar Rajagopalan). Proceedings of CRYPTO 1999.

“Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security”. Proceedings of FOCS 1999.

“Minimizing Wirelength in Zero and Bounded Skew Clock Trees” (with Moses Charikar, Jon Kleinberg, Ravi Kumar, Sridhar Rajagopalan, and Andrew Tomkins). Proceedings of SODA 1999.

“Pseudonym Systems” (with Anna Lysyanskaya, Ronald Rivest, and Stefan Wolf). Proceedings of Selected Areas in Cryptography, 1999.

1998

“Many-to-One Trapdoor Functions and Their Ralation to Public-Key Cryptosystems” (with Mihir Bellare, Shai Halevi, and Salil Vadhan). Proceedings of CRYPTO 1998.

“Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints” (with Cynthia Dwork). Proceedings of CRYPTO 1998.

“The Power of a Pebble: Exploring and Mapping Directed Graphs” (with Michael Bender, Antonio Fernández, Dana Ron, and Salil Vadhan). Proceedings of STOC 1998.

“Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge” (with Oded Goldreich and Salil Vadhan). Proceedings of STOC 1998.

“Concurrent Zero-Knowledge” (with Cynthia Dwork and Moni Naor). Proceedings of STOC 1998.

“Pushing Disks Together - The Continuous-Motion Case” (with Marshall Bern). Discrete & Computational Geometry 20(4), 1998.

1997

“A Complete Promise Problem for Statistical Zero-Knowledge” (with Salil Vadhan). Proceedings of FOCS 1997.

1996

“Pushing Disks Together - The Continuous-Motion Case” (with Marshall Bern). Proceedings of STOC 1996.