[Resource Topic] 2020/1516: How to compute all Pointproofs

Welcome to the resource topic for 2020/1516

How to compute all Pointproofs

Authors: Alin Tomescu


In this short note, we explain how to reduce the time to compute all N proofs in the Pointproofs vector commitment (VC) scheme by Gorbunov et al., from O(N^2) time to O(N\log{N}). The key ingredient is representing the computation of all proofs as a product between a Toeplitz matrix and the committed vector, which can be computed fast using Discrete Fourier Transforms (DFTs). We quickly prototype our algorithm in C++ and show it is much faster than the naive algorithm for computing all proofs in Pointproofs.

ePrint: https://eprint.iacr.org/2020/1516

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .