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.

Note: For an errata, see the latest GitHub diffs: https://github.com/alinush/pointproofs-note/compare/1eed43a..master

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
vector-commitmentspointproofstoeplitzdiscrete-fourier-transformdft
Contact author(s)
alint @ vmware com
History
2020-12-05: revised
See all versions
Short URL
https://ia.cr/2020/1516

CC BY

BibTeX

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

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.