[Resource Topic] 2022/957: Caulk+: Table-independent lookup arguments

Welcome to the resource topic for 2022/957

Caulk+: Table-independent lookup arguments

Authors: Jim Posen and Assimakis A. Kattis


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.

ePrint: https://eprint.iacr.org/2022/957

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 .