### Caulk+: Table-independent lookup arguments

##### Abstract

The recent work of Caulk introduces the security notion of position hiding linkability for vector commitment schemes, providing a zero-knowledge argument that a committed vector's elements comprise a subset of some other committed vector. The protocol has very low cost to the prover in the case where the size $m$ of the subset vector is much smaller than the size $n$ of the one containing it. The asymptotic prover complexity is $O(m^2 + m \log n)$, where the $\log n$ dependence comes from a subprotocol showing that the roots of a blinded polynomial are all $n$th roots of unity. In this work, we show how to simplify this argument, replacing the subprotocol with a polynomial divisibility check and thereby reducing the asymptotic prover complexity to $O(m^2)$, removing any dependence on $n$.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
polynomial commitments vector commitments zero knowledge
Contact author(s)
jimpo @ ulvetanna io
kattis @ cs nyu edu
History
2022-10-10: last of 2 revisions
See all versions
Short URL
https://ia.cr/2022/957

CC BY

BibTeX

@misc{cryptoeprint:2022/957,
author = {Jim Posen and Assimakis A. Kattis},
title = {Caulk+: Table-independent lookup arguments},
howpublished = {Cryptology ePrint Archive, Paper 2022/957},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/957}},
url = {https://eprint.iacr.org/2022/957}
}

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