Intractible 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, devising new applications, attacks, and mitigations. 
Iterated Inhomogeneous Polynomials


Let p be a polynomial, and let p^{(i)}(x) be the result of iterating the
polynomial i times, starting at an input x. The case where p(x) is the homogeneous
polynomial x^{2} has been extensively studied in cryptography. Due to its associated
group structure, iterating this polynomial gives rise to a number of interesting
cryptographic applications such as timelock puzzles and verifiable delay functions.
On the other hand, the associated group structure leads to quantum attacks on the
applications.
In this work, we consider whether inhomogeneous polynomials, such as 2x^{2}+3x+1, can have useful cryptographic applications. We focus on the case of polynomials mod 2^^{n}, due to some useful mathematical properties. The natural group structure no longer exists, so the quantum attacks but also applications no longer immediately apply. We nevertheless show classical polynomialtime attacks on analogs of hard problems from the homogeneous setting. We conclude by proposing new computational assumptions relating to these inhomogeneous polynomials, with cryptographic applications.
@misc{EPRINT:GuaZha21,
author = {Jiaxin Guan and Mark Zhandry}, howpublished = {Cryptology ePrint Archive, Report 2021/1399}, note = {\url{https://eprint.iacr.org/2021/1399}}, title = {Iterated Inhomogeneous Polynomials}, year = {2021} }  
Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption


An affine determinant program ADP: {0,1}^{n} → {0,1} is specified
by a tuple (A,B_{1},…,B_{n}) of square matrices over
F_{q} and a function Eval: F_{q} → {0,1}, and is evaluated on x
∈ {0,1}^{n} by computing Eval(det(A + ∑ x_{i}B_{i})).
In this work, we suggest ADPs as a new framework for building generalpurpose obfuscation and witness encryption. We provide evidence to suggest that constructions following our ADPbased framework may one day yield secure, practically feasible obfuscation. As a proofofconcept, we give a candidate ADPbased construction of indistinguishability obfuscation for all circuits along with a simple witness encryption candidate. We provide cryptanalysis demonstrating that our schemes resist several potential attacks, and leave further cryptanalysis to future work. Lastly, we explore practically feasible applications of our witness encryption candidate, such as publickey encryption with nearoptimal key generation.
@inproceedings{ITCS:BIJMSZ20,
author = {James Bartusek and Yuval Ishai and Aayush Jain and Fermi Ma and Amit Sahai and Mark Zhandry}, booktitle = {ITCS 2020}, editor = {Thomas Vidick}, month = jan, pages = {82:182:39}, publisher = {{LIPIcs}}, title = {Affine Determinant Programs: {A} Framework for Obfuscation and Witness Encryption}, volume = {151}, year = {2020} }  
Preventing Zeroizing Attacks on GGH15


The GGH15 multilinear maps have served as the foundation for a number of cuttingedge
cryptographic proposals. Unfortunately, many schemes built on GGH15 have been
explicitly broken by socalled "zeroizing attacks," which exploit leakage from honest
zerotest queries. The precise settings in which zeroizing attacks are possible have
remained unclear. Most notably, none of the current indistinguishability obfuscation
(iO) candidates from GGH15 have any formal security guarantees against zeroizing
attacks.
In this work, we demonstrate that all known zeroizing attacks on GGH15 implicitly construct algebraic relations between the results of zerotesting and the encoded plaintext elements. We then propose a "GGH15 zeroizing model" as a new general framework which greatly generalizes known attacks. Our second contribution is to describe a new GGH15 variant, which we formally analyze in our GGH15 zeroizing model. We then construct a new iO candidate using our multilinear map, which we prove secure in the GGH15 zeroizing model. This implies resistance to all known zeroizing strategies. The proof relies on the Branching Program UnAnnihilatability (BPUA) Assumption of Garg et al. [TCC 16B] (which is implied by PRFs in NC^1 secure against P/Poly) and the complexitytheoretic pBounded Speedup Hypothesis of Miles et al. [ePrint 14] (a strengthening of the Exponential Time Hypothesis).
@inproceedings{TCC:BGMZ18,
author = {James Bartusek and Jiaxin Guan and Fermi Ma and Mark Zhandry}, booktitle = {TCC~2018, Part~II}, editor = {Amos Beimel and Stefan Dziembowski}, month = nov, pages = {544574}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Return of {GGH15}: Provable Security Against Zeroizing Attacks}, volume = {11240}, year = {2018} }  
The MMap Strikes Back: Obfuscation and New Multilinear Maps Immune to CLT13 Zeroizing Attacks


We devise the first weak multilinear map model for CLT13 multilinear maps (Coron et
al., CRYPTO 2013) that captures all known classical polynomialtime attacks on the
maps. We then show important applications of our model. First, we show that in our
model, several existing obfuscation and orderrevealing encryption schemes, when
instantiated with CLT13 maps, are secure against known attacks under a mild algebraic
complexity assumption used in prior work. These are schemes that are actually being
implemented for experimentation. However, until our work, they had no rigorous
justification for security.
Next, we turn to building constant degree multilinear maps on top of CLT13 for which there are no known attacks. Precisely, we prove that our scheme achieves the ideal security notion for multilinear maps in our weak CLT13 model, under a much stronger variant of the algebraic complexity assumption used above. Our multilinear maps do not achieve the full functionality of multilinear maps as envisioned by Boneh and Silverberg (Contemporary Mathematics, 2003), but do allow for rerandomization and for encoding arbitrary plaintext elements.
@inproceedings{TCC:MaZha18,
author = {Fermi Ma and Mark Zhandry}, booktitle = {TCC~2018, Part~II}, editor = {Amos Beimel and Stefan Dziembowski}, month = nov, pages = {513543}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {The {MMap} Strikes Back: Obfuscation and New Multilinear Maps Immune to {CLT13} Zeroizing Attacks}, volume = {11240}, year = {2018} }  
Multiparty NonInteractive Key Exchange and More From Isogenies on Elliptic Curves


We describe a framework for constructing an efficient noninteractive key exchange
(NIKE) protocol for n parties for any n≥2. Our approach is based on the problem of
computing isogenies between isogenous elliptic curves, which is believed to be
difficult. We do not obtain a working protocol because of a missing step that is
currently an open problem. What we need to complete our protocol is an efficient
algorithm that takes as input an abelian variety presented as a product of isogenous
elliptic curves, and outputs an isomorphism invariant of the abelian variety.
Our framework builds a cryptographic invariant map, which is a new primitive closely related to a cryptographic multilinear map, but whose range does not necessarily have a group structure. Nevertheless, we show that a cryptographic invariant map can be used to build several cryptographic primitives, including NIKE, that were previously constructed from multilinear maps and indistinguishability obfuscation.
@article{Boneh2018MultipartyNK,
title = {Multiparty NonInteractive Key Exchange and More From Isogenies on Elliptic Curves}, author = {Dan Boneh and Darren B. Glass and Daniel Krashen and Kristin E. Lauter and Shahed Sharif and Alice Silverberg and Mehdi Tibouchi and Mark Zhandry}, journal = {Journal of Mathematical Cryptology}, year = {2018}, volume = {14}, pages = {5  14} }  
Secure Obfuscation in a Weak Multilinear Map Model


All known candidate indistinguishibility obfuscation (iO) schemes rely on candidate
multilinear maps. Until recently, the strongest proofs of security available for iO
candidates were in a generic model that only allows "honest" use of the multilinear
map. Most notably, in this model the zerotest procedure only reveals whether an
encoded element is 0, and nothing more.
However, this model is inadequate: there have been several attacks on multilinear maps that exploit extra information revealed by the zerotest procedure. In particular, Miles, Sahai and Zhandry [Crypto'16] recently gave a polynomialtime attack on several iO candidates when instantiated with the multilinear maps of Garg, Gentry, and Halevi [Eurocrypt'13], and also proposed a new "weak multilinear map model" that captures all known polynomialtime attacks on GGH13. In this work, we give a new iO candidate which can be seen as a small modification or generalization of the original candidate of Garg, Gentry, Halevi, Raykova, Sahai, and Waters [FOCS'13]. We prove its security in the weak multilinear map model, thus giving the first iO candidate that is provably secure against all known polynomialtime attacks on GGH13. The proof of security relies on a new assumption about the hardness of computing annihilating polynomials, and we show that this assumption is implied by the existence of pseudorandom functions in NC^{1}.
@inproceedings{TCC:GMMSSZ16,
author = {Sanjam Garg and Eric Miles and Pratyay Mukherjee and Amit Sahai and Akshayaram Srinivasan and Mark Zhandry}, booktitle = {TCC~2016B, Part~II}, editor = {Martin Hirt and Adam D. Smith}, month = oct # {~/~} # nov, pages = {241268}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Secure Obfuscation in a Weak Multilinear Map Model}, volume = {9986}, year = {2016} }  
Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13


In this work, we put forward a new class of polynomialtime attacks on the original
multilinear maps of Garg, Gentry, and Halevi (2013). Previous polynomialtime attacks
on GGH13 were "zeroizing" attacks that generally required the availability of
lowlevel encodings of zero. Most significantly, such zeroizing attacks were not
applicable to candidate indistinguishability obfuscation (iO) schemes. iO has been the
subject of intense study.
To address this gap, we introduce annihilation attacks, which attack multilinear maps using nonlinear polynomials. Annihilation attacks can work in situations where there are no lowlevel encodings of zero. Using annihilation attacks, we give the first polynomialtime cryptanalysis of candidate iO schemes over GGH13. More specifically, we exhibit two simple programs that are functionally equivalent, and show how to efficiently distinguish between the obfuscations of these two programs. Given the enormous applicability of iO, it is important to devise iO schemes that can avoid attack.
@inproceedings{C:MilSahZha16,
author = {Eric Miles and Amit Sahai and Mark Zhandry}, booktitle = {CRYPTO~2016, Part~II}, editor = {Matthew Robshaw and Jonathan Katz}, month = aug, pages = {629658}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over {GGH13}}, volume = {9815}, year = {2016} }  
PostZeroizing Obfuscation: New Mathematical Tools, and the Case of Evasive Circuits


Recent devastating attacks by Cheon et al.~[Eurocrypt'15] and others have highlighted
significant gaps in our intuition about security in candidate multilinear map schemes,
and in candidate obfuscators that use them. The new attacks, and some that were
previously known, are typically called "zeroizing" attacks because they all crucially
rely on the ability of the adversary to create encodings of 0.
In this work, we initiate the study of postzeroizing obfuscation, and we present a construction for the special case of evasive functions. We show that our obfuscator survives all known attacks on the underlying multilinear maps, by proving that no encodings of 0 can be created by a genericmodel adversary. Previous obfuscators (for both evasive and general functions) were either analyzed in a lessconservative "prezeroizing" model that does not capture recent attacks, or were proved secure relative to assumptions that are now known to be false. To prove security, we introduce a new technique for analyzing polynomials over multilinear map encodings. This technique shows that the types of encodings an adversary can create are much more restricted than was previously known, and is a crucial step toward achieving postzeroizing security. We also believe the technique is of independent interest, as it yields efficiency improvements for existing schemes.
@inproceedings{EC:BMSZ16,
author = {Saikrishna Badrinarayanan and Eric Miles and Amit Sahai and Mark Zhandry}, booktitle = {EUROCRYPT~2016, Part~II}, editor = {Marc Fischlin and JeanS{\'{e}}bastien Coron}, month = may, pages = {764791}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Postzeroizing Obfuscation: New Mathematical Tools, and the Case of Evasive Circuits}, volume = {9666}, year = {2016} }  
Functional Encryption without Obfuscation


Previously known functional encryption (FE) schemes for general circuits relied on
indistinguishability obfuscation, which in turn either relies on an exponential number
of assumptions (basically, one per circuit), or a polynomial set of assumptions, but
with an exponential loss in the security reduction. Additionally these schemes are
proved in an unrealistic selective security model, where the adversary is forced to
specify its target before seeing the public parameters. For these constructions, full
security can be obtained but at the cost of an exponential loss in the security
reduction.
In this work, we overcome the above limitations and realize a fully secure functional encryption scheme without using indistinguishability obfuscation. Specifically the security of our scheme relies only on the polynomial hardness of simple assumptions on multilinear maps.
@inproceedings{TCC:GGHZ16,
author = {Sanjam Garg and Craig Gentry and Shai Halevi and Mark Zhandry}, booktitle = {TCC~2016A, Part~II}, editor = {Eyal Kushilevitz and Tal Malkin}, month = jan, pages = {480511}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Functional Encryption Without Obfuscation}, volume = {9563}, year = {2016} }  
How to Avoid Obfuscation Using Witness PRFs


We propose a new cryptographic primitive called witness pseudorandom functions
(witness PRFs). Witness PRFs are related to witness encryption, but appear strictly
stronger: we show that witness PRFs can be used for applications such as multiparty
key exchange without trsuted setup, polynomiallymany hardcore bits for any oneway
function, and several others that were previously only possible using obfuscation.
Current candidate obfuscators are far from practical and typically rely on unnatural
hardness assumptions about multilinear maps. We give a construction of witness PRFs
from multilinear maps that is simpler and much more efficient than current obfuscation
candidates, thus bringing several applications of obfuscation closer to practice. Our
construction relies on new but very natural hardness assumptions about the underlying
maps that appear to be resistant to a recent line of attacks.
@inproceedings{TCC:Zhandry16,
author = {Mark Zhandry}, booktitle = {TCC~2016A, Part~II}, editor = {Eyal Kushilevitz and Tal Malkin}, month = jan, pages = {421448}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {How to Avoid Obfuscation Using Witness {PRFs}}, volume = {9563}, year = {2016} }  
Semantically Secure OrderRevealing Encryption: MultiInput Functional Encryption Without Obfuscation


Deciding "greaterthan" relations among data items just given their encryptions is at
the heart of search algorithms on encrypted data, most notably, noninteractive binary
search on encrypted data. Orderpreserving encryption provides one solution, but
provably provides only limited security guarantees. Twoinput functional encryption is
another approach, but requires the full power of obfuscation machinery and is
currently not implementable.
We construct the first implementable encryption system supporting greaterthan comparisons on encrypted data that provides the "bestpossible" semantic security. In our scheme there is a public algorithm that given two ciphertexts as input, reveals the order of the corresponding plaintexts and nothing else. Our constructions are inspired by obfuscation techniques, but do not use obfuscation. For example, to compare two 16bit encrypted values (e.g., salaries or age) we only need a 9way multilinear map. More generally, comparing kbit values requires only a (k/2+1)way multilinear map. The required degree of multilinearity can be further reduced, but at the cost of increasing ciphertext size. Beyond comparisons, our results give an implementable secretkey multiinput functional encryption scheme for functionalities that can be expressed as (generalized) branching programs of polynomial length and width. Comparisons are a special case of this class, where for kbit inputs the branching program is of length k+1 and width 4.
@inproceedings{EC:BLRSZZ15,
author = {Dan Boneh and Kevin Lewi and Mariana Raykova and Amit Sahai and Mark Zhandry and Joe Zimmerman}, booktitle = {EUROCRYPT~2015, Part~II}, editor = {Elisabeth Oswald and Marc Fischlin}, month = apr, pages = {563594}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Semantically Secure OrderRevealing Encryption: Multiinput Functional Encryption Without Obfuscation}, volume = {9057}, year = {2015} }  
Adaptively Secure Broadcast Encryption with Small System Parameters


We build the first publickey broadcast encryption systems that simultaneously achieve
adaptive security against arbitrary number of colluders, have small system parameters,
and have security proofs that do not rely on knowledge assumptions or complexity
leveraging. Our schemes are built from either composite order multilinear maps or
obfuscation and enjoy a ciphertext overhead, private key size, and public key size
that are all polylogarithmic in the total number of users. Previous broadcast
schemes with similar parameters are either proven secure in a weaker static model, or
rely on nonfalsifiable knowledge assumptions.
@misc{EPRINT:Zhandry14b,
author = {Mark Zhandry}, howpublished = {Cryptology ePrint Archive, Report 2014/757}, note = {\url{https://eprint.iacr.org/2014/757}}, title = {Adaptively Secure Broadcast Encryption with Small System Parameters}, year = {2014} }  
Low Overhead Broadcast Encryption from Multilinear Maps


We use multilinear maps to provide a solution to the longstanding problem of
publickey broadcast encryption where all parameters in the system are small. In our
constructions, ciphertext overhead, private key size, and public key size are all
polylogarithmic in the total number of users. The systems are fully
collusionresistant against any number of colluders. All our systems are based on an
O(log N)way multilinear map to support a broadcast system for N users. We present
three constructions based on different types of multilinear maps and providing
different security guarantees. Our systems naturally give identitybased broadcast
systems with short parameters.
@inproceedings{C:BonWatZha14,
author = {Dan Boneh and Brent Waters and Mark Zhandry}, booktitle = {CRYPTO~2014, Part~I}, editor = {Juan A. Garay and Rosario Gennaro}, month = aug, pages = {206223}, publisher = {Springer, Heidelberg}, series = {{LNCS}}, title = {Low Overhead Broadcast Encryption from Multilinear Maps}, volume = {8616}, year = {2014} }  
Fully Secure Attribute Based Encryption from Multilinear Maps


We construct the first fully secure attribute based encryption (ABE) scheme that can
handle access control policies expressible as polynomialsize circuits. Previous ABE
schemes for general circuits were proved secure only in an unrealistic selective
security model, where the adversary is forced to specify its target before seeing the
public parameters, and full security could be obtained only by complexity leveraging,
where the reduction succeeds only if correctly guesses the adversary's target string
x*, incurring a 2^{x*} loss factor in the tightness of the reduction.
At a very high level, our basic ABE scheme is reminiscent of Yao's garbled circuits, with 4 gadgets per gate of the circuit, but where the decrypter in our scheme puts together the appropriate subset of gate gadgets like puzzle pieces by using a cryptographic multilinear map to multiply the pieces together. We use a novel twist of Waters' dual encryption methodology to prove the full security of our scheme. Most importantly, we show how to preserve the delicate informationtheoretic argument at the heart of Waters'dual system by enfolding it in an informationtheoretic argument similar to that used in Yao's garbled circuits.
@misc{EPRINT:GGHZ14,
author = {Sanjam Garg and Craig Gentry and Shai Halevi and Mark Zhandry}, howpublished = {Cryptology ePrint Archive, Report 2014/622}, note = {\url{https://eprint.iacr.org/2014/622}}, title = {Fully Secure Attribute Based Encryption from Multilinear Maps}, year = {2014} } 