How to compute all Pointproofs

Alin Tomescu

Paper 2020/1516 Original: eprint.iacr.org/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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
History: 2020-12-05: last updated; 2020-12-04: published
Short URL: https://ia.cr/2020/1516
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2020/1516,
      author = {Alin Tomescu},
      title = {How to compute all Pointproofs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1516},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1516}
}