Wednesday, October 30, 2013

The l-Hensel Lifting Assumption

In one of my previous posts, i talked about the possibilities to insert backdoors in prime numbers (beside the property that $p-1$ is smooth). One of the potential ideas for a backdoor was to generate primes that allow an easy lift from $\mathbb{Z}/p$ to $\mathbb{Z}/{p^2}\mathbb{Z}$. But under the consideration of the $l$-Hensel Discrete Logarithm Assumption, this should be actually hard in the general case.

Because if you could successfully lift the element $e\equiv g^x\pmod{p}$ to $E\equiv g^x\pmod{p^2}$, then you could, as long as $x < \mathsf{ord}_p(g) = r$, compute
\begin{align*}
\left(g^x\right)^{r} \equiv (g^{r})^x \equiv (1+p\lambda)^x \pmod{p^2}
\end{align*}
Next, the Binomial Theorem gives
\begin{align*}
(1+p\lambda)^x \equiv \sum^x_{i=0}\binom{x}{i}p^i\lambda^i \equiv 1 + xp\lambda\pmod{p^2}
\end{align*}
and hence
\begin{align*}
\frac{E^{r} - 1}{p\lambda} \equiv x \pmod{p}
\end{align*}


So, if you are able to compute the lifted element $E$, you could compute the discrete logarithm $x$. However, as also mentioned in the $l$-Hensel Discrete Logarithm Assumption, it is not allowed to be $g^r \equiv 1\pmod{p^2}$. Because in that case, you could indeed compute $E$. But don't get exited, it does not help you to get $x$.

To see this, assume again $e\equiv g^x\pmod{p}$ and this time $g$ is also a $r$-th root of unity in $\mathbb{Z}/{p^2}\mathbb{Z}$. Note that such primes are called Generalized Wieferich Primes or Base-g Wieferich Primes. So you have
\begin{align*}
\left(g^x\right)^{r} \equiv (e+pX)^{r} \equiv E^r \equiv 1 \pmod{p^2}
\end{align*}
The integer $e$ is known, but we want to have $X$. We could further write
\begin{align*}
1 \equiv (e+pX)^r & \equiv \sum^{r}_{i=0}\binom{r}{i}e^{r-i}p^iX^i \pmod{p^2}\\
& \equiv e^{r} + re^{r-1}pX \pmod{p^2}
\end{align*} so
\begin{align*}
\frac{1-e^r}{re^{r-1}p} \equiv X \pmod{p}
\end{align*}
and hence we get $E = e + pX$. But in that case, you can not apply the previous algorithm to compute $x$, since we are in a group of order $r$ with $r|(p-1)$ and hence $\left( g^x \right)^r \equiv 1$, so $\lambda = 0$ which cancels the possibility to get $x$.
$E$ can be computed even simpler without the need to involve the Binomial Theorem. It holds that $$e^p \equiv E \pmod{p^2}$$ Based on Fermat Little Theorem $E$ must be $E\equiv e\pmod{p}$ And since $E$ is a $p$-th residue, it must hold $E^{p-1}\equiv 1\pmod{p^2}$. And since $E$ is the unique $p$-th residue with $E\equiv e\pmod{p}$ it is completely determined by $e^p\pmod{p^2}$.

Could the setup $g,p$ whereof $p$ is a $g$-base Wieferich Prime be utilized as a backdoor, i.e. an unsecure setup for a cryptosystem?

No comments:

Post a Comment