Candidate: Tanmayi Jandhyala
Date: December 2, 2024
Time: 1:00pm
Location: EIT 3151-3153
Supervisor: Guang Gong
All are welcome!
Abstract:
By employing secure, interoperable, and streamlined data-sharing capabilities, companies can leverage the blockchain technology to enhance data accessibility and collaboration while maintaining the security of their data. Notably, blockchain possesses potential to also support privacy-preservation by integrating zero-knowledge proofs into its design. Yet, the efficiency and scalability of the underlying cryptographic protocols that enable this remains a challenge. There evidently exists a gap between theoretical advances in cryptographic algorithms and their practical, performance-efficient implementations in software.
Zero-Knowledge Succinct Non-Interactive ARguments of Knowledge (zk-SNARKs) offer a promising approach to large-scale privacy assurance. However, with significantly large constraints and complex proofs, realizing zk-SNARK-based protocols in practice can be challenging. This thesis addresses this gap by enhancing the efficiency of the
Fast Reed-Solomon Interactive Oracle Proof of Proximity (FRI) protocol- a core component in post-quantum zk-SNARKs that reduces computational complexity in systems with substantial mathematical instances. Existing schemes that implement the FRI protocol entail significant computational times due to large proof sizes. Through an optimized, GPU-based implementation of FRI, this work aims to accelerate performance, essential for privacy-preserving, decentralized, and post-quantum secure systems.
This thesis presents Air-FRI, a novel GPU-enabled software implementation of the FRI protocol, which includes a parallelized computation of Reed-Solomon codewords, pre-computation of time-intensive finite field operations, non-interactiveness, and the application of a unified Merkle tree commitment to authenticate the entire proof. Together, the implemented optimizations yield a software-oriented solution that significantly reduces prover and verifier times while minimizing proof size, addressing both scalability and efficiency challenges in zk-SNARK-based algorithms. Performance evaluations across security levels confirm the implementation’s practicality and high throughput, establishing it as a valuable contribution within the research space.
Our results show a stellar 93.3% improvement on an average in the speed of the protocol on the GPU as compared to its implementation on a CPU for the same parameters, including the execution time of all of its sub-phases: the commit phase, the query phase, the co-linearity and authentication checks to ensure correctness of the proof.
This work expands on the use of FRI in zk-SNARK algorithms to strengthen the privacy in decentralized systems. It establishes a foundation for advancing privacy-preserving post-quantum cryptography, supporting the development of secure, transparent, and privacy-centered digital infrastructure for the future.