Public Key Cryptosystems: Stronger Security from General Assumptions

August 11, 2009
Tal Malkin | Columbia University

Public key encryption (PKE) allows parties that had never met in advance to communicate over an unsafe channel. The notion was conceived in the 1970s, followed by the discovery that one could provide formal definitions of security for this and other cryptographic problems, and that such definitions were achievable by assuming the hardness of some computational problem (e.g., factoring large numbers). For PKE, the most basic security definition – semantic security – guarantees privacy, namely that it is infeasible to learn anything about the plaintext from its encryption. However, as cryptographic applications grew more sophisticated, this level of security is often not sufficient, since it does not protect against active attacks arising in networked environments.

In this talk I will review some of my work aimed at achieving stronger security notions for public key encryption, including protections against adaptive corruptions, man-in-the-middle attacks (non-malleability), chosen ciphertext security, and, if time allows, tampering attacks. The emphasis of this line of work is on achieving the stronger notion from as general an assumption as possible (e.g., directly from semantically secure PKE), as well as achieving a black box construction, namely using the underlying scheme as a subroutine, without assuming it has any special structure or algebraic properties. This allows for more efficient cryptosystems that can be instantiated with a larger set of assumptions.

Based on several joint works with different coauthors. The main part of the talk will be based on joint works with Seung Geol Choi, Dana Dachman-Soled, and Hoeteck Wee.

Speaker Details

Tal Malkin is an assistant professor of Computer Science at Columbia University, where she directs the cryptography lab. She received her Ph.D. in Computer Science from the Massachusetts Institute of Technology in 2000, and joined Columbia after three years as a research scientist in the Secure Systems Research Department at AT&T Shannon Laboratory. Her research interests are in cryptography, security, complexity theory, and related areas. She has served on program committees and steering committees for over a dozen international conferences on cryptography, theoretical computer science, and security, she chaired the CT-RSA conference, and is on the editorial board for the Theory of Computing Journal. Prof. Malkin is the recipient an NSF Faculty Early Career Development award, an IBM faculty partnership award, and a research fellowship of the Columbia University Diversity Initiative. Her research is primarily funded by NSF, but she has also received research grants from NSA, NYSIA, IARPA, and Mitsubishi research lab.