Mohammad Mahmoody


CV | Teaching | Advising | Publications | Service | Talks

I am an associate professor in the Computer Science Department of the University of Virginia (UVA).

I am interested in theoretical computer science. In particular, I am interested in foundations of cryptography and its interplay with computational complexity. I am also interested in adversarial machine learning from a formal perspective. In both of these areas, I am particularly interested in understanding inherent barriers (aka "lower bounds", "impossibility results", or "separations") that might exist against using computational intractability assumptions.

I received my PhD from the Computer Science Department of Princeton University under the supervision of Boaz Barak. Prior to joining UVA, I was a postdoctoral research associate in the Computer Science Department of Cornell University under the supervision of Rafael Pass. For the 2019-2020 academic year, I was on sabbatical leave visiting UC Berkeley, hosted by Sanjam Garg.

⥣ Curriculum Vitae:

Here is my CV.

⥣ Teaching:

  • Spring 2021: Cryptography (Undergrad)
  • Spring 2019: Theory of Computation (Grad)
  • Fall 2018: Algorithms (Grad)
  • Spring 2018: Topics in Cryptography (Grad and Undergrad)
  • Fall 2017: Discrete Mathematics (Undergrad)
  • Spring 2017: Theory of Computation (Grad)
  • Fall 2016: Foundations of Cryptography (Undergrad)
  • Fall 2015: Algorithms (Grad)
  • Spring 2015: Topics in Cryptography [Seminar] (Grad and Undergrad)
  • Fall 2014: Cryptography (Grad)
  • Spring 2014: Computational Complexity (Undergrad)

    • ⥣ Advising:

  • Mohammad Hajiabadi Postdoc 2018, (jointly advised with Sanjam Garg) now assistant professor at Penn State.
  • Dimitris Diochnos Postdoc 2018-2019, now assistant professor at Oklahoma University.

  • Ameer Mohammed PhD 2013-2018, now assistant professor at Kuwait University.
  • Saeed Mahloujifar PhD 2015-2020, now postdoc at Princeton.

  • Ji Gao 2020-present.
  • Ahmadreza Rahimi 2017-present.
  • Caleb Smith 2017-present.

  • Saba Eskandarian Masters 2015-2016, now PhD student at Stanford.
  • Soheil Nematihaji Masters 2014-2016.

    • ⥣ Publications: Preprints | Conference Papers | Journal Papers | Other Manuscripts

    Preprints:

  • An Attack on InstaHide: Is Private Learning Possible with Instance Encoding?
    with Nicholas Carlini, Samuel Deng, Sanjam Garg, Somesh Jha, Saeed Mahloujifar, Shuang Song, Abhradeep Thakurta, and Florian Tramer.
    (Accepted to be presented at the Privacy Preserving Machine Learning workshop at NeurIPS 2020.)

  • Obliviousness Makes Poisoning Adversaries Weaker
    with Sanjam Garg, Somesh Jha, Saeed Mahloujifar, and Abhradeep Thakurta.
    (A related work presented at the Uncertainty & Robustness in Deep Learning workshop at ICML 2020.)

    • Conference Papers:

  • Black-Box Uselessness: Composable Separations in Cryptography.
    with Geoffroy Couteau and Pooya Farshim.
    Innovations in Theoretical Computer Science (ITCS) 2021. [recorded video] [live presentation with Q&A]

  • Lower Bounds for Adversarially Robust PAC Learning under Evasion and Hybrid Attacks.
    with Dimitrios I. Diochnos and Saeed Mahloujifar.
    IEEE InternationalConference On Machine Learning And Applications (ICMLA) 2020.
    (A related work also presented at Security and Privacy of Machine Learning workshop at ICML 2019, Safety and Robustness in Decision Making workshop at NeurIPS 2019, and International Symposium on Artificial Intelligence and Mathematics (ISAIM) 2020.)

  • Can Verifiable Delay Functions be Based on Random Oracles?
    with Caleb Smith and David J. Wu.
    International Colloquium on Automata, Languages and Programming (ICALP) 2020. [ePrint version] [video]
    (Also presented at the VDF Day, Stanford, Feb 2020; see here for the video.)

  • Adversarially Robust Learning Could Leverage Computational Hardness
    with Sanjam Garg, Somesh Jha, and Saeed Mahloujifar.
    Algorithmic Learning Theory (ALT) 2020.
    (Also presented at Security and Privacy of Machine Learning workshop at ICML 2019, as well as Safety and Robustness in Decision Making workshop at NeurIPS 2019.)

  • Computational Concentration of Measure: Optimal Bounds, Reductions, and More
    with Omid Etesami and Saeed Mahloujifar.
    ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020.

  • Empirically Measuring Concentration: Fundamental Limits on Intrinsic Robustness
    with Saeed Mahloujifar, Xiao Zhang, and David Evans.
    Conference on Neural Information Processing Systems (NeurIPS) 2019 (spotlight talk). [poster] [slides] [brief presentation]
    (Also presented at Safe Machine Learning and Debugging ML Models workshops at ICLR 2019, as well as Uncertainty & Robustness in Deep Learning workshop at ICML 2019.)

  • Universal Multi-Party Poisoning Attacks
    with Saeed Mahloujifar and Ameer Mohammed.
    International Conference on Machine Learning (ICML) 2019. [full version] [video of the talk by Saeed, starts at 1:09:00]
    (Also presented at Debugging ML Models workshop at ICLR 2019, as well as the Security and Privacy of Machine Learning workshop at ICML 2019.)

  • Registration-Based Encryption from Standard Assumptions
    with Sanjam Garg, Mohammad Hajiabadi, Ahmadreza Rahimi, and Sruthi Sekar.
    International Conference on Practice and Theory of Public Key Cryptography (PKC) 2019.

  • Can Adversarially Robust Learning Leverage Computational Hardness?
    with Saeed Mahloujifar.
    Algorithmic Learning Theory (ALT) 2019.

  • The Curse of Concentration in Robust Learning:
    Evasion and Poisoning Attacks from Concentration of Measure
    with Saeed Mahloujifar and Dimitrios I. Diochnos.
    AAAI Conference on Artificial Intelligence 2019.
    (Also presented at Workshop on Security in Machine Learning at NeurIPS 2018.)

  • Adversarial Risk and Robustness:
    General Definitions and Implications for the Uniform Distribution
    with Dimitrios I. Diochnos and Saeed Mahloujifar.
    Conference on Neural Information Processing Systems (NeurIPS) 2018. [poster] [brief presentation]

  • Registration-Based Encryption: Removing Private-Key Generator from IBE
    with Sanjam Garg, Mohammad Hajiabadi and Ahmadreza Rahimi.
    Theory of Cryptography Conference (TCC) 2018.

  • Limits on the Power of Garbling Techniques for Public-Key Encryption
    with Sanjam Garg, Mohammad Hajiabadi and Ameer Mohammed.
    International Cryptography Conference (CRYPTO) 2018.

  • On the Round Complexity of OT Extension
    with Sanjam Garg, Daniel Masny, and Izaak Meckler.
    International Cryptography Conference (CRYPTO) 2018.

  • Learning under p-Tampering Attacks
    with Saeed Mahloujifar and Dimitrios I. Diochnos.
    Algorithmic Learning Theory (ALT) 2018.
    (Also presented at International Symposium on Artificial Intelligence and Mathematics (ISAIM) 2018.)

  • Blockwise p-Tampering Attacks on Cryptographic Primitives, Extractors, and Learners
    with Saeed Mahloujifar.
    Theory of Cryptography Conference (TCC) 2017.

  • When Does Functional Encryption Imply Obfuscation?
    with Sanjam Garg and Ameer Mohammed.
    Theory of Cryptography Conference (TCC) 2017.

  • Lower Bounds on Obfuscation from All-or-Nothing Encryption Primitives
    with Sanjam Garg and Ameer Mohammed.
    International Cryptography Conference (CRYPTO) 2017. [full version]

  • On the Power of Hierarchical Identity-Based Encryption
    with Ameer Mohammed.
    Theory and Applications of Cryptographic Techniques (EUROCRYPT) 2016.

  • On the Impossibility of Virtual Black-Box Obfuscation in Idealized Models
    with Ameer Mohammed and Soheil Nematihaji.
    Theory of Cryptography Conference (TCC) 2016-A.

  • Lower Bounds on Assumptions behind Indistinguishability Obfuscation
    with Ameer Mohammed, Soheil Nematihaji, Rafael Pass, and abhi shelat.
    Theory of Cryptography Conference (TCC) 2016-A.

  • On the Impossibility of Cryptography with Tamperable Randomness
    with Per Austrin, Kai-Min Chung, Rafael Pass, and Karn Seth.
    International Cryptography Conference (CRYPTO) 2014. [full version]
    Invited to the Journal Algorithmica.

  • On the Power of Public-key Encryption in Secure Computation
    with Hemanta K. Maji and Manoj Prabhakaran.
    Theory of Cryptography Conference (TCC) 2014.

  • Can Optimally Fair Coin Tossing be Based on One-Way Functions?
    with Dana Dachman-Soled and Tal Malkin.
    Theory of Cryptography Conference (TCC) 2014.

  • Limits of Random Oracles in Secure Computation
    with Hemanta K. Maji and Manoj Prabhakaran.
    Innovations in Theoretical Computer Science (ITCS) 2014.

  • Languages with Efficient Zero-Knowledge PCPs are in SZK
    with David Xiao.
    Theory of Cryptography Conference (TCC) 2013.
    Invited to the TCC's 10-year anniversary special issue in Computational Complexity Journal.

  • On the Power of Nonuniformity in Proofs of Security
    with Kai-Min Chung, Huijia Lin, and Rafael Pass.
    Innovations in Theoretical Computer Science (ITCS) 2013.

  • Publicly Verifiable Proofs of Sequential Work
    with Tal Moran and Salil Vadhan.
    Innovations in Theoretical Computer Science (ITCS) 2013.

  • The Curious Case of Noninteractive Commitments:
    On the Power of Black-Box vs. Non-Black-Box Use of Primitives
    with Rafael Pass.
    International Cryptography Conference (CRYPTO) 2012. [full version] [video]

  • On Efficient Zero-Knowledge PCPs
    with Yuval Ishai and Amit Sahai.
    Theory of Cryptography Conference (TCC) 2012. [full version]
    Invited to the Journal of Cryptology.

  • On Black-Box Reductions between Predicate Encryption Schemes
    with Vipul Goyal, Virendra Kumar, and Satya Lokam.
    Theory of Cryptography Conference (TCC) 2012.

  • Time-Lock Puzzles in the Random Oracle Model
    with Tal Moran and Salil Vadhan.
    International Cryptography Conference (CRYPTO) 2011. [full version]

  • On Black-Box Complexity of Optimally-Fair Coin-Tossing
    with Dana Dachman-Soled, Yehuda Lindell, and Tal Malkin.
    Theory of Cryptography Conference (TCC) 2011.

  • Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography
    with Vipul Goyal, Yuval Ishai, and Amit Sahai.
    International Cryptography Conference (CRYPTO) 2010.

  • On the Power of Randomized Reductions and the Checkability of SAT
    with David Xiao
    Computational Complexity Conference (CCC) 2010.

  • A New Sampling Protocol and
    Applications to Basing Cryptographic Primitives on the Hardness of NP
    with Iftach Haitner and David Xiao
    Computational Complexity Conference (CCC) 2010.

  • Merkle Puzzles are Optimal —
    An O(n2)-Query Attack on Any Key Exchange from a Random Oracle
    with Boaz Barak
    International Cryptography Conference (CRYPTO) 2009. [conference video] [full version]
    Invited to the Journal of Cryptology.

  • Lower Bounds on Signatures from Symmetric Primitives
    with Boaz Barak
    Annual Symposium on Foundations of Computer Science (FOCS), 2007.

    • ↥ Journal Papers:

  • Learning under p-Tampering Poisoning Attacks
    with Saeed Mahloujifar and Dimitrios I. Diochnos.
    Annals of Mathematics and Artificial Intelligence, Vol. 88, pp. 759--792, 2020

  • On the Impossibility of Cryptography with Tamperable Randomness
    with Per Austrin, Kai-Min Chung, Rafael Pass, and Karn Seth.
    Algorithmica, Vol. 79.4, pp. 1052--1101, 2017. [full version]

  • Merkle's Key Agreement Protocol is Optimal:
    An O(n2)-Query Attack on Any Key Exchange from a Random Oracle
    with Boaz Barak
    Journal of Cryptology, Vol. 30.3, pp. 699--734, 2017. [full version]

  • Load Sensitive Topology Control:
    Towards Minimum Energy Consumption in Dense Ad Hoc Sensor Networks
    with A. Nayyeri, S. Zarifzadeh, and N. Yazdani
    Computer Networks, Vol. 52, pp. 493--513, 2008.

  • On Rainbow Cycles in Edge Colored Complete Graphs
    with S. Akbari, O. Etesami, and H. Mahini
    Australasian Journal of Combinatorics, Vol. 37, pp. 33--42, 2007.

  • Transversals in Long Rectangular Arrays
    with S. Akbari, O. Etesami, H. Mahini, and A. Sharifi
    Discrete Mathematics, Vol. 306, pp. 3011--3013, 2006.

    • ↥ Other Manuscripts:

  • A Note on Black-Box Separations for Indistinguishability Obfuscation
    with Ameer Mohammed, Soheil Nematihaji, Rafael Pass, and abhi shelat.

  • Black Boxes, Incorporated (a survey)
    with Avi Wigderson.

  • Unprovable Security of Two-Message Zero Knowledge
    with Kai-Min Chung, Edward Lui, and Rafael Pass.

  • Optimizing Trees for Static Searchable Encryption
    with Mohammad Etemad and David Evans.

  • Studies in the Efficiency and (versus) Security of Cryptographic Tasks
    Ph.D. Thesis, Princeton University, 2010. [local copy]

    • ⥣ Service:

    Program Committees:

  • International Cryptology Conference (CRYPTO) 2020
  • Topics in Theoretical Computer Science (TTCS) 2020
  • Theory of Cryptography Conference (TCC) 2019
  • Theory and Applications of Cryptographic Techniques (EUROCRYPT) 2019
  • Theory and Applications of Cryptographic Techniques (EUROCRYPT) 2018
  • ACM Conference on Computer and Communications Security (CCS) 2017
  • International Cryptology Conference (CRYPTO) 2017
  • Topics in Theoretical Computer Science (TTCS) 2017
  • Theory of Cryptography Conference (TCC) 2015
  • Topics in Theoretical Computer Science (TTCS) 2015
  • Theory of Cryptography Conference (TCC) 2014
  • Theory of Cryptography Conference (TCC) 2013
  • Theory of Cryptography Conference (TCC) 2011

    • Organized Events/Workshops:

  • Organizing (together with Pooya Farshim, Iftach Haitner, Yuval Ishai)
    the workshop "Lower Bounds in Cryptography" Bertinoro, Italy, July 2019.

  • Helped organize Cyberwars at UVA, A GenCyber Camp, June 2018.

  • Helped organize DC-area crypto days (going on since Sept 2014).

    • ⥣ Selected (Recent) Talks:

    (See my CV for a more complete list.)

  • Connections between cryptographic coin flipping and adversarially robust learning.
    Privacy-Preserving Machine Learning Workshop at Crypto, August 2020. [video]

  • (Im)possibility of (forms of) VDFs in the Random Oracle Mode.
    VDF Day, Stanford, Feb 2020. [video]

  • Computational concentration of measure.
    Theory Seminar, Computer Science Department, UC Berkeley, Oct 2019.

  • Coin-tossing attacks, concentration of products, and robust learning.
    Lower Bounds in Cryptography Workshop, Bertinoro, Italy, July 2019. [video]

  • Coin-tossing attacks, computational concentration of products, and limits of robust learning.
    Theory Seminar, Computer Science Department, University of Washington, April 2019.

  • Registration-Based Encryption.
    DC Area Crypto Day, National Institute of Standards and Technology (NIST), April 2019.

  • Coin Tossing, Concentration of Products, and Limits of Robust Learning.
    Charles River Crypto Day, MIT, March 2019.

  • Learning under p-Tampering Attacks.
    DC-Area Anonymity, Privacy, and Security Seminar, George Mason University, February 2018.

  • Blockwise p-Tampering Attacks on Cryptographic Primitives, Extractors, and Learners.
    Bay Area Crypto Day, Berkeley, November 2017.

  • Black-box and Non-black-box Lower Bounds on Assumptions behind IO.
    DIMACS Workshop on Complexity of Crypto Primitives and Assumptions, City College of New York, June 2017. [video]

  • Lower bounds on Indistinguishability Obfuscation from All-or-Nothing Encryption.
    Theory Seminar, Computer Science Department, Johns Hopkins University, March 2017.

  • Lower Bounds on Indistinguishability Obfuscation.
    DIMACS/CEF Workshop on Cryptography and Software Obfuscation, Stanford, Nov 2016. [video]

  • Lower Bounds on VBB and Indistinguishability Obfuscations in Idealized Models.
    Cryptography Reunion Workshop, Simons Institute, Berkeley, August 2016.

  • Assumptions in Cryptography: How Do Cryptographers Sleep Well?
    TEDx UVA, University of Virginia, Feb 2015. [video]

  • On the (Im)Possibility of Cryptography with Tamperable Randomness
    New York Crypto Day, Cornell Tech, Nov 2014.

  • Program Checkers for NP and Black-box separations (tutorial)
    Summer School on Black-Box Impossibility Results, Bertinoro Italy, July 2014.