## Rachael Cai

Multi-Scalar Multiplication Optimization in CUDA

2024–2025

Electrical Engineering and Computer Science

- Theory of Computation

Charles E. Leiserson

In cryptography, a zero-knowledge proof (ZKP) allows one party (the prover) to prove to another (the verifier) that a given statement is true while avoiding revealing any unnecessary, private information. In the world of digital currency, the accessibility and efficiency of both computing and verifying a ZKP is essential to users.

The most computationally expensive step in ZKP is multiscalar multiplication (MSM), as it requires large, time-consuming PMUL operations, often taking up over 70% of runtime required for ZKP. Current implementations for ZKP that optimize MSM use Pippenger and/or Straus algorithms for reducing complexity. In all implementations involving these optimizations, computation scaling for methods that reduce eliptic curve operations must be implemented on MSM subtasks, since the size of the overall tasks are too large.

This project’s goal is to investigate and implement efficient algorithms for accelerating elliptic curve computation through reducing complexity with elliptic curve calculation techniques, FMA design, and leveraging GPU architecture.

I’m looking forward to better understanding the complexities of performance computing. I believe zero-knowledge proofs serve an important role in cryptography today, and I’m excited to be investigating the multiscalar multiplication aspect of it, which takes the majority of its current runtime.