Research and Selected Publications

(Currently incomplete; more information coming soon! A full list of papers is available here.)

Foundations of Cryptography

Research in this area focuses on definitions and cryptographic primitives, as well as research regarding secure two-party and multi-party computation.

"Lower Bounds on the Efficiency of 'Black-Box' Commitment Schemes" (with Omer Horvitz). ICALP 2005
"Reducing Complexity Assumptions for Statistically-Hiding Commitment" (with Iftach Haitner, Omer Horvitz, Chiu-Yuen Koo, Ruggero Morselli, and Ronen Shaltiel). Eurocrypt 2005
"Adaptively-Secure, Non-Interactive Public-Key Encryption" (with Ran Canetti and Shai Halevi). 2nd Theory of Cryptography Conference, 2005
"Handling Expected Polynomial-Time Strategies in Simulation-Based Security Proofs" (with Yehuda Lindell). 2nd Theory of Cryptography Conference, 2005
"Identity-Based Zero Knowledge" (with Rafail Ostrovsky and Michael Rabin). Security in Communication Networks 2004.
"Round-Optimal Secure Two-Party Computation" (with Rafail Ostrovsky). Crypto 2004.
"Chosen-Ciphertext Security from Identity-Based Encryption" (with Ran Canetti and Shai Halevi). Eurocrypt 2004.
"Efficiency Improvements for Signature Schemes with Tight Security Reductions" (with Nan Wang). ACM CCCS 2003.
"Bounds on the Efficiency of Generic Cryptographic Constructions" (with Rosario Gennaro, Yael Gertner, and Luca Trevisan). A preliminary version of STOC 2003, and a full version will appear in the SIAM Journal of Computing.
"Round Efficiency in Multi-Party Computation with Dishonest Majority" (with Rafail Ostrovsky and Adam Smith). Eurocrypt 2003.
"Cryptographic Counters and Applications to Electronic Voting" (with Steven Myers and Rafail Ostrovsky). Eurocrypt 2001.
"Characterization of Security Notions for Probabilistic, Private-Key Encryption" (with Moti Yung). A preliminary version appeared in STOC 2000, and a full version will appear in the Journal of Cryptology.

Authentication and Key Exchange

Protocols for authentication and for the generation of cryptogaphically-strong keys among a set of parties in a larger (and insecure) network underlie most secure interactions taking place on the Internet. Mutual authentication protocols ensure that the intended partners are indeed talking to each other, while key exchange protocols are used to establish a common key which may then be used to protect the confidentiality and integrity of the subsequent conversation.

I am interested in a number of topics within this area, including: password-based authentication, protocols for group key exchange, and feasibility results in generalized network settings.

"Modeling Insider Attacks on Group Key Exchange Protocols" (with Ji Sun Shin). ACM CCCS 2005.
"Two-Server Password-Only Authenticated Key Exchange" (with Phil MacKenzie, Gelareh Taban, and Virgil Gligor). Applied Cryptography and Network Security (ACNS) 2005.
"Universally Composable Password-Based Key Exchange" (with Ran Canetti, Shai Halevi, Yehuda Lindell, and Phil MacKenzie). Eurocrypt 2005.
"One-Round Protocols for Two-Party Authenticated Key Exchange" (with Ik Rae Jeong and Dong Hoon Lee). Applied Cryptography and Network Security 2004.
"Scalable Protocols for Authenticated Group Key Exchange" (with Moti Yung). Crypto 2003.
"Forward Secrecy in Password-Only Key Exchange Protocols" (with Rafail Ostrovsky and Moti Yung). Security in Communication Networks (SCN) 2002.
"Efficient Password-Authenticated Key Exchange Using Human-Memorizable Passwords" (with Rafail Ostrovsky and Moti Yung). Eurocrypt 2001. A full version of this work appears as a chapter in my PhD thesis (see below).

Cryptographic Systems Resistant to Exposure of Secret Keys

Exposure of secret keys can be a devastating attack on a cryptosystem since such an attack typically implies that all security guarantees are lost. Indeed, standard notions of securty offer no protection whatsoever once the secret key is exposed. With the threat of key exposure becoming more acute as cryptographic algorithms are increasingly deployed on small, mobile, and easily compromised devices, new techniques are needed to deal with this concern.

I am working on modeling different ways to protect against key exposure, and on designing provably-secure systems which are resilient to such attacks.

"Chosen Ciphertext Security of Multiple Encryption" (with Yevgeniy Dodis). 2nd Theory of Cryptography Conference, 2005
"A Generic Construction for Intrusion-Resilient Public-Key Encryption" (with Yevgeniy Dodis, Matt Franklin, Atsuko Miyaji, and Moti Yung). RSA 2004 --- Cryptographers' Track.
"A Forward-Secure Public-Key Encryption Scheme" (with Ran Canetti and Shai Halevi). Eurocrypt 2003.
"Intrusion-Resilient Public-Key Encryption" (with Yevgeniy Dodis, Matt Franklin, Atsuko Miyaji, and Moti Yung). RSA 2003 --- Cryptographers' Track.
"Strong Key-Insulated Signature Schemes" (with Yevgeniy Dodis, Shouhuai Xu, and Moti Yung). Public-Key Cryptography 2003.
"Key-Insulated Public-Key Cryptosystems" (with Yevgeniy Dodis, Shouhuai Xu, and Moti Yung). Eurocrypt 2002.

Security in Distributed Systems

Some relevant papers... (more info coming soon!)

"A Pairwise Key Pre-Distribution Scheme for Wireless Sensor Networks" (with Wenliang Du, Jing Deng, Yunghsiang S. Han, Pramod K. Varshney, and Aram Khalili). ACM Transactions on Information and System Security 8(2): 228-258, 2005.
"A Game-Theoretic Framework for Analyzing Trust-Inference Protocols" (with Ruggero Morselli and Bobby Bhattacharjee). Second Workshop on the Economics of Peer-to-Peer Systems, 2004.
"Trust Preserving Set Operations" (with Ruggero Morselli, Bobby Bhatacharjee, and Pete Keleher). IEEE Infocom 2004.
"Toward Secure Key Distribution in Truly Ad-Hoc Networks" (with Bill Arbaugh and Aram Khalili). IEEE Workshop on Security and Assurance in Ad-Hoc Networks.
"Threshold Cryptosystems Based on Factoring" (with Moti Yung). Asiacrypt 2002.

Protocols Preventing "Man-in-the-Middle" Attacks

In the analysis of many cryptographic protocols, it is useful to distinguish between passive attacks in which an adversary eavesdrops on messages sent between honest users and active attacks (i.e., ``man-in-the-middle'' attacks) in which --- in addition to eavesdropping --- the adversary inserts, deletes, or arbitrarily modifies messages sent from one user to another. Passive attacks are well understood; indeed, much work in the 1970's and 1980's dealt with formalizing notions of security and providing provably-secure solutions for this setting. On the other hand, active attacks are not well characterized and precise modeling has been difficult. In addition, few techniques exist for dealing with active attacks; it is fair to say that designing practical protocols secure against such attacks remains a challenge.

My research has focused on active attacks in a variety of settings and has led to new, provably-secure protocols preventing such attacks. I have especially concentrated on the design and analysis of efficient and practical protocols which may be proven secure in the standard cryptographic model. (For other research focused on preventing man-in-the-middle attacks, see the section on "Authentication and Key-Exchange". Research aimed at exploiting man-in-the-middle attacks on some real-world systems appears in the section "Cryptanalysis of Real-World Protocols".)

"Chosen-Ciphertext Security from Identity-Based Encryption" (with Ran Canetti and Shai Halevi). Eurocrypt 2004.
"Efficient and Non-Malleable Proofs of Plaintext Knowledge and Applications". Eurocrypt 2003.
"Efficient Cryptographic Protocols Preventing 'Man-in-the-Middle' Attacks". PhD Thesis, Columbia University, 2002.
"Efficient and Non-Interactive Non-Malleable Commitment" (with Giovanni Di Crescenzo, Rafail Ostrovsky, and Adam Smith). Eurocrypt 2001.

Private-Key Cryptography

Some relevant papers (more info coming soon!)

"Incremental and Unforgeable Encryption" (with Enrico Buonanno and Moti Yung). Fast Software Encryption 2001.
"Unforgeable Encryption and Chosen-Ciphertext-Secure Modes of Operation" (with Moti Yung). Fast Software Encryption 2000.

Cryptanalysis of Real-World Protocols

Some relevant papers (more info coming soon!)

"Implementation of Chosen-Ciphertext Attacks Against PGP and GnuPG" (with Kahil Jallad and Bruce Schneier). Information Security Conference 2002.
"A Chosen-Ciphertext Attack Against Several Email Encryption Protocols" (with Bruce Schneier). USENIX Security Symposium 2000