Let p be a polynomial, and let p⁽ⁱ⁾(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² 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 time-lock 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²+3x+1, can have useful cryptographic applications. We focus on the case of polynomials mod 2^ⁿ, 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 polynomial-time 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}
}

An affine determinant program ADP: {0,1}ⁿ → {0,1} is specified by a tuple (A,B₁,…,B_n) of square matrices over F_q and a function Eval: F_q → {0,1}, and is evaluated on x ∈ {0,1}ⁿ by computing Eval(det(A + ∑ x_iB_i)).

In this work, we suggest ADPs as a new framework for building general-purpose obfuscation and witness encryption. We provide evidence to suggest that constructions following our ADP-based framework may one day yield secure, practically feasible obfuscation.

As a proof-of-concept, we give a candidate ADP-based 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 public-key encryption with near-optimal 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:1--82:39},
    publisher =     {{LIPIcs}},
    title =         {Affine Determinant Programs: {A} Framework for
                     Obfuscation and Witness Encryption},
    volume =        {151},
    year =          {2020}
}

The GGH15 multilinear maps have served as the foundation for a number of cutting-edge cryptographic proposals. Unfortunately, many schemes built on GGH15 have been explicitly broken by so-called "zeroizing attacks," which exploit leakage from honest zero-test 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 zero-testing 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 Un-Annihilatability (BPUA) Assumption of Garg et al. [TCC 16-B] (which is implied by PRFs in NC^1 secure against P/Poly) and the complexity-theoretic p-Bounded 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 =         {544--574},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Return of {GGH15}: Provable Security Against
                     Zeroizing Attacks},
    volume =        {11240},
    year =          {2018}
}

We devise the first weak multilinear map model for CLT13 multilinear maps (Coron et al., CRYPTO 2013) that captures all known classical polynomial-time attacks on the maps. We then show important applications of our model. First, we show that in our model, several existing obfuscation and order-revealing 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 re-randomization 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 =         {513--543},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {The {MMap} Strikes Back: Obfuscation and New
                     Multilinear Maps Immune to {CLT13} Zeroizing Attacks},
    volume =        {11240},
    year =          {2018}
}

We describe a framework for constructing an efficient non-interactive 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 Non-Interactive 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}
}

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 zero-test 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 zero-test procedure. In particular, Miles, Sahai and Zhandry [Crypto'16] recently gave a polynomial-time 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 polynomial-time 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 polynomial-time 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¹.

@inproceedings{TCC:GMMSSZ16,
    author =        {Sanjam Garg and Eric Miles and Pratyay Mukherjee and
                     Amit Sahai and Akshayaram Srinivasan and
                     Mark Zhandry},
    booktitle =     {TCC~2016-B, Part~II},
    editor =        {Martin Hirt and Adam D. Smith},
    month =         oct # {~/~} # nov,
    pages =         {241--268},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Secure Obfuscation in a Weak Multilinear Map Model},
    volume =        {9986},
    year =          {2016}
}

In this work, we put forward a new class of polynomial-time attacks on the original multilinear maps of Garg, Gentry, and Halevi (2013). Previous polynomial-time attacks on GGH13 were "zeroizing" attacks that generally required the availability of low-level 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 non-linear polynomials. Annihilation attacks can work in situations where there are no low-level encodings of zero. Using annihilation attacks, we give the first polynomial-time 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 =         {629--658},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Annihilation Attacks for Multilinear Maps: Cryptanalysis 
                     of Indistinguishability Obfuscation over {GGH13}},
    volume =        {9815},
    year =          {2016}
}

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 post-zeroizing 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 generic-model adversary. Previous obfuscators (for both evasive and general functions) were either analyzed in a less-conservative "pre-zeroizing" 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 post-zeroizing 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 Jean-S{\'{e}}bastien Coron},
    month =         may,
    pages =         {764--791},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Post-zeroizing Obfuscation: New Mathematical Tools,
                     and the Case of Evasive Circuits},
    volume =        {9666},
    year =          {2016}
}

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~2016-A, Part~II},
    editor =        {Eyal Kushilevitz and Tal Malkin},
    month =         jan,
    pages =         {480--511},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Functional Encryption Without Obfuscation},
    volume =        {9563},
    year =          {2016}
}

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 multi-party key exchange without trsuted setup, polynomially-many hardcore bits for any one-way 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~2016-A, Part~II},
    editor =        {Eyal Kushilevitz and Tal Malkin},
    month =         jan,
    pages =         {421--448},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {How to Avoid Obfuscation Using Witness {PRFs}},
    volume =        {9563},
    year =          {2016}
}

Deciding "greater-than" relations among data items just given their encryptions is at the heart of search algorithms on encrypted data, most notably, non-interactive binary search on encrypted data. Order-preserving encryption provides one solution, but provably provides only limited security guarantees. Two-input 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 greater-than comparisons on encrypted data that provides the "best-possible" 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 16-bit encrypted values (e.g., salaries or age) we only need a 9-way multilinear map. More generally, comparing k-bit 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 secret-key multi-input 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 k-bit 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 =         {563--594},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Semantically Secure Order-Revealing Encryption:
                     Multi-input Functional Encryption Without Obfuscation},
    volume =        {9057},
    year =          {2015}
}

We build the first public-key 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 poly-logarithmic in the total number of users. Previous broadcast schemes with similar parameters are either proven secure in a weaker static model, or rely on non-falsifiable 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}
}

We use multilinear maps to provide a solution to the long-standing problem of public-key broadcast encryption where all parameters in the system are small. In our constructions, ciphertext overhead, private key size, and public key size are all poly-logarithmic in the total number of users. The systems are fully collusion-resistant 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 identity-based 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 =         {206--223},
    publisher =     {Springer, Heidelberg},
    series =        {{LNCS}},
    title =         {Low Overhead Broadcast Encryption from Multilinear Maps},
    volume =        {8616},
    year =          {2014}
}

We construct the first fully secure attribute based encryption (ABE) scheme that can handle access control policies expressible as polynomial-size 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 information-theoretic argument at the heart of Waters'dual system by enfolding it in an information-theoretic 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}
}