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
    $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.)2011-04-15
  • 0
    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.2011-04-15
  • 0
    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.2011-04-15
  • 0
    Furthermore, it would be ironic to suggest closing this question as too broad; MO closed it as too localized...2011-04-15
  • 1
    @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.2011-04-15
  • 0
    Qiaochu: Yes, I understand. There is something more to the homomorphism than just the property of any function commuting the the union and intersection. *If* the function is also surjective and we define the codomain to have the the quotient topology *then* it is true that open/closed sets $U \subset A \to p^{-1}(U)$ is open/closed in $X$. That is the homomorphism respects *more* with surjective $p$. The hope is that my very specific application isn't too specific when I ask a general question about it and that the general question isn't too broad when answers need apply to specific constraint2011-04-15
  • 0
    @Ross: that property is independent of the homomorphism property (which I am using to refer to the fact that unions and intersections are preserved). Is this open/closed preservation property actually relevant to the application you have in mind? (The fact that I cannot tell this from your question tells you something about its lack of precision.)2011-04-15
  • 0
    Qiaochu: Yes, the open/closed preservation property is relevant to the application I have in mind. For certain topologies on certain sets X, the union of sets acts like an OR function and the intersection of sets acts like an AND function (consider the cofinite topology on an infinite set X and 'true' sets = 'open' sets, 'false' sets = 'closed' sets). Then one could "obscure" the sets by a cryptographic trap door function and hand them to a third party who (in theory) could not easily tell which obscured sets are open and closed in the quotient topology. However they could still take set...2011-04-15
  • 0
    ... unions and intersections, effectively doing computations without knowing the results or intermediary values of said computation. The first party can easily tell the computation result - they apply the trapdoor information and test whether the preimage of the resultant set is open in the original topology. This would allow "Fully Homomorphic Encryption" (https://secure.wikimedia.org/wikipedia/en/wiki/Homomorphic_encryption) however in this case openness/closedness testing in a quotient topology is easy for the third party. I am looking for other homomorphisms in mathematics with similaritie2011-04-15
  • 0
    I will try to improve the wording of the question.2011-04-15

0 Answers 0