Reduction from non-injective hidden shift problem to injective hidden shift problem

Understand

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.