Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
$p$ doesn't have to be surjective. I don't really understand what you're asking for. What is a malleable morphism? And, for those of us not in the know, could you briefly explain what a cryptographic trapdoor function is? (Right now I can't read this question as anything other than "what are examples of homomorphisms" and this seems far too broad to me.) –  Qiaochu Yuan Apr 15 '11 at 15:58
It is my understanding that $p$'s surjectivity is important when we restrict the conversation to quotient maps, which is at least the context in which I learned the fact. I do not think it is true that if a set in the codomain is open (for some arbitrary topology on $A$) then the sets preimage is open in the domain - this fact only works if you specify the quotient topology on $A$. I could easily be mistaken... in any case this surjectivity isn't terribly important for my question. I have added a brief description of a cryptographic trapdoor function. I hope it helps. –  Ross Snider Apr 15 '11 at 16:20
Qiaochu: I am, in fact, asking for 'examples of homomorphisms' (although the people at MO apparently disagree with that terminology). On the MO post I made the comparison to Hellman (of Diffie-Hellman-Merkle public key exchange) asking his colleges for problems in math where it is easy to go in one direction but hard to invert (responses included discrete logarithms and factoring - this is one of the reasons why RSA is RSA and Elgamal is Elgamal today). I am looking for a very particular sort of morphism and am hoping that the wealth of experts from different areas of mathematics can weigh in. –  Ross Snider Apr 15 '11 at 16:25
Furthermore, it would be ironic to suggest closing this question as too broad; MO closed it as too localized... –  Ross Snider Apr 15 '11 at 16:31
@Ross: the homomorphism property does not require that $p$ be surjective, which is what I assumed you were asking about. I don't understand what irony has to do with whether this question should be closed: it is too broad in the sense that you are asking for a very general thing and too localized in the sense that you have a very specific application in mind. –  Qiaochu Yuan Apr 15 '11 at 16:33
show 5 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.