Publications

2024

1. On Sequential Functions and Fine-Grained Cryptography

   Jiaxin Guan, and Hart Montgomery

   In CRYPTO , 2024

   Abs ePrint Bib

   A sequential function is, informally speaking, a function f for which a massively parallel adversary cannot compute "substantially" faster than an honest user with limited parallel computation power. Sequential functions form the backbone of many primitives that are extensively used in blockchains such as verifiable delay functions (VDFs) and time-lock puzzles. Despite this widespread practical use, there has been little work studying the complexity or theory of sequential functions.
   
   Our main result is a black-box oracle separation between sequential functions and one-way functions: in particular, we show the existence of an oracle O that implies a sequential function but not a one-way function. This seems surprising since sequential functions are typically constructed from very strong assumptions that imply one-way functions and also since time-lock puzzles are known to imply one-way functions (Bitansky et al., ITCS ’16).
   
   We continue our exploration of the theory of sequential functions. We show that, informally speaking, the decisional, worst-case variant of a certain class of sequential function called a continuous iterative sequential function (CISF) is PSPACE-complete. A CISF is, in a nutshell, a sequential function f that can be written in the form f(k, x) = g^k(x) for some function g where k is an input determining the number of "rounds" the function is evaluated. We then show that more general forms of sequential functions are not contained in PSPACE relative to a random oracle.
   
   Given these results, we then ask if it is possible to build any interesting cryptographic primitives from sequential functions that are not one-way. It turns out that even if we assume just the existence of a CISF that is not one-way, we can build certain "fine-grained" cryptographic primitives where security is defined similarly to traditional primitives with the exception that it is only guaranteed for some (generally polynomial) amount of time. In particular, we show how to build "fine-grained" symmetric key encryption and "fine-grained" MACs from a CISF. We also show how to build fine-grained public-key encryption from a VDF with a few extra natural properties and indistinguishability obfucsation (iO) for null circuits. We do not assume one-way functions. Finally, we define a primitive that we call a commutative sequential function–essentially a sequential function that can be computed in sequence to get the same output in two different ways–and show that it implies fine-grained key exchange.

   @inproceedings{C:GuaMon24,
     title = {On Sequential Functions and Fine-Grained Cryptography},
     author = {Guan, Jiaxin and Montgomery, Hart},
     booktitle = {Annual International Cryptology Conference},
     pages = {393--428},
     year = {2024},
     organization = {Springer},
   }

2. Adaptively Secure Streaming Functional Encryption

   Pratish Datta, Jiaxin Guan, Alexis Korb, and Amit Sahai

   Abs ePrint Bib

   This paper introduces the first adaptively secure streaming functional encryption (sFE) scheme for P/Poly. sFE stands as an evolved variant of traditional functional encryption (FE), catering specifically to contexts with vast and/or dynamically evolving data sets. sFE is designed for applications where data arrives in a streaming fashion and is computed on in an iterative manner as the stream arrives. Unlike standard FE, in sFE: (1) encryption is possible without knowledge of the full data set, (2) partial decryption is possible given only a prefix of the input.
   
   Guan, Korb, and Sahai introduced this concept in their recent publication [CRYPTO 2023], where they constructed an sFE scheme for P/Poly using a compact standard FE scheme for the same. However, their sFE scheme only achieved semi-adaptive-function-selective security, which constrains the adversary to obtain all functional keys prior to seeing any ciphertext for the challenge stream. This limitation severely limits the scenarios where sFE can be applied, and therefore fails to provide a suitable theoretical basis for sFE.
   
   In contrast, the adaptive security model empowers the adversary to arbitrarily interleave requests for functional keys with ciphertexts related to the challenge stream. Guan, Korb, and Sahai identified achieving adaptive security for sFE as the key question left open by their work.
   
   We resolve this open question positively by constructing an adaptively secure sFE construction from indistinguishability obfuscation for P/Poly and injective PRGs. By combining our work with that of Jain, Lin, and Sahai [STOC 2021, EUROCRYPT 2022], we obtain the first adaptively secure sFE scheme for P/Poly based on sub-exponential hardness of well-studied computational problems.

   @article{EPRINT:DGKS24,
     title = {Adaptively Secure Streaming Functional Encryption},
     author = {Datta, Pratish and Guan, Jiaxin and Korb, Alexis and Sahai, Amit},
     journal = {Cryptology ePrint Archive},
     year = {2024},
   }

2023

1. Multi-Instance Randomness Extraction and Security against Bounded-Storage Mass Surveillance

   Jiaxin Guan, Daniel Wichs, and Mark Zhandry

   In TCC , 2023

   Abs ePrint Bib

   Consider a state-level adversary who observes and stores large amounts of encrypted data from all users on the Internet, but does not have the capacity to store it all. Later, it may target certain "persons of interest" in order to obtain their decryption keys. We would like to guarantee that, if the adversary‘s storage capacity is only (say) 1% of the total encrypted data size, then even if it can later obtain the decryption keys of arbitrary users, it can only learn something about the contents of (roughly) 1% of the ciphertexts, while the rest will maintain full security. This can be seen as an extension of incompressible cryptography (Dziembowski CRYPTO ’06, Guan, Wichs and Zhandry EUROCRYPT ’22) to the multi-user setting. We provide solutions in both the symmetric key and public key setting with various trade-offs in terms of computational assumptions and efficiency.
   
   As the core technical tool, we study an information-theoretic problem which we refer to as "multi-instance randomness extraction." Suppose X₁, ..., X_t are correlated random variables whose total joint min-entropy rate is α, but we know nothing else about their individual entropies. We choose t$ random and independent seeds S₁, ..., S_t and attempt to individually extract some small amount of randomness Y_i = Ext(X_i; S_i) from each X_i. We’d like to say that roughly an α-fraction of the extracted outputs Y_i should be indistinguishable from uniform even given all the remaining extracted outputs and all the seeds. We show that this indeed holds for specific extractors based on Hadamard and Reed-Muller codes.

   @inproceedings{TCC:GuaWicZha23,
     title = {Multi-Instance Randomness Extraction and Security against Bounded-Storage Mass Surveillance},
     author = {Guan, Jiaxin and Wichs, Daniel and Zhandry, Mark},
     booktitle = {Theory of Cryptography Conference},
     pages = {93--122},
     year = {2023},
     organization = {Springer},
   }

2. Streaming Functional Encryption

   Jiaxin Guan, Alexis Korb, and Amit Sahai

   In CRYPTO , 2023

   Abs ePrint Bib

   We initiate the study of streaming functional encryption (sFE) which is designed for scenarios in which data arrives in a streaming manner and is computed on in an iterative manner as the stream arrives. Unlike in a standard functional encryption (FE) scheme, in an sFE scheme, we (1) do not require the entire data set to be known at encryption time and (2) allow for partial decryption given only a prefix of the input. More specifically, in an sFE scheme, we can sequentially encrypt each data point x_i in a stream of data x = x₁...x_n as it arrives, without needing to wait for all n values. We can then generate function keys for streaming functions which are stateful functions that take as input a message x_i and a state st_i and output a value y_i and the next state st_i+1. For any k ≤ n, a user with a function key for a streaming function f can learn the first k output values y₁...y_k where (y_i, st_i+1) = f(x_i, st_i) and st₁ = ⟂ given only ciphertexts for the first k elements x₁...x_k.
   
   In this work, we introduce the notion of sFE and show how to construct it from FE. In particular, we show how to achieve a secure sFE scheme for P/Poly from a compact, secure FE scheme for P/Poly, where our security notion for sFE is similar to standard FE security except that we require all function queries to be made before the challenge ciphertext query. Furthermore, by combining our result with the FE construction of Jain, Lin, and Sahai (STOC, 2022), we show how to achieve a secure sFE scheme for P/Poly from the polynomial hardness of well-studied assumptions.

   @inproceedings{C:GuaKorSah23,
     title = {Streaming Functional Encryption},
     author = {Guan, Jiaxin and Korb, Alexis and Sahai, Amit},
     booktitle = {Annual International Cryptology Conference},
     pages = {433--463},
     year = {2023},
     organization = {Springer},
   }

3. Cryptography against Space-Bounded Adversaries

   Jiaxin Guan

   Ph.D. Dissertation

   Abs PDF Bib

   Traditionally in cryptography, we consider adversaries that are time-bounded by making certain computational assumptions. In this thesis, I study the scenario where the adversaries are space-bounded, i.e. the adversary can only use up to a certain amount of memory bits. Under these scenarios, we can achieve either unconditional security properties or neverbefore-possible results.
   
   First, I start off with Maurer’s Bounded Storage Model. It is a model where the adversary abides by a certain memory bound throughout the entire attack. Under this model, I show simple constructions of a key-agreement protocol, a commitment scheme, and an oblivious transfer protocol, all based on Raz’s lower bound on parity learning. These constructions have several advantages over prior work, including enhanced correctness and an improved and optimal number of rounds.
   
   Subsequently, I show that if we combine computational assumptions with the bounded storage model, we can achieve results that are not possible in the standard model. I define a new object named Online Obfuscation, which is analogous to a Virtual Grey-Box Obfuscation in the Bounded Storage Model, and show how to use it to construct disappearing encryption and signature schemes where the ciphertext and the signature effectively "disappear" after transmission.
   
   Lastly, I make the observation that in the Bounded Storage Model, the memory bound on the adversary is enforced throughout the entire game. One can imagine a variant where the bound is only enforced for long-term storage, allowing the adversary to use an arbitrary amount of memory during the transmission phase. I define incompressible cryptography to capture this intuition and show constructions using randomness extractors and other cryptographic tools. Furthermore, I show that under the multi-user setting, we can still achieve desired incompressible security if we simply replace the randomness extractor with a special "multi-instance randomness extractor".

   @phdthesis{guan2023cryptography,
     title = {Cryptography against Space-Bounded Adversaries},
     author = {Guan, Jiaxin},
     year = {2023},
     school = {Princeton University},
   }

4. A Lower Bound on the Length of Signatures Based on Group Actions and Generic Isogenies

   Dan Boneh, Jiaxin Guan, and Mark Zhandry

   In EUROCRYPT , 2023

   Abs ePrint Bib

   We give the first black box lower bound for isogeny-based protocols that can be described as group actions. We show that, for a large class of signature schemes making black box use of a (potentially non-abelian) group action, the signature length must be Ω(λ²/log λ). Our class of signatures generalizes all known signatures that derive security exclusively from the group action, and our lower bound matches the state of the art, showing that the signature length cannot be improved without deviating from the group action framework.

   @inproceedings{EC:BonGuaZha23,
     title = {A Lower Bound on the Length of Signatures Based on Group Actions and Generic Isogenies},
     author = {Boneh, Dan and Guan, Jiaxin and Zhandry, Mark},
     booktitle = {Annual International Conference on the Theory and Applications of Cryptographic Techniques},
     pages = {507--531},
     year = {2023},
     organization = {Springer},
   }

2022

1. Incompressible Cryptography

   Jiaxin Guan, Daniel Wichs, and Mark Zhandry

   In EUROCRYPT , 2022

   Abs ePrint Bib

   Incompressible encryption allows us to make the ciphertext size flexibly large and ensures that an adversary learns nothing about the encrypted data, even if the decryption key later leaks, unless she stores essentially the entire ciphertext. Incompressible signatures can be made arbitrarily large and ensure that an adversary cannot produce a signature on any message, even one she has seen signed before, unless she stores one of the signatures essentially in its entirety.
   
   In this work, we give simple constructions of both incompressible public-key encryption and signatures under minimal assumptions. Furthermore, large incompressible ciphertexts (resp. signatures) can be decrypted (resp. verified) in a streaming manner with low storage. In particular, these notions strengthen the related concepts of disappearing encryption and signatures, recently introduced by Guan and Zhandry (TCC 2021), whose previous constructions relied on sophisticated techniques and strong, non-standard assumptions. We extend our constructions to achieve an optimal "rate", meaning the large ciphertexts (resp. signatures) can contain almost equally large messages, at the cost of stronger assumptions.

   @inproceedings{EC:GuaWicZha22,
     title = {Incompressible Cryptography},
     author = {Guan, Jiaxin and Wichs, Daniel and Zhandry, Mark},
     booktitle = {Annual International Conference on the Theory and Applications of Cryptographic Techniques},
     pages = {700--730},
     year = {2022},
     organization = {Springer},
   }

2021

1. Disappearing Cryptography in the Bounded Storage Model

   Jiaxin Guan, and Mark Zhandry

   In TCC , 2021

   Abs ePrint Bib

   In this work, we study disappearing cryptography in the bounded storage model. Here, a component of the transmission, say a ciphertext, a digital signature, or even a program, is streamed bit by bit. The stream is so large for anyone to store in its entirety, meaning the transmission effectively disappears once the stream stops.
   
   We first propose the notion of online obfuscation, capturing the goal of disappearing programs in the bounded storage model. We give a negative result for VBB security in this model, but propose candidate constructions for a weaker security goal, namely VGB security. We then demonstrate the utility of VGB online obfuscation, showing that it can be used to generate disappearing ciphertexts and signatures. All of our applications are not possible in the standard model of cryptography, regardless of computational assumptions used.

   @inproceedings{TCC:GuaZha21,
     title = {Disappearing Cryptography in the Bounded Storage Model},
     author = {Guan, Jiaxin and Zhandry, Mark},
     booktitle = {Theory of Cryptography: 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8--11, 2021, Proceedings, Part II 19},
     pages = {365--396},
     year = {2021},
     organization = {Springer},
   }

2. Iterated Inhomogeneous Polynomials

   Jiaxin Guan, and Mark Zhandry

   In CFail , 2021

   Abs ePrint Bib

   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.

   @article{EPRINT:GuaZha21b,
     title = {Iterated Inhomogeneous Polynomials},
     author = {Guan, Jiaxin and Zhandry, Mark},
     journal = {Cryptology ePrint Archive},
     year = {2021},
   }

2019

1. Simple Schemes in the Bounded Storage Model

   Jiaxin Guan, and Mark Zhandry

   In EUROCRYPT , 2019

   Abs ePrint Bib

   The bounded storage model promises unconditional security proofs against computationally unbounded adversaries, so long as the adversary’s space is bounded. In this work, we develop simple new constructions of two-party key agreement, bit commitment, and oblivious transfer in this model. In addition to simplicity, our constructions have several advantages over prior work, including an improved number of rounds and enhanced correctness. Our schemes are based on Raz’s lower bound for learning parities.

   @inproceedings{EC:GuaZha19,
     title = {Simple Schemes in the Bounded Storage Model},
     author = {Guan, Jiaxin and Zhandry, Mark},
     booktitle = {Advances in Cryptology--EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19--23, 2019, Proceedings, Part III 38},
     pages = {500--524},
     year = {2019},
     organization = {Springer},
   }

2018

1. Return of GGH15: Provable Security against Zeroizing Attacks

   James Bartusek, Jiaxin Guan, Fermi Ma, and Mark Zhandry

   In TCC , 2018

   Abs ePrint Bib

   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¹ 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,
     title = {Return of GGH15: Provable Security against Zeroizing Attacks},
     author = {Bartusek, James and Guan, Jiaxin and Ma, Fermi and Zhandry, Mark},
     booktitle = {Theory of Cryptography Conference},
     pages = {544--574},
     year = {2018},
     organization = {Springer},
   }