# RSA as an Hidden Subgroup Problem

the Hidden Subset 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 Problem is, given $$\mathbb{G}$$ and 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 the subgroup or to factorize the modulus.

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:

Let $$\mathbb{G} = \mathbb{Z}$$ and $$\mathbb{H} = \{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\}$$. So maybe some technical work has to be done to restrict the size of $$\mathbb{G}$$ to make it work. What do you think? (I am not sure, since the group operation involves $$m$$.)

Regards, Etsch