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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.