The high-energy astrophysical neutrinos detected by IceCube, with TeV-PeV energies, allow us to test neutrino physics in new energy and distance scales. One possibility is looking for new interactions between neutrinos and matter whose existence would ordinarily be too feeble to detect, except at high neutrino energies. We focus on well-motivated, economical new interactions introduced by gauging lepton-number symmetries that already exist in the Standard Model, Le-Lmu, Le-Ltau, and Lmu-Ltau. They introduce a new Z' boson that, if light, mediates a long-range potential between neutrinos and distant matter, separated by distances of up to gigaparsecs. This potential can significantly alter the oscillation probabilities of high-enery neutrinos en route to Earth and, as a result, also their flavor composition, i.e., the relative number of neutrinos of each flavor in the incoming flux. The high energies and long propagation distances of the IceCube neutrinos allow us to probe unexplored regions of the parameter space: tiny Z' masses, of 10-10-10-35 eV, and tiny adimensional couplings with the Z', of 10-24-10-35. We present refined constraints for Le-Lmu and Le-Ltau, and new limits on Lmu-Ltau, and projections, based on the measurement of flavor composition in IceCube and its planned upgrade, IceCube-Gen2.