2
$\begingroup$

I recently posted this question on mathoverflow and it was closed as being too localized. I am hoping to more precisely say what I mean here.

I recently learned, through my Topology coursework, that for any set $\mathbb{X}$, subset $A \subset \mathbb{X}$ and function $p : \mathbb{X} \rightarrow A$ that $p^{-1}(\cup_{\alpha \in \Lambda}\mathcal{U_\alpha}) = \cup_{\alpha \in \Lambda}{(p^{-1}(\mathcal{U_\alpha}))}$ $p^{-1}(\cap_{\alpha \in \Lambda}\mathcal{U_\alpha}) = \cap_{\alpha \in \Lambda}{(p^{-1}(\mathcal{U_\alpha}))}$ for indexed collections $\Lambda$ of subsets $\mathcal{U}$ in the range $A$.

Furthermore, if we restrict ourselves to surjective functions $p$ we get something stronger. In a topological setting such surjective functions define a "quotient map" and an additional morphism can be seen. An open set $\mathcal{U} \subset A$ is open in $A$ iff $p^{-1}(\mathcal{U})$ is open in $\mathbb{X}$. The same property is true for closed sets.

What is interesting to me is that for any surjective function we get this morphism behavior. In my particular application I am looking for morphisms of which I can replace functors with cryptographic trapdoor functions. My application is to take these morphisms and to try to make them homomorphic to boolean algebra. (In the case of topology we can interpret "open sets" as "true" and "closed sets" as "false" for certain topologies on certain sets).

I am looking for examples similar to this anywhere in mathematics. The key property which would make any example more interesting is if there are very few restrictions stated for the functor $p$.


I have been asked to characterize cryptographic trapdoor functions. A function is a cryptographic trap door if it is difficult to compute (e.g. has an asymptotic lower bound sub-exponentially in the length of the input in the average case; here meaning the number of digits it takes to specify the element of the domain) without some secret bits of information $y$ and easy to compute (number of operations are upper bounded by a polynomial asymptotically in the size of the input). The canonical example of a trapdoor function is the RSA Problem, which is believed to be hard without the prime factorization of a semi-prime and easy with.

  • 0
    I will try to improve the wording of the question.2011-04-15

0 Answers 0