Research

[Back to Adam Smith's home page.]

I am interested cryptography and data privacy, and their connections to diverse fields such as information theory, combinatorics, quantum mechanics and statistics.

Tutorial Presentations

• Tutorial (video) on differential privacy at the 2019 North American School of Information Theory

• Invited talk at PPML 2018 on models for private data analysis of distributed data (slides)

• Tutorial (slides and video) on a few aspects of differential privacy at the 2017 Bar-Ilan Winter School on Cryptography.

• Tutorial on Privacy in Statistical Databases from Crypto & Big Data workshop at Columbia, December 2015 (slides)
  • Older, longer version on privacy in statistical databases at CRYPTO 2012 (slides (pdf, 15.7 MB)).

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

Surveys

• Information, Privacy and Stability in Adaptive Data Analysis
  • Adam Smith
  • To appear in IEEE Information Theory Society Newsletter
  • Available as arXiv:1706.00820 [cs.LG] (pdf)
• Exposed! A Survey of Attacks on Private Data
  • Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman
  • Annual Review of Statistics and Its Application, Vol. 4, Issue 1, pp. 61-84, 2017.
• Cryptography and the Economics of Supervisory Information: Balancing Transparency and Confidentiality
  • Mark D. Flood, Jonathan Katz, Stephen J. Ong, Adam Smith
  • FRB of Cleveland Working Paper No. 13-12 and Office of Financial Research Working Paper #11, Sept. 2013

• Fuzzy Extractors: A Brief Survey of Results from 2004 to 2006
  • 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
  • Cynthia Dwork and Adam Smith
  • NCHS/CDC Data Confidentiality Workshop, 2008.

Manuscripts (comments welcome)

• Non-parametric Differentially Private Confidence Intervals for the Median. Jörg Drechsler, Ira Globus-Harris, Audra McMillan, Jayshree Sarathy, Adam D. Smith. CoRR abs/2106.10333 (2021)
• The Price of Differential Privacy under Continual Observation. Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, Adam D. Smith. CoRR abs/2112.00828 (2021)
• Private Algorithms Can Always Be Extended. Christian Borgs, Jennifer Chayes, Adam Smith, Ilias Zadik. arXiv:1810.12518 [math.ST]
• Quantum Secret Sharing for General Access Structures. Adam Smith. arXiv:quant-ph/0001087, January 2000. (A note describing some results from my undergraduate research project.)
• Multiparty computation unconditionally secure against Q² adversary structures (unpublished technical report). Adam Smith and Anton Stiglic. McGill University, Montreal, 1998.

Publications (dblp, Google Scholar)

• Differentially Private Simple Linear Regression
  • Daniel Alabi, Audra McMillan, Jayshree Sarathy, Adam D. Smith, Salil P. Vadhan
  • Proc. Priv. Enhancing Technol. (PETS) 2022(2): 184-204 (2022)
  • arXiv 2007.05157
• Differntially Private Model Personalization
  • Prateek Jain, J. Keith Rush, Adam Smith, Shuang Song, Abhradeep Guha Thakurta
  • NeurIPS 2021 (spotlight)
• Differentially Private Sampling from Distributions
  • Sofya Raskhodnikova, Satchit Sivakumar, Adam Smith, Marika Swanberg
  • NeurIPS 2021
• Covariance-Aware Private Mean Estimation Without Private Covariance Estimation
  • Gavin Brown, Marco Gaboardi, Adam D. Smith, Jonathan R. Ullman, Lydia Zakynthinou
  • NeurIPS 2021 (spotlight)
  • arXiv: 2106.13329
• When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?
  • Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, Kunal Talwar.
  • STOC 2021
  • arXiv:2012.06421 [cs.LG]. (Talk video)
• Manipulation Attacks in Local Differential Privacy
  • Albert Cheu, Adam Smith, Jonathan Ullman.
  • In IEEE Symposium on Security and Privacy (Oakland) 2021
  • arXiv:1909.09630 [cs.DS]
• Turning HATE Into LOVE: Homomorphic Ad Hoc Threshold Encryption for Scalable MPC.
  • Leonid Reyzin, Adam Smith, Sophia Yakoubov.
  • CSCML 2021: 361-378
  • IACR ePrint 2018/997, 2018.
• The Flajolet-Martin Sketch Itself Preserves Differential Privacy: Private Counting with Minimal Space
  • Adam Smith, Shuang Song, Abhradeep Thakurta
  • In NeurIPS 2020
• Guaranteed Validity for Empirical Approaches to Adaptive Data Analysis.
  • Ryan Rogers, Aaron Roth, Adam Smith, Nathan Srebro, Om Thakkar, Blake Woodworth.
  • AISTATS 2020.
  • arXiv:1906.09231 [cs.LG]
• The Structure of Optimal Private Tests for Simple Hypotheses
  • Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam Smith, Jonathan Ullman
  • STOC 2019
  • arXiv:1811.11148 [cs.DS]
• Distributed Differential Privacy via Shuffling.
  • Albert Cheu, Adam D. Smith, Jonathan Ullman, David Zeber, Maxim Zhilyaev.
  • EUROCRYPT (1) 2019, p. 375-403.
• From Soft Classifiers to Hard Decisions: How fair can we be?
  • Ran Canetti, Aloni Cohen, Nishanth Dikkala, Govind Ramnarayan, Sarah Scheffler, Adam D. Smith.
  • In ACM FAT* 2019, p. 309-318.
• Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimation
  • Christian Borgs, Jennifer T. Chayes, Adam D. Smith, Ilias Zadik.
  • FOCS 2018: 533-543
• Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
  • Blake E. Woodworth, Jialei Wang, Adam D. Smith, Brendan McMahan, Nati Srebro
  • NeurIPS 2018: 8505-8515
• The Limits of Post-Selection Generalization
  • Jonathan Ullman, Adam D. Smith, Kobbi Nissim, Uri Stemmer, Thomas Steinke
  • NeurIPS 2018: 6402-6411
• When is Nontrivial Estimation Possible for Graphons and Stochastic Block Models?
  • Audra McMillan, Adam Smith
  • Information and Inference, Vol. 7, No. 2, 2017.
  • arXiv:1604.01871 [math.ST]
• Is Interaction Necessary for Distributed Private Learning?
  • A. Smith, A. Thakurta, J. Upadhyay
  • Oakland 2017 (IEEE Symposium on Security and Privacy)
• Calibrating Noise to Sensitivity in Private Data Analysis.
  • C. Dwork, F. McSherry, K. Nissim, A. Smith.
  • J. Privacy and Confidentiality, Vol. 7, No. 3, 2016.
  • 2017 Gödel Prize recipient.
• Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing
  • Ryan Rogers, Aaron Roth, Adam Smith, Om Thakkar.
  • FOCS 2016
  • arXiv:1604.03924 [cs.LG]
• Efficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributions
  • Sofya Raskhodnikova, Adam Smith
  • FOCS 2016
  • arXiv:1504.07912 [cs.CR]
• When Are Fuzzy Extractors Possible?
  • Benjamin Fuller, Leonid Reyzin, Adam Smith
  • ASIACRYPT 2016
  • IACR eprint 2014/961
• Reusable Fuzzy Extractors for Low-entropy Distributions
  • Ran Canetti, Benjamin Fuller, Omer Paneth, Leonid Reyzin, Adam Smith
  • EUROCRYPT 2016
  • IACR eprint 2014/243
• Algorithmic Stability for Adaptive Data Analysis
  • Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, Jonathan Ullman
  • STOC 2016
  • arXiv:1511.02513 [cs.LG] (subsumes the earlier preprint at arXiv:1503.04843), updated November 2015.
• Private Graphon Estimation for Sparse Graphs
  • Christian Borgs, Jennifer T. Chayes, Adam Smith
  • NIPS 2015
  • arXiv:1506.06162 [math.ST], April 2015.
  • NIPS poster
• On the Robust Traceability of Trace Amounts
  • Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, Salil Vadhan
  • FOCS 2015
  • Slides from Dagstuhl workshop on genetic privacy
• Local, Private, Efficient Protocols for Succinct Histograms
  • Raef Bassily, Adam Smith
  • STOC 2015
  • arXiv:1504.04686 [cs.CR]
• On the Regularity of Lossy RSA: Improved Bounds and Applications to Padding-Based Encryption
  • Adam Smith, Ye Zhang
  • TCC 2015
  • IACR eprint 2015/027
• Privacy-Preserving Public Information for Sequential Games
  • Avrim Blum, Jamie Morgenstern, Ankit Sharma, Adam Smith
  • ITCS 2015
  • arXiv:1402.4488 [cs.GT]
• Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
  • Raef Bassily, Abhradeep Thakurta, Adam Smith
  • FOCS 2014
  • arXiv:1405.7085 [cs.LG]
• Causal Erasure Channels
  • Raef Bassily, Adam Smith
  • SODA 2014
• On the `Semantics' of Differential Privacy: A Bayesian Formulation
  • Shiva Prasad Kasiviswanathan, Adam Smith
  • J. Privacy and Confidentiality, 6(1), Article 1, 2014.
  • arXiv:0803.3946 [cs.CR], originally posted March 2008.
• (Nearly) Optimal Algorithms for Private Online Learning in Full-information and Bandit Settings
  • Abhradeep Thakurta, Adam Smith
  • NIPS 2013
• Coupled-Worlds Privacy: Exploiting Adversarial Uncertainty in Statistical Data Privacy
  • Raef Bassily, Adam Groce, Jonathan Katz, Adam Smith
  • FOCS 2013
• Differentially Private Feature Selection via Stability Arguments, and the Robustness of the Lasso
  • Abhradeep Thakurta, Adam Smith
  • COLT 2013
• Regularity of Lossy RSA on Subdomains and its Applications.
  • Mark Lewko, Adam O'Neill, Adam Smith.
  • Eurocrypt 2013
• Analyzing Graphs with Node Differential Privacy
  • Shiva Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith.
  • TCC 2013
• The Power of Linear Reconstruction Attacks.
  • Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam Smith.
  • SODA 2013.
• Private Convex Empirical Risk Minimization and High-dimensional Regression
  • Daniel Kifer, Adam Smith, Abhradeep Thakurta
  • COLT 2012.
• Private Analysis of Graph Structure
  • Vishesh Karwa, Sofya Raskhodnikova, Adam Smith and Grigory Yaroslavtsev.
  • PVLDB 4(11): 1146-1157 (2011).
• Classical Cryptographic Protocols in a Quantum World
  • Sean Hallgren, Adam Smith, Fang Song
  • CRYPTO 2011
  • Also appeared as a featured paper at QIP 2011
  • Crypto 2011 talk by Fang Song: video
• Privacy-preserving Statistical Estimation with Optimal Convergence Rates
  • Adam Smith
  • STOC 2011.
• Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate
  • Venkatesan Guruswami and Adam Smith
  • FOCS 2010
  • arXiv:1004.4017 [cs.IT]
  • Accepted to Journal of the ACM
  • Subsumes an older manuscript (Explicit Capacity-achieving Codes for Worst-Case Additive Error)
• Instantiability of RSA-OAEP under Chosen-Plaintext Attack
  • Eike Kiltz, Adam O'Neill and Adam Smith.
  • CRYPTO 2010
• Discovering frequent patterns in sensitive data
  • Raghav Bhaskar, Srivatsan Laxman, Adam Smith, Abhradeep Thakurta
  • KDD 2010
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows.
  • Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam Smith and Jonathan Ullman.
  • STOC 2010, p. 775-784.
• Efficient, Differentially Private Point Estimators
  • Adam Smith
  • Preprint arXiv:0809.4794v1 [cs.CR]
• Composability and On-Line Deniability of Authentication
  • Yevgeniy Dodis, Jonathan Katz, Adam Smith and Shabsi Walfish
  • TCC 2009
• Defending Against Attacks on Main Memory Persistence
  • William Enck, Kevin R. B. Butler, Thomas Richardson, Patrick McDaniel, and Adam Smith
  • ACSAC 2008.
• What Can We Learn Privately?
  • Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith
  • FOCS 2008
  • Invited to FOCS 2008 special issue of SIAM J. Computing.
• Composition Attacks and Auxiliary Information in Data Privacy
  • Srivatsava Ranjit Ganta, Shiva Prasad Kasiviswanathan and Adam Smith
  • KDD 2008
• Scalable Multiparty Computation with Nearly Optimal Work and Resilience
  • 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.
  • Vipul Goyal, Payman Mohassel and Adam Smith
  • Eurocrypt 2007
• Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem.
  • Sofya Raskhodnikova, Dana Ron, Amir Shpilka and Adam Smith.
  • Preliminary version on Symposium on the Foundations of Computer Science (FOCS) 2007 .
  • Full version in SIAM Journal on Computing, 39(3):813-842, 2009.
  • 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
  • Sofya Raskhodnikova, Dana Ron, Ronnitt Rubinfeld and Adam Smith.
  • 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
  • Kobbi Nissim, Sofya Raskhodnikova and Adam Smith.
  • STOC 2007, San Diego, CA.

• Scrambling Adversarial Errors Using Few Random Bits
  • Adam Smith
  • SODA 2007.
  • Available as IACR ePrint Report 2006/020.
• Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority
  • Michael Ben-Or, Claude Crepeau, Daniel Gottesman, Avinatan Hassidim, and Adam Smith
  • FOCS 2006
• Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models
  • Moni Naor, Gil Segev and Adam Smith
  • CRYPTO 2006
  • Longer version available as ePrint report 2006/175
• Robust Fuzzy Extractors and Authenticated Key Agreement from Close Secrets
  • Yevgeniy Dodis, Jonathan Katz, Leonid Reyzin and Adam Smith.
  • CRYPTO 2006
• Calibrating Noise to Sensitivity in Private Data Analysis
  • Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith.
  • Theory of Cryptography (TCC) 2006, New York, March, 2006.
  • Conference version: PDF, PS

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

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

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

• Towards Privacy in Public Databases
  • Shuchi Chawla, Cynthia Dwork, Frank McSherry, Adam Smith and Hoeteck Wee.
  • 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
  • Yevgeniy Dodis and Adam Smith.
  • 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.
  • Andris Ambainis and Adam Smith.
  • 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.
  • 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.
  • Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin and Adam Smith.
  • Eurocrypt 2004, May 2004.
  • 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.
  • Cynthia Dwork, Ronen Shaltiel, Adam Smith and Luca Trevisan.
  • 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
  • Jonathan Katz, Rafail Ostrovsky and Adam Smith.
  • Eurocrypt 2003, Warsaw, Poland, May 2003.
  • Conference version: PS,PDF.
  • Longer version: PDF, PS.
  • Conference talk: PDF

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

• Authentication of Quantum Messages,
  • Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam Smith and Alain Tapp.
  • 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),
  • Matthias Fitzi, Daniel Gottesman, Martin Hirt, Thomas Holenstein and Adam Smith.
  • 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
  • Claude Crépeau, Daniel Gottesman and Adam Smith.
  • STOC 2002, May 2002.
  • Proceedings version: PS
  • Talk from QIP 2002: PDF

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

• March Madness is (NP-)Hard.
  • David Liben-Nowell, Moses Liskov, Chris Peikert, abhi shelat, Adam Smith and Grant Wang.
  • Unpublished manuscript, mad March 2002. PS, PDF.
• Mutually Independent Commitment
  • Moses Liskov, Anna Lysyanskaya, Silvio Micali, Leonid Reyzin and Adam Smith.
  • Proc. of Asiacrypt 2001, Springer LNCS 2248, pp. 385-401, December 2001.
• Efficient and Non-interactive Non-malleable Commitment,
  • 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
  • Yevgeniy Dodis, Amit Sahai and Adam Smith.
  • 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).