Vector commitments using only symmetric cryptography

Question

A vector commitment scheme is a scheme (dough!) that allows a prover to prove that $v_i$ is a component of a vector $v$ without revealing any other information about $v$ . (So the prover commits to $v$ and then proves that $v_i$ is one of it's components).

To the best of my knowledge, current vector commitment schemes that use $O(1)$ space, rely on asymmetric cryptography, either polynomial commitments (depending on strong DH) or other schemes relying on CVP.

Is it known if vector commitment schemes can be done with symmetric crypto only? Are there any schemes or any impossibility results?

Answer 1

A simple method for an $n$-long vector $v$ is to select $n$ random secret keys $k_i$ for $i=0,\ldots n-1$. Now compute an HMAC for each key-component pair i.e. $H_i:=\mathrm{HMAC}(k_i,v_i)$, sort the list of $H_i$ values and publish this as a commitment.

To prove that $v_i$ is a component, simply reveal $k_i$ and identify $H_i$ in the list.

One can get fancier with smaller commitments by randomly permuting the components and hashing them into a Merkle tree and then publishing the root of the tree. This allows committing with a single hash value which takes $O(1)$ space. A proof then consists of revealing the leaf node $v_i$ as well as one intermediate node per level to recreate a computation of the commitment. These proofs will consist of $O(\log n)$ hash values as well as the component itself.