The Hidden Subgroup Problem (HSP) covers several known problems (e.g. Integer Factorization Problem, Discrete Logarithm Problem) as a special case:
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 Hidden Subgroup Problem is, given $\mathbb{G}$ and (oracle-)access to the function $f$, to determine a generating set for the subgroup $\mathbb{H}$.
I found several papers which show how to instantiate the involved groups and functions, for example in case of the Integer Factorization Problem: $$\mathbb{G} = \mathbb{Z}^+_{\varphi(N)}; \mathbb{H} = \langle r\rangle^+; S = \mathbb{Z}^*_N, f(x)=g^x\pmod{N}$$ whereof the integer $r$ is the order of the multiplicative group generated by $g$.
I am trying to find a direct HSP approach to the RSA problem, without to find the order of a subgroup or to factorize the modulus by any other methods.
RSA Problem: Given an RSA modulus $N$ and a public exponent $e$ and an integer $C$, find $m$ such that $m^e \equiv C \pmod{N}$
I came up with the following solution, but i am not sure if it is valid according to the definition of the HSP, since it contains $m$, the target integer, in the description of the group operation.
Let $\mathbb{G} = (\mathbb{Z},\circ_m)$ and $\mathbb{H} = \{0, m, m+N, m+2N, m+3N,\ldots\}$, $S = \mathbb{Z}^*_N$ as well as $f(x) = x^e\pmod{N}$. The group operation that is defined on $\mathbb{G}$ is $\circ_m(a,b) := a+b-m$. So $\circ$ makes $\mathbb{H}$ a subgroup of $\mathbb{G}$ (neutral element is $m$ and inverse is $a^{-1} = 2m-a$). And $f$ can distinguish $N$ cosets of $\mathbb{H}$: $$c\mathbb{H} = \{m+c, m+c+N, m+c+2N,\ldots\}$$. 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 also on cstheory.stackexchange (here) but did not get an answer)
