 Solution

Regard bit strings as the elementary abelian group $G=({\mathbb{Z}}_2{)}^n$ under bitwise exclusive or. The promise saysThus $f$ is constant exactly on the cosets of $H$ and distinct between them. Determining the hidden subgroup determines its nonzero element $p$, so this is Simon's problem as an instance of the hidden subgroup problem.