  It has been suggested that the baseline scenario of collisionless cold dark
matter over-predicts the numbers of satellite galaxies, as well as the dark
matter (DM) densities in galactic centers. This apparent lack of structure at
small scales can be accounted for if one postulates neutrino-DM and DM-DM
interactions mediated by light O(MeV) force carriers. In this letter, we
consider a simple, consistent model of neutrinophilic DM with these features
where DM and a "secluded" SM-singlet neutrino species are charged under a new
$U(1)$ gauge symmetry. An important ingredient of this model is that the
secluded sector couples to the Standard Model fields only through neutrino
mixing. We observe that the secluded and active neutrinos recouple, leading to
a large relic secluded neutrino population. This relic population can prevent
small-scale halos from collapsing, while at same time significantly modifying
the optical depth of ultra-high-energy neutrinos recently observed at Icecube.
We find that the bulk of the parameter space accommodating an (a)symmetric
thermal relic has potentially observable consequences for the IceCube high
energy signal, with some of the parameter ranges already ruled out by the
existing data. Future data may confirm this mechanism if either spectral
absorption features or correlations with nearby sources are observed.
