Candidate: Ahmed Zawia
Date: November 6, 2024
Time: 2:00 PM
Location: Online - contact the candidate for more information.
Supervisor: Hasan, Anwar
Abstract:
The primary objectives of the thesis work are to conduct in-depth research in the field of delay-based cryptography and to improve the efficiency of evaluating ideal class group action, which serves as a building block in this area. Our study of delay-based cryptography aims to formalize and implement new delay-based primitives that use time-delay functions to improve the security and functionality of various applications. Delay-based cryptographic primitives, such as time-lock puzzles and verifiable delay functions, play a crucial role in various cryptographic protocols by ensuring that certain computations cannot be performed faster than a predefined time, no matter the level of parallelism.
We start by introducing a class of trapdoor verifiable delay functions (trapdoor-VDFs), an extended concept of verifiable delay functions, and provide a formal definition of their security notions. Trapdoor-VDFs feature a large ensemble of trapdoors, enabling a client to randomly select a private trapdoor to generate a unique challenge. Without the trapdoor, a server must perform a predetermined number of sequential steps to solve the challenge, while any client can efficiently verify the server's solution without knowing the trapdoor. We also propose a construction of trapdoor-VDFs leveraging large smooth degree supersingular isogenies, with bilinear pairings for efficient public verification. Our construction is useful for time-sensitive applications that require public verification and guarantees of timely release, such as sealed-voting and front-running attack prevention.
Then, we introduce the notion of ChronoCloak, an integrated solution designed to prevent premature access to digital media content while preserving recipient's privacy. Specifically, ChronoCloak enables a sender to transmit a collection of secret data through a puzzle that requires a predetermined amount of time to be solved. Once the puzzle is solved, the receiver can only extract a chosen subset of the secret data, without the sender knowing which subset was chosen. With public verifiability, the puzzle-solving process can be securely outsourced while ensuring that only the receiver can extract the chosen secret subset. Additionally, we introduce an ideal functionality for ChronCloak and propose a generic instantiation that implements ChronCloak's functionality in the random oracle model.
Finally, we propose a new batching strategy for computing a set of group actions within the Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) framework, which is a crucial component for developing post-quantum cryptographic schemes like zero-knowledge proofs and signature schemes. Our work presents two variants of the batching strategy each of which is suited for different security requirements and application contexts. The first variant is for computing a public set of CSIDH group actions, and aims to reduce the number of finite field arithmetic operations required. Our results show roughly up to 14% reduction in computational cost. Towards our second variant, we first propose an efficient new constant-time CSIDH algorithm for evaluating a private group action, which is based on the state-of-the-art batching techniques from CTIDH. We then introduce a method for computing a private set of CSIDH group actions, which runs in constant time and reduces the overall number of finite field arithmetic operations needed. When combined with our constant-time algorithm, it shows a reduction in computational cost roughly up to 8% compared to the current state-of-the-art constant-time CSIDH. Interestingly, the constant-time implementation alone reduces computation by about 4%. Finally, we present a proof-of-concept implementation showcasing the results of our work.