A Computational Category-Theoretic Approach to Cryptography and Average-Case Complexity

Abstract

We study of cryptography and average-case complexity through the lens of what we call computational category theory, wherein we consider category-theoretic objects and relationships endowed with computational hardness properties. We show that such a computational category-theoretic approach provides many novel insights into the mathematical structure inherent to certain cryptographic primitives and reductions in average-case complexity:

• We show how to model cryptographic primitives as computational category-theoretic diagrams, where each
  such diagram is described using category-theoretic objects and relationships endowed with computational
  hardness properties. This yields a novel approach to understanding the mathematical structure that is inherent
  to any given primitive.
• We also prove that any “hard” family of problems with a certain type of randomized self-reduction implies
  the existence of a monoid equipped with a natural notion of one-wayness, thus demonstrating that some
  mathematical structure is inherent to the existence of these kinds of randomized self-reductions.
• We further extend these observations to a certain family of collision-resistant hash functions (CRHFs): we
  show that any CRHF where preimage resistance is reducible to collision resistance with a particular type of
  reduction also implies a one-way monoid. These statements prove that even certain Minicrypt primitives with
  “good” reductions also imply mathematical structure, which is (to our knowledge) a novel type of proof.