Elements of Commitment Schemes

<style> .markdown-body code, .markdown-body tt { color: #eee; background-color: rgba(20, 230, 230, 0.36); } /* a, .open-files-container li.selected a { color: #5EB7E0; } */ </style> Commitment schemes are fundamental components of many cryptography protocols. A commitment scheme allows a *committer* to compute and publish a value $d=C(m)$, called a *commitment* or a *digest*, which binds him/her to a message $m$ (*binding*) without revealing it to the public (*hiding/zero-knowledge*). Later, she may *open* the commitment by revealing to the public a candidate $m^*$ that she claims to correspond (fully or partially) to the hidden message $m$ associated with the digest $d$. A public *verifier* can then check that the candidate $m^*$ is indeed consistent with the commitment $d$ obtained from the hidden message $m$, hitherto unknow to the verifier.   ![](https://i.imgur.com/jj48ydK.png) As mentioned, commitment schemes can be catagorized based on the *type* of data or information containing mathematical objects they operate on, which corresponds to the type/structure of the message $m$. The message can have many parts and have the structure of sets, vectors, functions and so on. In the notation we will use, $i(m)$ will indicate the $i$th element of the committed message $m$, when $m$ is a set (arbitrary order) or a vector (natural order). In the case of a commitment to a function $m$ however, $i(m)$ will indicate $m(i)$, the evaluation of $m$ at $i$, which requires $i$ to be an element of its domain. In the case of commitments to messages with multiple parts, a *partial opening* is relevant. In such cases, partial opening for a specific part of the message $i(m)$ involves revealing both a candidate $m_i^*$ and an *opening proof* $\pi_i$ that is needed to show the consistency of $m_i^*$ with the overall commitment $d$ for the entire message. Once the candidate for the partial opening is verified, and $m_i^* = i(m)$ is confirmed, $i$th element of the original message is revealed to the public through this verification process. However, the rest of the message ideally remains hidden. This is a key property, being able to open parts of a message while keeping the rest hidden. Next, we give a more formal definition that identifies the common elements of all commitment schemes. --- Formal definition --- There are four algorithms that are shared by all commitment schemes: - A (trusted/non-trusted) setup algorithm $\Phi(s)\rightarrow \rho$, where some initial input parameters $s$ (e.g. security parameters) determine the publicly-known parameters $\rho$ of the scheme. - a commitment algorithm $C(\rho, m)\rightarrow d$, which produces the digest $d$ (overall commitment) for the input message $m$, - a partial opening algorithm $O(\rho, m, i) \rightarrow \pi_i$, which produces an *opening proof* for a specific part of the message $i(m)$, which contains information from the rest of the message that is needed by the verification algorithm, - and finally, a verification algorithm $V(\rho, d, i, \pi_i, m_i^*)\rightarrow 0/1$, which confirms with an output of $1$ (or denies with an output of $0$), that the $i$th element of the message is indeed the candidate, $m_i^*=i(m)$, given the digest and the opening proof as input, without knowing any part of $m$, the message that was committed to. Note that the verification algorithm $V$, which is used by the public, must be completely blind to the message $m$ by design, meaning that it cannot have *as input* any information about the committed message that it aims to verify/open. For example, in the case of a vector commitment, this includes information such as the number of elements that the committed message has. In the case of a polynomial commitment, it includes information such as the degree of the polynomial. It must rely only on the candidate, the digest and the opening proof. On the other hand, the commitment algorithm $C$ and the opening algorithm $O$ are used only by the committer, as they require the message $m$ to be known. --- Properties --- The commitment algorithm $C$ (and the opening algorithm $O$) achieve *binding* and *hiding* in various different ways, as we will discuss in individual examples schemes specific to different families. Aside from binding and hiding, there is an important property we would like to discuss shortly when we talk about commitment schemes: **Soundness**: The verification algorithm should output $1$ for the correct set of inputs, i.e. the correct digest $C(\rho, m)$, correct opening proof $O(\rho, m, i)$ and the correct candidate $i(m)$, $$ V(\rho, C(\rho, m), i, O(\rho, m, i), i(m))=1. $$ Further, it should output $0$ for any incorrect set of inputs (any deviation from the above). This latter condition is hard to satisfy for most practical commitment schemes and, in general, they achieve it probabilistically (and as a further downgrade, computationally), meaning that it is extremely hard to find a set of invalid inputs that will cause the verification algorithm to output $1$. This *imperfect* computational soundness is a result of going from an idealized oracle to a more real-realistic and practical finite computation to arrive at a digest (and opening proof etc.), usually based on one-way functions. This is the same type of soundness breakdown as the transition from the *random oracle model* to a *cryptographic hash function*.  --- Efficiency --- **Space/Communication Efficiency**: The first type of efficiency of interest is about the sizes of outputs produced by a commitment scheme, namely, - the size of the digest $d$, - the size of the opening proof $\pi_i$ for any given element $i$. These are of interest because usually these need to be communicated between different parties, or in more recent applications such as blockchain, stored in an computationally expensive type of storage. **Time/Computational Efficiency**: The second type of efficiency of interest is about the time complexity of the three algorithms, $C$, $O$, and $V$, associated with a commitment scheme. Overall, this gives us $5$ different aspects of efficiency, whose importance depends on the application. State-of-the-art commitment schemes usually have trade-offs between these different aspects in a way that is suitable to the problems they are trying to solve. In addition to these concerns about efficiency, there is also the difficulty of the setup algorithm $\Phi$, which may require a trusted setup, a special ritual between the parties involved to establish binding/hiding properties for the scheme. Since this is cumbersome, it is a disadvantage for the commitment scheme, though it could lead to better efficiency as we will see in later chapters, e.g. Kate polynomial commitments. --- Remarks --- This concludes the introductory discussion on the elements of commitment schemes. In the following chapter, we begin our discussion of different families of schemes through single-element commitments. [Intro: A Hierarchical View of Cryptographic Commitment Schemes](/@kullervo/commitmentHierarchy) [Next: Single-element Commitments](/@kullervo/commitmentSingle)