Welcome to the resource topic for 2020/1516
Title:
How to compute all Pointproofs
Authors: Alin Tomescu
Abstract: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 .