Mark Zhandry

I am currently a Senior Scientist at NTT Research in the Cryptography & Information Security Lab. I will be joining the faculty at Stanford University starting Fall 2025, and was previously an Assistant Professor of Computer Science at Princeton University. My research focus is on cryptography and quantum computing, although I am broadly interested in all aspects of computer science theory.

I completed a postdoc at MIT, my PhD at Stanford University, and my bachelor's degree with Highest Honors at UC Berkeley. I am a recipient of the NSF CAREER Award, the Sloan Research Fellowship, and three Best Paper Awards.

Research Interests

Our construction of a search problem that is easy for quantum computers, but hard for classical computers. Unlike other known demonstrations of "Quantum Advantage" that require tools from number theory and public key cryptography, our search problem can be instantiated from any cryptographic hash function whose outputs are sufficiently "random looking." See .	Quantum Quantum computers — harnessing the strange features of quantum mechanics such as superpositions, entanglement, etc. — promise to revolutionize computer science. As the operation of quantum computers is fundamentally different than classical computation, we need to re-evaluate our long-established understanding of what computers can and cannot do. The situation is particularly urgent for cryptography, where we need to develop new systems to protect against quantum computers' enhanced computational power. On the other hand, quantum computers offer solutions to never-before-possible tasks, such as certifying random strings, validating the deletion of data, programs that cannot be copied, and more.
Our construction for obfuscating conjuctions. Assuming the conjunction is sampled from a sufficiently random distribution, we prove security under the LPN assumption. Along the way, we prove a partial converse to a theorem of Arora and Ge, showing that LPN remains hard under structured noise when the number of samples is small. See .	Obfuscation Can you hide secrets in software? For decades, attempts at obfuscation applied code transformations such as inserting dummy operations or re-naming variables. These transformations make extracting secrets harder, but not impossible. A new, stronger form of obfuscation has emerged, however, that applies mathematical transformations to software, and has the potential to make extracting secrets effectively impossible. Obfuscation has numerous connections to cryptography and computer science generally.
A diagram of the Augmented Random Oracle Model (AROM). The AROM is designed to capture known uninstantiability results that apply to idealized models, in particular the random oracle model (ROM). Such uninstantiability results take the form of protocols that are secure in the ROM but insecure when the random oracle is replaced with any concrete function. The AROM augments the random oracle in a way so as to make such protocols insecure even in the idealized model. As such, a proof of security in the AROM indicates resilience to known uninstantiabilities. See .	Idealized Models Many of the most practical cryptosystems lack a full security proof in the standard model. Nevertheless, we can gain confidence in their security by heuristically treating one or more of the building blocks as an "ideal" object implemented as an oracle. Prominent examples include random oracles, ideal ciphers, generic groups, etc. Proofs in idealized models are often very different from standard crypto proofs, requiring both reductions and query complexity arguments.
The general structure of an Affine Determinant Program (ADP): the program is specified by a collection of matrices. To evaluate the program on input x, first compute the linear combination of matrices, where the coefficients are the input bits. Then take the determinant. We give candidate obfuscators for such programs, which can be lifted to obfuscators for general programs using known techniques. We use this obfuscator to construct public key encryption with very fast key generation. See .	Crypto Math Intractable mathematical problems are the heart of modern cryptography. Unfortunately, until someone proves that P≠NP, the intractability of such problems cannot be proven unconditionally and can only be conjectured. Then how do we discover novel mathematical structures, figure out how to use them, and gain confidence in their security? Through extensive study, development of new applications, attacks, and mitigations.
A representation of our traitor tracing algorithm built on top of threshold broadcast encryption. This tracing algorithm plays a crucial role in constructing the first traitor tracing scheme from pairings with O(N^1/3) sized parameters, overcoming a quadratic barrier that had stood for almost 15 years. See .	Watermarking Software watermarking protects against software piracy by embedding a "mark" into a program that cannot be removed without destroying the functionality of the program. A prominent example is traitor tracing, where the program being marked is a decryption functionality. There are a number of fundamental questions in watermarking/traitor tracing: achieving security against colluding users, attaining the shortest possible paramater sizes, embedding arbitrary information into the mark, ensuring honest users' embedded information remains private, and maintaining security in the presence of quantum adversaries, to name a few.
The smallest tournament graph in which every pair of nodes has at least one common ancestor. Erdős and Sós consider the general problem of constructing tournament graphs where every n nodes have a common ancestor, giving an exponential lower bound for such graphs. This lower bound plays a crucial role in our impossibility results for constructing order-revealing encryption. See .	Black-Box Impossibilities Can public key encryption be built from one-way functions? Is it just a matter of time before the community solves this problem, or are this problem and others like it actually impossible? This question is addressed by black box impossibilities, which show, relative to certain techniques, that such a result is indeed impossible. Black box impossibilities help guide protocol design by showing which techniques won't work. The proofs of such impossibilities can draw on interesting mathematical tools from linear algebra, graph theory, are more.
The leakage profile in our construction of practical order revealing encryption (ORE). Like all known practical ORE schemes, our scheme leaks more than just the order of plaintexts. Unlike other leakage profiles, however, this leakage is invariant under multiplying all plaintexts by 2. With some additional processing, this allows us to construct parameter-hiding ORE, which hides the scale and shift of the underlying plaintext distribution. Parameter hiding is the only known semantically meaningful privacy notion achieved by practical ORE schemes. See .	Property Preserving Encryption Property Preserving Encryption (PPE) deliberately preserves certain relations on the plaintext data (e.g. equalities in the case of deterministic encryption, or order in the case of order revealing encryption). In addition to applications such as encrypted databases, PPE also has other interesting connections, such as security under bad randomness and differential privacy. The question is then: how to reveal such information without revealing other sensitive data, and what security, if any, remains.
Our commitment to a bit b. By streaming the bits of our commitment in the correct order, the commitment can be computed and read in very low space, and remains secure as long as the adversary's storage is somewhat smaller than the total length of the commitment. Prior commitments in the bounded storage model were rather complicated and required 5 messages. In contrast, our protocol is extremely simple and only requires a single message. See .	Bounded Storage Model Cryptography typically models adversaries as time-bounded, but what about adversaries that are space-bounded? The space-bounded model allows for unconditional and everlasting protocols, sometimes far simpler than their time-bounded counterparts. If we bound time and space, we can also achieve never-before-possible functionalities, such as ciphertexts that effectively disappear after transmission.