Set Commitments

<style> .markdown-body code, .markdown-body tt { color: #eee; background-color: rgba(20, 230, 230, 0.36); } </style> In this chapter, we discuss set commitments, which are the first in the hierarchy with a partial opening mechanism. The mathematical object to be committed to, which will consitute our message $m$, is a set $m = \{m_1, m_2,...,m_n\}$ of variable size $n \leq n_\text{max}$. Being a set, its elements are unique, i.e. $i\neq j \implies m_i\neq m_j$ and indexing of the elements is arbitrary. In practice, commitments to sets are usually simulated by vector commitments. However, there is an important commitment primitive called an *accumulator* that is invariant to the arbitrary indexing of the set's elements (order/permutation invariance). Accumulators are *not* vector commitments, as they do not commit to a particular positioning of the elements. We will discuss accumulators through a specific example. --- <span style="color: #0; font-family: Times New Roman; font-size: 1.1em;">Accumulators with groups of known order -- DL </span> --- Let us assume that the elements of the sets to be committed to belong to the set $\mathbb{S}$. In other words, the sets to be committed to are elements of the power set of $\mathbb{S}$, $m \in 2^\mathbb{S}$. Further, let us assume that there exists a one-to-one mapping function $\lambda: \mathbb{S} \rightarrow \mathbb{P}_{\leq p_\text{max}}$ that transforms each element $s \in \mathbb{S}$ to a distinct prime number $\lambda(s) \leq p_\text{max}$. This mapping is easy to create for any finite cardinality $\mathbb{S}$. - Similar to the single-element commitment scheme that were based on groups of known order, the setup algorithm outputs the group generator, and the group order, based on some security parameters $s$, such as the size of the group to be used, along with the mapping $\lambda$, $\Phi(s)=\rho=(p,g,\lambda)$. - The commitment algorithm maps each element of the message set $m = \{m_1, m_2, ..., m_n\}$ into their prime number counterparts $\lambda(m_i)$ and computes the product $\prod_{i=1}^n \lambda(m_i)$. This accumulator is unique for each message set in $2^\mathbb{S}$ due to the prime mapping. Then, the digest is simply the group encrypted accumulator, $d = C(\rho, m) = g^{\prod_{i=0}^n \lambda(m_i)}=g^{\prod_{i=0}^n \lambda(m_i) \mod p}$. - The opening algorithm computes the proof for the $i$th element of the message $i(m) = m_i$ by first computing the inverse element $g^{-\lambda(m_i) \mod p}$ and group multiplying it with the digest, $ $O(\rho, m, i) = \pi_i = d\cdot g^{-\lambda(m_i) \mod p} = g^{\prod_{j\neq i}^n \lambda(m_j)}$. Note that $\pi_i$ contains (in an encrypted manner) all the information from the set $m$ that is needed in addition to $m_i$ to arrive at the digest $d$, since $d=\pi_i \cdot g^{\lambda(m_i)}$ for any $i$. - Therefore, the verification algorithm simply checks that the above relationship holds for candidate message $m_i^*$, $V(\rho, d, i, \pi_i, m_i^*) = (\pi_i \cdot g^{\lambda(m_i^*)} \stackrel{?}{=} d)$. The prime number mapping $\lambda$ makes this commitment scheme impractical and in general accumulators replace this mapping with a more interactive map such as $\lambda(m_i) = m_i+\beta$ where $\beta$ is determined by a verifier. This makes the mapping pseudo-unique, meaning that it is hard to replicate its results without knowing $\beta$ beforehand. --- **Efficiency**: The space/communication complexity of the digest $d$ and any opening proof $\pi_i$ are single group elements (whose size depends on the group size and representation). The complexity of the commitment algorithm is $\mathrm{O}(\log (\prod_{i=0}^n \lambda(m_i) \mod p))$ group operations in $G$, using fast exponentiation such as the square & multiply algorithm. The complexity of the opening algorithm is $\mathrm{O}(\log (-\lambda(m_i) \mod p))$ group operations in $G$ using fast exponentiation. The scheme does not require a trusted-setup algorithm, as the parameters of the group and $\lambda$ are completely public. --- <span style="color: #0; font-family: Times New Roman; font-size: 1.1em;">Reduction to single-element commitments </span> --- Given a set commitment $(\Phi^+, C^+, O^+, V^+)$, it is straightforward to simulate a single-element commitment $(\Phi, C, O, V)$ through the following reduction: - The setup algorithm is the same, i.e. $\Phi(s)= \Phi^+(s) = \rho$. - The commitment algorithm creates a digest from a single-element message $m$ by creating a single element set $\{m\}$ and committing to it through $C^+$, $C(\rho, m) = C^+(\rho, \{m\}) = d$. - The opening algorithm $O$ for the entire message $i(m) = m$ produces the opening proof for the first element of the set with $O^+$, $O(\rho, m, i) = O^+(\rho, \{m\}, 1)= \pi_i$. Note that in the reduction, the opening proof is no longer empty as was the case in single-element commitment schemes of the previous chapter. - The verification algorithm for a candidate message $m_i^*$ is simulated as $V(\rho, d, i, \pi_i, m_i^*) = V^+(\rho, d, 1, \pi_i, m_i^*)$. This is extremely simplistic, as we are just wrapping the single-element message $m$ as a set and using the set commitment algorithms to simulate the single-element commitment. This will be a common theme, but the reductions become a bit more complex and will require additional algorithms in later chapters. --- <span style="color: #0; font-family: Times New Roman; font-size: 1.1em;">Remarks </span> --- As we mentioned, commitments to sets are usually simulated through practical and efficient vector commitments, which we discuss in the next chapter. However, accumulators (with some slight modifications to the presented version) are important components in some state-of-the-art zero-knowledge proof systems. [Intro: A Hierarchical View of Cryptographic Commitment Schemes](/@kullervo/commitmentHierarchy) [Previous: Single-element Commitments](/@kullervo/commitmentSingle) [Next: Vector Commitments](/@kullervo/commitmentVector)