RSA as Hidden Subgroup Problem

▍The Hidden Subgroup Problem is an important problem from Computer Science / Mathematics and actually covers several well known problems as a special case. The formal statement of the problem is:

Definition [Hidden Subgroup Problem (HSP)] Let $\mathbb{G}$ be a group and $\mathbb{H}$ an unknown subgroup of $\mathbb{G}$, i.e., $\mathbb{H} \leq \mathbb{G}$. Let $S$ be any set and $f$ be a function that maps the group elements of $\mathbb{G}$ to $S$, i.e., $f: \mathbb{G} \rightarrow S$. The function $S$ has the special property that it can distinguish cosets of $\mathbb{H}$: $$ f(e_1) = f(e_2) \Leftrightarrow e_1\mathbb{H} = e_2\mathbb{H} $$ The Problem is, given $\mathbb{G}$ and access to the function $f$, to determine a generating set for the subgroup $\mathbb{H}$ ∎ 

The notation $e\mathbb{H}$ denotes the coset $$e\mathbb{H} = \left\{eh | h \in \mathbb{H}\right\}$$. Problems that can be described as an instance of the HSP are for example:

1. Integer Factorization Problem
2. Discrete Logarithm Problem
3. Shortest Vector Problem
4. Deutsch Problem
5. Simon's Problem

and probably many more. The definition of the HSP above seems very abstract, but the subgroup $\mathbb{H}$ actually covers the usual integers of interest, e.g. divisors of $\varphi(N)$ in case of the Factorization Problem or multiples of the exponents in question in case of the Discrete Logarithm Problem. Shors Algorithm is a special instance of an HSP-Solver that finds the period of the function $g^x \pmod{N}$, i.e., it finds divisors of $\varphi(N)$. However, his algorithm only works in the ablian case. How to solve the HSP efficiently for non abelian groups is not known, also for quantum computers. The Shortest Vector Problem is a hard problem for quantum computers. So it is no surprise, that the reduction from SVP to HSP brings into play a non abelian group, the dihidral group.

Let us take a closer look at the first two problems and how they translate to a HSP. Therefore, we restate these two problems how they are usually defined:

Definition [Integer Factorization Problem (IFP)] Given an integer $N$, an integer $g$ that is co-prime to $N$. Let $\langle g \rangle^*$ be the subgroup of $\mathbb{Z}^*_N$ generated by $g$ of size $r$. Find a non-trivial factor of $N$ ∎

Definition [Discrete Logarithm Problem (DLP)] Given a multiplicative cyclic group $\langle g \rangle^*$ of size $N$ and an integer $r \in \langle g \rangle$. Find an integer $e \in \{0,1,\ldots,N-1\}$ such that $g^e = r$ ∎

Then we get the following instantiations of $\mathbb{G},\mathbb{H},S$ and $f$:

Problem	$\mathbb{G}$	$\mathbb{H}$	$S$	$\mathbb{f}$
IFP	$\mathbb{Z}^+_{\varphi(N)}$	$\langle r \rangle^+$	$\mathbb{Z}^*_N$	$f(x) = g^x \pmod{N}$
DLP	$\mathbb{Z}^+_N\times \mathbb{Z}^+_N$.	$\langle (e,1) \rangle^+$.	$\langle g \rangle^*$.	$f(x,y) = g^xr^{-y}$
	.	.	.	.

Note that for the IFP, it holds for any integer $e \in \langle r\rangle^+$ that $f(e) = 1\pmod{N}$, so we know that $r | \varphi(N)$. Likewise, for the DLP, it is $(v_1,v_2) \in \langle (e,1) \rangle^+$ so we get $$f(v_1,v_2) = g^{v_1}r^{-v_2} = g^{v_1}g^{-ev_2} = g^{ke}g^{-ek} = 1$$ So $f$ obviously distinguishes cosets of $\mathbb{H}$. E.g. for the IFP for each coset $e\mathbb{H}$, $e \in \mathbb{G}$ it is $x \in e\mathbb{H}$, $f(x) = g^e\pmod{N}$. Hence each coset maps a unique integer in $S = \mathbb{Z}^*_N$.

Lets make a small numerical example: Let $N=15 = 3\cdot 5$. It is $\varphi(15) = 8$. We choose $g = 7$ so $\langle 7 \rangle^* = \{7,4,13,1\}$ hence $r = 4$. It is $\mathbb{G} = \mathbb{Z}^+_8 = \{0,1,2,3,4,5,6,7\}$ and $\mathbb{H} = \langle r\rangle^+ = \{0,4\}$ is a subgroup of $\mathbb{G}$. The function $f$ is $7^x \pmod{15}$ and $S = \{1,2,4,7,8,11,13,14\}$. The unique cosets of $\mathbb{H}$ are

1. $\{0,4\}$ so $f(0) = f(4) = 1\pmod{15}$
2. $\{1,5\}$ so $f(1) = f(5) = 7\pmod{15}$
3. $\{2,6\}$ so $f(2) = f(6) = 4\pmod{15}$
4. $\{3,7\}$ so $f(3) = f(7) = 13\pmod{15}$

and are distinguishable by $f$.

RSA as Hidden Subgroup Problem

Definition [RSA Problem] Given an RSA modulus $N$ and the public exponent $e$ and an integer $C$, find $m$ such that $m^e \equiv C\pmod{N}$ ∎

As far as i know, the RSA Problem has never been formulated as a HSP, so i came up with the following solution: 

1. $\mathbb{H} = \{m, m+N,m+2N,\ldots\}$ 
2. $\mathbb{G} = \mathbb{Z}$ whereof the group operation is $\circ_m(a,b) := a+b - m$. With this operation $\mathbb{H}$ is indeed a subgroup of $\mathbb{G}$ (Notice that the neutral element is $m$ and the inverse of an element is $a^{-1} = 2m-a$ (for $m=0$ we get the normal addition)). 
3. We set $S = \mathbb{Z}^*_N$.  
4. The function $f(x) = x^e\pmod{N}$. 

I am not sure if the definition of the group $\mathbb{G}$ is valid due to the involvement of the integer $m$. $f$ can distinguish cosets

$$c\mathbb{H} = \{m+c, m+c+N, m+c+2N, \ldots\}$$

for two different $c$. 

Question: Does the term "given a group $\mathbb{G}$" forbid the definition of a valid but non accessible group operation? Is it enough that someone could, even not knowing $m$, compute $$\circ_m(a,b) - \circ_m(u,v) = a+b-u-v$$ I asked this question already several people, but no one actually knew an answer.