Scaling Verifiable Computations with Hidden-order RSA Groups

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


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 hash 
function property.

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:                   Tuesday, 19 August 2025

Time:                   10:00am - 12:00noon

Venue:                  Room 5501
                        Lifts 25/26

Chairman:               Dr. Maosheng XIONG (MATH)

Committee Members:      Dr. Dimitris PAPADOPOULOS (Supervisor)
                        Prof. Ke YI
                        Prof. Charles ZHANG
                        Prof. Allen HUANG (ACCT)
                        Dr. Foteini BALDIMTSI (George Mason University)