Mohammad Mahmoody



CV | Teaching | Advising | Publications | Service | Talks


I am an assistant 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.


Curriculum Vitae:

Here is my CV from April 2019.
An extended version with more details could be found here.
Also, here you can find my Research Statement (from August 2018).


Teaching:

  • 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 (jointly advised with Sanjam Garg).
  • Dimitris Diochnos Postdoc.
  • Saeed Mahloujifar PhD.
  • Ahmadreza Rahimi PhD.
  • Caleb Smith PhD.
  • Ameer Mohammed PhD (2013-2018 - now, assistant professor at Kuwait University).
  • Saba Eskandarian Masters (2015-2016 - now, PhD student at Stanford).
  • Soheil Nematihaji Masters (2014-2016).


  • Publications: Conference Papers | Journal Papers | Other Manuscripts

    Refereed Conference Papers:

  • Universal Multi-party Poisoning Attacks
    with Saeed Mahloujifar and Ameer Mohammed.
    (to appear in) International Conference on Machine Learning (ICML) 2019.
  • Registration-Based Encryption from Standard Assumptions
    International Conference on Practice and Theory of Public Key Cryptography (PKC) 2019.
    with Sanjam Garg, Mohammad Hajiabadi, Ahmadreza Rahimi, and Sruthi Sekar.
  • Can Adversarially Robust Learning Leverage Computational Hardness?
    Algorithmic Learning Theory (ALT) 2019.
    with Saeed Mahloujifar.
  • 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.
  • 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] [short video]
  • 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.
  • 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. [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:

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

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

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