Is there a category theoretic definition of a cryptographic commitment scheme?

Question

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 for any algorithm $\mathcal{A}$ that outputs two valid proofs $\pi, \pi' \in \Pi_{valid}$ we have $$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?

Answer 1

Answer from Dusko Pavlovic:

the question is a very nice case for categorical cryptography because the commitment schema seems like an extreme case of bad notations causing bad confusions. the use cases of the commitment schema that i am aware of (from naor to quantum) boil down to

DEF: a commitment schema is type T with three functions

** ct, dt : T—>T ** ot : TxT—>T

satisfying

** quations: ot(ct(w), dt(w)) = w and dt(ot(u,v)) = v ** sequrity: ct is a one-way (collision-free) function

USE: commitment protocols extend the basic schema:

** Alice commits w by announcing c=ct(w) ** Later Alice decommits by announcing c=dt(w) ** Bob verifies the commitment c=ct(ot(c,d))

[exercise: prove that the functional requirements imply c=ct(ot(c,d)). the first one suffices.]

EXAMPLES: a) ct(w) = H(w), dt(w) = w, ot(u,v) = v b) ct(w) = p(H(w)), dt(w) = w::q(H(w)), ot(u,v) = p(v) c) ct(w) = E(p(w), q(w)), dt(w) = p(w), ot(u,v) = v::D(v,u)

where

• H is a hash function
• p,q: T—>T and (-::-): TxT—>T give surjective pairing: p(x::y) = x, q(x::y)=y, and p(z)::q(z) = z
• E(x,D(x,y))=y and E(x,-): T—>T are one-way functions

the commitment schema that you describe in your math overflow question seems to be obtained by:

1. generalizing the decommitment test ct(ot(ct(w),dt(w)))=ct(w) to a predicate Verify(w,dt(w),ct(w))
2. assigning every variable in sight a different type w:M, ct(w):C, dt(w):Pi

while (1) may be justified by situations where checking equality may be hard, (2) seems just a matter of bad hygiene. this requirement in (1) that the committed source w must be disclosed reduces the use cases to instances of example (a) above. two things are achieved:

1)) it precludes the use cases of commitment where the source cannot be disclosed (eg the main quantum protocols), and 2)) confuses you into taking Pi = MxC (and then trying to encode the concept of one-way function by hardwiring that the commitment function must be injective up to a negligible chance of collisions).

so we have two definitions of commitment: A) (ct,dt,ot)-algebra + ct is one-way B) M-C-Pi-definition (katz-lindell?)

definition (A) is expressed in terms of my categorical crypto paper: a (ct,dt,ot)-algebra is a diagram, and the requirement that ct is one-way was there expressed simply by postulating a family of easy functions. ((my message last night was referring to a categorical framework for algorithmics of one-way functions. but all we need for security proofs of commitment schemas is an abstract family of easy functions.))

definition (B) can be reduced to (A) by generalizing from ot to Verify and by distinguishing the types C, M, and Pi. but if there are no compositions that separating the types prevents, this just obscures things.