Scaling Verifiable Computations with Hidden-order RSA Groups

PhD Thesis Proposal Defense


Title: "Scaling Verifiable Computations with Hidden-order RSA Groups"

by

Mr. Jiajun XIN


Abstract:

Verifiable computation (VC) enables an untrusted server to prove the correct 
execution of a computation to a client that only needs to spend minimal 
effort for verification. Initially mostly a theoretical concept, recent 
advancements in succinct non-interactive arguments of knowledge (SNARKs) 
have transformed VC into a tool with significant real-world applications. 
For instance, verifiable computation has been instrumental in addressing 
problems such as verifiable databases, zkRollups, authenticated cloud 
computing, data auditing, decentralized identities, etc. Despite this, 
verifiable computation suffers from high computational overheads for the 
prover, which limits its scalability and broader adoption in practice. This 
thesis explores methods to overcome these limitations and scale verifiable 
computation effectively using hidden-order RSA groups. Specifically, it 
focuses on three key aspects: 1) applying verifiable computation to 
real-world problems, specifically by designing a proof-of-solvency system 
for cryptocurrency exchanges; 2) efficiently integrating large datasets into 
SNARKs; 3) building new cryptographic tools with novel verifiability 
features.

In the first part of this thesis, we combine RSA accumulators with SNARKs to 
efficiently compute the sum of millions of committed values, applying this 
technique to dynamic proofs of liabilities. In the second part, we optimize 
the efficiency of RSA + SNARK compositions by eliminating a previously 
required step, significantly improving performance under a novel hardness 
assumption. In the final part, we extend the scope of verifiable computation 
to time-locked settings by introducing verifiable time-lock puzzles (VTLPs). 
Unlike traditional time-lock puzzles, where solvers have no guarantee about 
the correctness of the solution they reveal, VTLPs allow the generator to 
publish a succinct proof that the solution satisfies specific properties 
without revealing additional information. This bridges the gap between 
time-lock puzzles and verifiable computation, enabling new applications in 
time-sensitive cryptographic protocols.


Date:                   Friday, 27 June 2025

Time:                   4:00pm - 6:00pm

Venue:                  Room 3494
                        Lifts 25/26

Committee Members:      Dr. Dimitris Papadopoulos (Supervisor)
                        Dr. Shuai Wang (Chairperson)
                        Prof. Cunsheng Ding