# RSA as a hidden subgroup problem

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)

• Link to the question on cstheory? Aug 3 '20 at 10:55