  We introduce a simple tool that can be used to reduce non-injective instances
of the hidden shift problem over arbitrary group to injective instances over
the same group. In particular, we show that the average-case non-injective
hidden shift problem admit this reduction. We show similar results for
(non-injective) hidden shift problem for bent functions. We generalize the
notion of influence and show how it relates to applicability of this tool for
doing reductions. In particular, these results can be used to simplify the main
results by Gavinsky, Roetteler, and Roland about the hidden shift problem for
the Boolean-valued functions and bent functions, and also to generalize their
results to non-Boolean domains (thereby answering an open question that they
pose).
