<100 subscribers
Share Dialog
OpenSSH supports a number of cryptographic key agreement algorithms considered to be safe against attacks from quantum computers.
Fully Homomorphic Encryption (FHE) enables computations on encrypted data, supporting private shared states on blockchains. Unlike zero-knowledge proofs, FHE allows complex operations but relies on external processors. OpenZeppelin is advancing its use in confidential tokens and beyond.
The Sumcheck protocol is a fundamental building block in probabilistic proof systems and has recently become a key component in the study of efficient and succinct arguments. We investigate time-space tradeoffs for the prover in the streaming computation model, providing tight upper and lower bounds characterizing achievable prover efficiency.
For Sumcheck on a single multi-linear polynomial, we propose an algorithm running in time $O(kN)$ and space $O(N^{\frac{1}{k}})$ for any parameter $k \geq 1$. For non-adaptive provers (which encompass all known Sumcheck algorithms), we prove this time-space tradeoff is optimal.
For Sumcheck on the product of multi-linear polynomials, we design a prover algorithm with running time $O(N\log\log N + k)$ and space $O(N^{\frac{1}{k}})$ for any $k \geq 1$. We further prove that, under the assumption that a natural problem related to multi-linear polynomial multiplication is computationally hard, any prover algorithm using $O(N^{\frac{1}{2}-\epsilon})$ space must incur $\Omega(N(\log\log N + \log \epsilon))$ time.
We implement and evaluate this prover algorithm for multi-linear polynomial products. Experiments show that compared to linear-time prover algorithms, our algorithm can reduce memory usage by up to 120$\times$, while keeping the time overhead within 2$\times$.
The above algorithms and lower bounds also apply in the interactive proof model. In the Polynomial-Interactive Oracle Proof (PIOP) model, we design a new protocol achieving a better time-space tradeoff of $O(N^{\frac{1}{k}})$ space and $O(N(\log^* N + k))$ time for any $k \geq 1$.
https://eprint.iacr.org/2025/1473, which expands on the results of https://eprint.iacr.org/2024/524.
