Adam D. Smith

Ph.D. (MIT), 2004
Assistant Professor
Computer Science and Engineering Department
Pennsylvania State University, University Park

News

• Presidential Early Career Award for Scientists and Engineers (PECASE), for my NSF CAREER proposal on Rigorous Foundations for Data Privacy.
• I am co-organizing a workshop on Statistical and Learning-Theoretic Challenges in Data Privacy (February 22-26, 2010) at IPAM. More about the workshop here.

I am part of the Theory of Computation and the Systems and Internet Infrastructure Security (SIIS) groups at Penn State. If you are interested in cryptography or theoretical computer science, consider attending the theory seminar (or at least sign up for the mailing list).

I am interested cryptography and data privacy, and their connections to diverse fields such as information theory, combinatorics, quantum mechanics and statistics. Recently, I've focused on a few specific topics:

• Privacy-preserving publication of statistical data
• Cryptography based on noisy secrets ("fuzzy cryptography")
• Efficient two- and multi-party protocols for tasks such as agreement, commitment and secure function evaluation.
• Quantum cryptography, and quantum information theory

During Fall 2006, before coming to Penn State, I was Securing Cyberspace at UCLA's IPAM. Previously, I was a post-doc at the Weizmann Institute in Rehovot, Israel, hosted by Moni Naor. Before that, I did a Ph.D. in the Computer Science and AI Lab at MIT, under the supervision of Madhu Sudan.

Graduate applicants

The picture above was taken in
Olympic National Park, Washington
(click for a picture of Maya and me)

Teaching

• Fall 2009: (CMPSC 465) Introduction to Algorithms
• Spring 2009: (CSE 546) Cryptography.
• Fall 2008: (CSE 565) Algorithm Design and Analysis
• Spring 2008: Theoretical CS seminar
• Fall 2007:
  • Introduction to Cryptography
  • Data Privacy
• Spring 2007: CSE 465: Introduction to Algorithms
• Spring 2005:Short course on database privacy at Weizmann.

Awards

• US PECASE award, 2009, based on NSF CAREER Award, 2008.
• Microsoft Research Graduate Fellowship, 2003

Students

• Abhradeep Guha Thakurta, Ph.D. in progress.
• Youngtae Youn, Ph.D. in progress.
• Hsu-Kwang Hwang, Ph.D. (math), in progress.

• Laxman Vembar, M.S. 2008.
• Ashwinkumar Gopalrathnam, M.S. (Electrical Engineering) 2008.
• S. Ranjit Ganta, Ph.D. 2008 (co-advised with Raj Acharya).

Contact information

• Email:
  
• Office telephone: +1-814-863-0076
  Fax: +1-814-865-3176
• Mailing adress:
  338K IST building, College of Engineering
  Department of Computer Science and Engineering
  Pennsylvania State University
  University Park, PA 16802

Professional information:

• Biographical:
  • Curriculum vitae (updated Jan. '09): PDF
  • Short bio: txt
  • Portraits: 2006, 2009

• Program committee member for CRYPTO 2005, TCC 2006, CT-RSA 2007, EC'07 (Electronic Commerce), CRYPTO 2007, PPDM@ICML, QIP 2008, TQC 2008, WWW 2008 (Security & Privacy track), SCN 2008, CRYPTO 2008 , SODA 2009, CRYPTO 2009, CANS 2009, TCC 2010 .

Life:

• Sofya, Maya and Arik.

• Flowers, worries

• Pinning Down "Privacy" in Statistical Databases (.pdf). Survey/tutorial talk presented at DIMACS, February 2008, and Google Research, March 2008.

• What Can Cryptography Do For Coding Theory? Invited presentation at ICITS 2009.

• Evolving Notions of Security for Quantum Protocols (in Powerpoint XP format). Tutorial talk presented at the Classical and Quantum Information Security Workshop at Caltech, December 15-18, 2005.

• Some presentations on specific papers are also linked below.

• Fuzzy Extractors: A Brief Survey of Results from 2004 to 2006
  • Authors: Y. Dodis, L. Reyzin, A. Smith
  • Chapter in P. Tuyls, B. Skoric, T. Kevenaar, eds, Security with Noisy Data: On Private Biometrics, Secure Key Storage and Anti-Counterfeiting

• Differential Privacy for Statistics: What we Know and What we Want to Learn
  • Authors: Cynthia Dwork and Adam Smith
  • In NCHS/CDC Data Confidentiality Workshop, 2008.

• Explicit Capacity-achieving Codes for Worst-Case Additive Errors
  • Authors: Venkatesan Guruswami and Adam Smith
  • Preprint arxiv:0912.0965 [cs.IT]
  • Covered in ICITS 2009 invited talk

• Efficient, Differentially Private Point Estimators
  • Author: Adam Smith
  • Preprint arXiv:0809.4794v1 [cs.CR]

• Composability and On-Line Deniability of Authentication
  • Authors: Yevgeniy Dodis, Jonathan Katz, Adam Smith and Shabsi Walfish
  • In TCC 2009

• Defending Against Attacks on Main Memory Persistence
  • Authors: William Enck, Kevin R. B. Butler, Thomas Richardson, Patrick McDaniel, and Adam Smith
  • In ACSAC 2008.

• What Can We Learn Privately?
  • Authors: Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith
  • In FOCS 2008
  • Invited to FOCS 2008 special issue of SIAM J. Computing.

• Composition Attacks and Auxiliary Information in Data Privacy
  • Authors: Srivatsava Ranjit Ganta, Shiva Prasad Kasiviswanathan and Adam Smith
  • In KDD 2008

• Scalable Multiparty Computation with Nearly Optimal Work and Resilience
  • Authors: Ivan Damgaard, Yuval Ishai , Mikkel Kroigaard, Jesper Buus Nielsen and Adam Smith
  • IN CRYPTO 2008

• Efficient Two Party and Multi Party Computation Against Covert Adversaries.
  • Authors: Vipul Goyal, Payman Mohassel and Adam Smith
  • In Eurocrypt 2007

• Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem.
  • Authors: Sofya Raskhodnikova, Dana Ron, Amir Shpilka and Adam Smith.
  • In Symposium on the Foundations of Computer Science (FOCS) 2007 .
  • Conference version: PDF
  • The results in this paper appeared previously as part of Electronic Colloquium on Communication Complexity Technical Report TR05-125 (with additional co-author Ronitt Rubinfeld).

• Sublinear Algorithms for Approximating String Compressibility
  • Authors: Sofya Raskhodnikova, Dana Ron, Ronnitt Rubinfeld and Adam Smith.
  • In RANDOM 2007, Princeton, NJ, August 2007.
  • Conference version: pdf
  • Full version: pdf
  • The results in this paper appeared previously as part of Electronic Colloquium on Communication Complexity Technical Report TR05-125 (with additional co-author Amir Shpilka).

• Smooth Sensitivity and Sampling in Private Data Analysis
  • Authors: Kobbi Nissim, Sofya Raskhodnikova and Adam Smith.
  • In STOC 2007, San Diego, CA.

• Scrambling Adversarial Errors Using Few Random Bits
  • Author: Adam Smith
  • In SODA 2007.
  • Available as IACR ePrint Report 2006/020.

• Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority
  • Authors: Michael Ben-Or, Claude Crepeau, Daniel Gottesman, Avinatan Hassidim, and Adam Smith
  • In FOCS 2006

• Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models
  • Authors: Moni Naor, Gil Segev and Adam Smith
  • In CRYPTO 2006
  • Longer version available as ePrint report 2006/175

• Robust Fuzzy Extractors and Authenticated Key Agreement from Close Secrets
  • Authors: Yevgeniy Dodis, Jonathan Katz, Leonid Reyzin and Adam Smith.
  • In CRYPTO 2006

• Calibrating Noise to Sensitivity in Private Data Analysis
  • Authors: Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith.
  • In Theory of Cryptography (TCC) 2006, New York, March, 2006.
  • Conference version: PDF, PS

• Correcting Errors Without Leaking Partial Information
  • Authors: Yevgeniy Dodis and Adam Smith
  • In STOC 2005, Baltimore, MD, May 2005.
  • Conference version: PDF, PS
  • Seminar talk: ppt

• Approximate Quantum Error Correcting Codes and Verifiable Secret Sharing
  • Authors: Claude Crépeau, Daniel Gottesman and Adam Smith
  • In Eurocrypt 2005, Aarhus, Denmark, May 2005
  • Proceedings version: PDF, PS
  • Also quant-ph/0503139

• Secure Remote Authentication Using Biometric Data
  • Authors: Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky and Adam Smith
  • In Eurocrypt 2005, Aarhus, Denmark, May 2005
  • Proceedings version: PDF, PS,

• Towards Privacy in Public Databases
  • Authors: Shuchi Chawla, Cynthia Dwork, Frank McSherry, Adam Smith and Hoeteck Wee.
  • In Theory of Cryptography (TCC) 2005, February 2005.
  • Conference Proceedings Version: PS, PDF
  • Preliminary version (more proofs, but also more typos): PS.
  • Seminar talk: PDF, zipped Powerpoint
• Entropic Security and the Encryption of High Entropy Messages
  • Authors: Yevgeniy Dodis and Adam Smith.
  • In Theory of Cryptography (TCC) 2005, February 2005.
  • Available as IACR eprint 2004/219.
  • Seminar talk: PDF, zipped Powerpoint. Conference talk: PDF, zipped Powerpoint.
  • NOTE: There is a simpler proof of Theorem 2.1, which has a few added benefits.
    A new version of the paper is forthcoming.
• Maintaining Secrecy When Information Leakage is Unavoidable
  • Ph.D. Thesis, MIT, August 2004.
  • Supervisor: Professor Madhu Sudan

• Small Pseudo-Random Families of Matrices: Derandomizing Approximate Quantum Encryption.
  • Authors: Andris Ambainis and Adam Smith.
  • In RANDOM 2004, Cambridge, MA, August 2004.
  • Also e-print quant-ph/0404075, April 2004.
  • Proceedings version: PDF, PS.

• Efficient Proofs of Consistency for Generalized Queries on a Committed Database.
  • Authors: Rafail Ostrovsky, Charles Rackoff and Adam Smith.
  • In ICALP 2004, Turku, Finland, July 2004.
  • Proceedings version: PDF, PS
  • Longer version: PDF, PS
  • Also available as IACR ePrint Report 2004/170.

• Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data.
  • Authors: Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin and Adam Smith.
  • In Eurocrypt 2004, May 2004.
  • Accepted to SIAM Journal on Computing
  • Full version available as IACR ePrint Report 2003/235.
  • Long talk: PDF version, zipped Powerpoint

• List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument.
  • Authors: Cynthia Dwork, Ronen Shaltiel, Adam Smith and Luca Trevisan.
  • In Theory of Cryptography 2004, Boston, MA, February 2004.
  • Proceedings version: PDF, PS.
  • Conference Talk: PDF version

• Round Efficiency of Multi-Party Computation with a Dishonest Majority
  • Authors: Jonathan Katz, Rafail Ostrovsky and Adam Smith.
  • In Eurocrypt 2003, Warsaw, Poland, May 2003.
  • Conference version: PS,PDF.
  • Longer version: PDF, PS.
  • Conference talk: PDF

• Lower Bounds for Collusion-Secure Fingerprinting Codes
  • Authors: Chris Peikert, abhi shelat and Adam Smith.
  • In SODA 2003, Baltimore, Maryland, January 2003.

• Authentication of Quantum Messages,
  • Authors: Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam Smith and Alain Tapp.
  • In FOCS 2002, Vancouver, British Columbia, November 2002.
  • Also available as IACR ePrint 2002/082, and quant-ph/0205128).

• Detectable Byzantine Agreement Tolerating Faulty Majorities (from scratch),
  • Authors: Matthias Fitzi, Daniel Gottesman, Martin Hirt, Thomas Holenstein and Adam Smith.
  • In PODC 2002, Monterey, CA, July 2002.
  • Conference talk: PDF

• Quantum Multi-party Computation,
  • S.M. Thesis, MIT, August 2001.
    Supervisor: Professor Madhu Sudan.
    (PS, PDF, quant-ph/0111030).

• Quantum Multi-party Computation
  • Authors: Claude Crépeau, Daniel Gottesman and Adam Smith.
  • In STOC 2002, May 2002.
  • Proceedings version: PS
  • Talk from QIP 2002: PDF

• General Entanglement Purification Procedures,
  • Authors: Andris Ambainis, Ke Yang and Adam Smith.
  • In CCC 2002, May 2002.

• March Madness is (NP-)Hard.
  • Authors: David Liben-Nowell, Moses Liskov, Chris Peikert, abhi shelat, Adam Smith and Grant Wang.
  • Unpublished manuscript, mad March 2002. PS, PDF.

• Mutually Independent Commitment
  • Authors: Moses Liskov, Anna Lysyanskaya, Silvio Micali, Leonid Reyzin and Adam Smith.
  • In Proc. of Asiacrypt 2001, Springer LNCS 2248, pp. 385-401, December 2001.

• Efficient and Non-interactive Non-malleable Commitment,
  • Authors: Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky and Adam Smith.
  • In Proc. of Eurocrypt 2001, Springer LNCS 2045, pp. 40-59, May 2001.
  • Conference version: (Conference version)
  • Also IACR ePrint 2001/032

• On Perfect and Adaptive Security in Exposure-Resilient Cryptography
  • Authors: Yevgeniy Dodis, Amit Sahai and Adam Smith.
  • In Proc. of Eurocrypt 2001, Springer LNCS 2045, pp. 301-324, May 2001.
  • Conference talk: PDF

• My books: An Inquiry into the Nature and Causes of the Wealth of Nations, (Strahan, Cadell & Co., London, 1776) and The Theory of Moral Sentiments (Edinburgh, 1759).

• Quantum Secret Sharing for General Access Structures
  • Author: Adam Smith.
  • A note describing some results from my undergraduate research project.
  • Unpublished. Available as quant-ph/0001087.

• Technical report on multiparty computation, with Anton Stiglic (postscript), McGill University, Montreal, 1998.