In our view, the simplest family that is at the base of the hierarchy of commitment schemes consists of commitments to messages with no parts, which we call simple-element commitments. Paradoxically, all messages have some parts to them, perhaps outside of a single bit of information, i.e. a message that contains a single

$0$ or a

$1$.

Therefore, it is not the nature of the messages being committed to that is of importance, but the treatment of the messages by the commitment scheme that makes them "single-element commitments" in our catagorization. In more practical terms, a single-element commitment scheme does not allow a partial opening of the message and treats it as a single indivisible entity. When any part of a message is opened, it is forced by the scheme to be revealed in its entirety.

Next, we discuss a few different schemes in more detail by describing the four algorithms associated with commitments as discussed in the previous chapter.

---

CRHF-based commitments

Cryptographic hash functions (CRHFs) are primitives that approximate a random oracle, a theoretical black box that responds to every unique query with a truly random response chosen uniformly from its output domain.

CRHFs typically achieve this approximate uniformity through ciphers within them with high diffusion and confusion properties. It is statistically hard to find a collision, two inputs that result in the same output, for CRHFs. Pseudo-uniformity of the outputs provides hiding, and collision-resistance provides binding, both of which we require from commitment schemes.

Given a family of hash functions whose inputs are messages with arbitrary length, we can define the four algorithms of the commitment scheme as follows:

• The setup algorithm outputs the specific hash function to use based on some security parameters
  $s$, such as the number of bits the hash function will output etc.,
  $\mathrm{\Phi }(s)=\rho =H$.
• The commitment algorithm simply computes the hash of the message as its digest to be published,
  $C(\rho ,m)=d=H(m)$.
• The opening algorithm outputs nothing, as the only opening proof available is for the entire message
  $i(m)=m$, i.e. its output is empty
  $O(\rho ,m,i)={\pi }_i=()$.
• The verification algorithm simply checks that a candidate message
  $m_i^{\ast }$ has the same hash as the original message, given in the public digest
  $d$,
  $V(\rho ,d,i,{\pi }_i,m_i^{\ast })=(H(m_i^{\ast })\stackrel{?}{=}d)$.

A partial opening of the message is not really possible, as the only plausible way to get to the digest

$d$ is through computing

$H(m)$ using the entire and exact message

$m$ as input. Even a single bit of change to the input changes the output drastically for CRHFs.

As we can see, there is nothing really special about CRHF-based commitments and algorithms of the scheme are just wrappers around the hash function. Nevertheless, this formalization is important for consistency with more complex schemes we will encounter.

---

Efficiency: The space/communication complexity of the digest

$d$ is simply the bit-size of the codomain of the hash function.

The complexity of the commitment and the verification algorithms is simply the same as the hash function's complexity with respect to the input message size.

The scheme does not require a trusted-setup algorithm, as the parameters of the hash function are completely public.

---

Encryption with groups of known order – DL

The next two commitment schems are based on the idea of encryption with finite groups, which are extremely popular in many areas of cryptography.

Let us be given a cyclic multiplicative group

$G$ of prime order

$p$, with a generator

$g$. Assume that the discrete logarithm (DL) problem is hard in

$G$. The order of the group must be exceptionally high (e.g.

$>2^{80}$ or

$80$ bits of security) for the commitment scheme to be binding, and the group operation must be sufficiently unpredictable for it to be hiding.

Then, the four algorithms of a commitment scheme for messages of any length (all messages consisting of bits can be turned into integers) are as follows:

• 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,
  $\mathrm{\Phi }(s)=\rho =(p,g)$.
• The commitment algorithm simply encrypts the message integer
  $m$ through group exponentiation as its digest to be published,
  $C(\rho ,m)=d=g^m=g^{m\text{ mod }p}$.
• The opening algorithm outputs nothing, as the only opening proof available is for the entire message
  $i(m)=m$, and it is empty
  $O(\rho ,m,i)={\pi }_i=()$.
• The verification algorithm simply checks that a candidate message
  $m_i^{\ast }$ has the same encryption as the original message, given in the public digest
  $d$,
  $V(\rho ,d,i,{\pi }_i,m_i^{\ast })=(g^{m_i^{\ast }}-g^{m_i^{\ast }\text{ mod }p}\stackrel{?}{=}d)$.

Again, a partial opening of the message is difficult, as the entire message

$m$ is represented as an integer for the exponentiation (though this is a bit more in the gray area compared to a hash function for some specific parts of the message, and depending on the exact procedure to convert the message to an integer).

---

Efficiency: The space/communication complexity of the digest

$d$ is a single group element (whose size depends on the group size and representation).

The complexity of the commitment (and the verification) algorithm is

$\mathrm{O}(\log m)$ group operations in

$G$, using fast exponentiation such as the square & multiply algorithm.

The scheme does not require a trusted-setup algorithm, as the parameters of the group are completely public.

---

Encryption with groups of unknown order – RSA

A similar encryption based commitment scheme can be constructed using groups of unknown order, of which the RSA encryption is the most well-known. A more in depth discussion of RSA encryption can be found here.

• The setup algorithm picks two large primes
  $p$ and
  $q$ of size
  $s$-bits, computes their product
  $h=pq$ and the order of the multiplicative group modulo h,
  $\varphi (h)=(p–1)(q–1)$. Further, a public key
  $k_{\text{pub}}$ is chosen randomly from the set
  $\{1,2,...,\varphi (h)\}$ s.t.
  $\text{gcd}(\varphi (h),k_{\text{pub}})=1$. The setup algorithm outputs
  $h$ and
  $k_{\text{pub}}$ after promptly destroying
  $p$ and
  $q$, so that no party knowns the factorization of
  $h$.
  $\mathrm{\Phi }(s)=\rho =(h,k_{\text{pub}})$.
• The commitment algorithm simply encrypts the message integer
  $m$ through RSA as its digest to be published,
  $C(\rho ,m)=d=m^{k_{\text{pub}}}\text{ mod }h$.
• The opening algorithm outputs nothing, as the only opening proof available is for the entire message
  $i(m)=m$, and it is empty
  $O(\rho ,m,i)={\pi }_i=()$.
• The verification algorithm simply checks that a candidate message
  $m_i^{\ast }$ has the same encryption as the original message, given in the public digest
  $d$,
  $V(\rho ,d,i,{\pi }_i,m_i^{\ast })=({m^{\ast }}^{k_{\text{pub}}}\text{ mod }h\stackrel{?}{=}d)$.

Partial opening is difficult again as the message is turned into an integer.

Efficiency: The space/communication efficiency of the digest

$d$ is a single large integer of size

$2s+1$-bits.

The computational efficiency of the commitment (and the verification) algorithm is the same as RSA encryption, which can be based on square & multiply (which involves

$\mathrm{O}(\log k_{\text{pub}})$ modulo

$h$ multiplications) or more specific tricks like those based on CRT (see article).

The scheme requires a trusted-setup algorithm, as

$p,q$ and

$\varphi (h)$ must be completely destroyed (so that no party knows them) after the public parameters are computed and published in order to ensure that the scheme is binding and hiding.

---

Remarks

Although this family consists of extremely basic (and admittedly boring) commitment schemes, it allowed us to establish an example for discussing commitment schemes of more complex variety, which will be continued in the upcoming chapters.

Further, since this family is at the base of the hierarchy, there is no reduction for simulating a simpler family of schemes, unlike those in the upcoming chapters.

Intro: A Hierarchical View of Cryptographic Commitment Schemes
Previous: Elements of Commitment Schemes
Next: Set Commitments