Content area
Cryptographic research aims to study and guarantee the confidentiality, integrity, and authenticity of information in an increasingly digital world. This thesis focuses on different cryptographic primitives and intends to optimize the efficiency of deploying these protocols for multiple instances, thereby enhancing their scalability. We propose new designs of these primitives in the "batching" setting with a goal of practical deployment. We focus on three protocols: public key encryption, time-lock puzzles, and short non-interactive proofs. These protocols address different facets of security, ensuring the confidentiality of messages to unintended recipients and verifying the authenticity of computations.
Suppose a user wants to broadcast an encrypted message to K recipients. With public-key encryption, the sender would construct K different ciphertexts, one for each recipient. The size of the broadcasted message then scales linearly with K. Broadcast encryption offers one solution to this problem where ciphertext size scales sublinearly with the number of recipients, but at the cost of introducing a central trusted party. Recently, several works have introduced notions like distributed broadcast encryption and flexible broadcast encryption, which combine the decentralized, trustless model of traditional public-key encryption with the efficiency guarantees of broadcast encryption. In this work, we introduce a generic compiler that takes any distributed broadcast encryption scheme and produces a flexible one.
Time-lock puzzles allow a user to communicate a message that takes a recipient a large amount of sequential computation to unlock. When scaling these systems in practical use cases, it becomes crucial to be able to batch-solve puzzles, i.e., simultaneously open multiple puzzles. Ideally, we would want to batch solve while working to solve a single one. Unfortunately, all previously known TLP constructions that support batch solving rely on super-polynomially secure indistinguishability obfuscation, making them impractical. We present novel TLP constructions that offer batch-solving capabilities without using heavy cryptographic hammers. Furthermore, we introduce the concept of "rogue-puzzle attacks", where maliciously crafted puzzle instances may disrupt the batch-solving process of honest puzzles. We propose constructions of concrete and efficient TLPs designed to prevent such attacks.
In a proof system, a prover convinces the verifier that some statement is true. We want certain properties such as zero-knowledge (where we require that the proof does not reveal anything more about the statement other than its truth) and succinctness (where proofs are short and can be verified quickly). In the batch setting, a prover convinces a verifier of multiple NP statements with communication that scales sublinearly in the number of instances. We give a direct construction of such a protocol that supports batching an unbounded number of statements from indistinguishability obfuscation and one-way functions. Additionally, we introduce and prove a new system property updatability, where a prover can take a proof on T statements and "update" it to obtain a proof on T+1 statements. Notably, the update procedure only requires knowledge of a (short) proof for T statements and does not require knowledge of witnesses for T+1 statements.