I'm trying to come up with a composeable framework for cryptographic commitment schemes, where inclusion proofs can be combined in different ways. I'm thinking this can be done with category theory, which is known for being able to describe how to combine things. The following is what I have so far, with my concrete questions at the bottom.

Cryptographic commitment schemes

A cryptographic commitment scheme is roughly the following (omitting security parameters and non-determinism):

• A set $\mathcal{M}$ of messages that can be commited to
• A set $\mathcal{C}$ of commitments
• A set $\mathcal{\Pi}$ of proofs

And algorithms

$\require{AMScd}$ \begin{CD} \mathcal{M} @>\mathsf{Commit}>> \mathcal{\Pi} \times \mathcal{C}\\ \\ \mathcal{M} \times \mathcal{\Pi} \times \mathcal{C} @>\mathsf{Verify}>> \Omega \end{CD}

such that the following diagram commutes:

Here, $\Omega$ is the set $\{True, False\}$.

The commutative diagram just says that the $\mathsf{Commit}$ algorithm produces commitments with proofs that verifies with the commitment and message.

Simplifying

We can simplify the above construction by requiring that each proof comes with the corresponding message and commitment. Then, a commitment scheme consists of a diagram of algorithms

such that $p_{\mathcal{M}} \circ \mathsf{Commit} = id_{\mathcal{M}}$ and such that the diagram

\begin{CD} \mathcal{M} @>\mathsf{Commit}>> \Pi\\ @VVV @VV\mathsf{Verify}V \\ * @>True>> \Omega \end{CD}

commutes.

Simplifying more

Abstracting even more, since we are only really interested in the subset $\Pi_{valid} \subset \Pi$ consisting of the valid proofs, we can define a commitment scheme to be a diagram of algorithms

such that $p_{\mathcal{M}} \circ \mathsf{Commit} = id_{\mathcal{M}}$. In category theory language, this is just a span plus a section of the left morphism in the span. Here, the verify algorithm is not part of the definition. Instead, we just say that all elements of $\Pi_{valid}$ are valid by definition.

Binding property

A good commitment scheme should satisfy a binding property. Informally, using our last definition above, we say that a commitment scheme is (computationally) binding if it is computationally infeasible to constructfor any algorithm $\mathcal{A}$ that outputs two valid proofs $\pi, \pi' \in \Pi_{valid}$ such that $p_{\mathcal{M}}(\pi) \neq p_{\mathcal{M}}(\pi')$ andwe have $p_{\mathcal{C}}(\pi) = p_{\mathcal{C}}(\pi')$$$p_{\mathcal{C}}(\pi) = p_{\mathcal{C}}(\pi') \Rightarrow p_{\mathcal{M}}(\pi) = p_{\mathcal{M}}(\pi')$$ with overwhelming probability.

Generalizations

It is often the case that $\mathcal{M}$ and/or $\mathcal{C}$ have more structure than just being sets. For instance, an authenticated dictionary over a set $\mathcal{K}$ of keys and a set $\mathcal{V}$ of values can be described as a commitment scheme where $\mathcal{M}$ is the set of all subsets of $\mathcal{K} \times \mathcal{V}$ where the keys are distinct. In this case, $\mathcal{M}$ inherits the poset structure on $\mathcal{P}(\mathcal{K} \times \mathcal{V})$. This suggests that we should generalize from spans between sets to profunctors between posets (or more generally between categories).

Questions

Question 1:

While the correctness property of a commitment scheme is easy to define categorically, the binding property is not. Is there a suitable category which hides the dirty details of PPT algorithms, security parameters, non-determinism, etc, where the binding property can be stated in purely categorical terms?

Question 2:

The most basic way to construct a commitment scheme is with a hash function. A hash function is similar to an injective function, in that it is computationally infeasible to find two elements that maps to the same output. If we have a suitable category (see question 1), is a hash function just a monomorphism in this category?