@schmittlauch @liaizon I know, they're Hash Tables after all. My initial application for them is going to be importing your existing friend lists from centralized services, and they do work well for this. For text-based search, one could split the query into words and search for each word as a tag, then intersect the resulting lists. This begs for some experimentation though.
@grishka Mozo et al. proposed that the infrastructure can already help with that: doi:10.1016/j.comcom.2007.08.035
But their approach may put you into trouble in MITM or hot spot scenarios.