Cryptology ePrint Archive: Report 2020/1516
How to compute all Pointproofs
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.
Category / Keywords: public-key cryptography / vector-commitments, pointproofs, toeplitz, discrete-fourier-transform, dft
Date: received 3 Dec 2020, last revised 4 Dec 2020
Contact author: alint at vmware com
Available format(s): PDF | BibTeX Citation
Note: For an errata, see the latest GitHub diffs: https://github.com/alinush/pointproofs-note/compare/1eed43a..master
Version: 20201205:030024 (All versions of this report)
Short URL: ia.cr/2020/1516
[ Cryptology ePrint archive ]