Jiaxin Guan will present his FPO "Cryptography against Space-Bounded Adversaries" on July 12, 2023 at 1pm in CS 105
The members of his committee are as follows:
Examiners: Mark Zhandry (Advisor), Gillat Kol, Ran Raz
Readers: Mark Braverman, Matt Weinberg
Abstract:
Traditionally in cryptography, we consider adversaries that are time-bounded by making specific computational assumptions. In this thesis, I examine the scenario where the adversaries are space-bounded instead, 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 never-before-possible results.
First, we start off with Maurer's Bounded Storage Model. It is a model where the adversary abides to a certain memory bound throughout the entire game. 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 an improved number of rounds and enhanced correctness.
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, 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 notice 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 "somewhere randomness extractor".