In Shoup's proof of the hardness of discrete log in the generic group in this paper, he mentions that:

At any step in the game, the algorithm has computed a list $F_1,\dots,F_k$ of linear polynomials in $Z/p^t[X]$ along with a list of values $z_1,\dots,z_k$ in $Z/s$, and a list $\sigma_1,\dots,\sigma_k$ of distinct values in $S$.

The algorithm is initially given the encodings of $1,x$ and access to the group operation + inverses so it is clear that anything the algorithm computes can be expressed as a linear polynomial in $Z/n[X]$, where $n=p^t s$. However, I don't see how this breaks down into a linear polynomial in $Z/p^t[X]$ and a constant in $Z/s$.


1 Answer 1


$n$ and $p^t$ are coprime numbers. Then, we can use the Chinese remainder theorem to deduce a ring isomorphism $\phi$ from $\mathbb{Z}_n$ to $\mathbb{Z}_s\times \mathbb{Z}_{p^t}.$

And $\phi$ is just $y \mapsto (y \mod s, y \mod p^t).$

In the proof, the value of $(x\mod s)$ is chosen uniformly at random at the beginning of the game : it's $z_2$ in the paper. But $x \mod p^t$ is written as the indeterminate $X$ by the challenger (it's $F_2$). Because $1 \mod s = 1$ and $1 \mod p^t =1$, $(z_1,F_1)=(1,1).$

Then for all the new elements, they are written as a linear combination of $x$ and $1$ in $\mathbb{Z}_n$ and also (by using the chinese remainder theorem) as a linear combination of $(z_2, X)$ and $(1,1)$ in $\mathbb{Z}_n$.

To compute the new coefficients for the $k^{th}$ element which is decomposed as $\lambda_1 \cdot 1 + \lambda_x \cdot x$ in $\mathbb{Z}_n$, you have to use the ring isomorphism $\phi.$

$$ \phi(\lambda_1 \cdot 1 + \lambda_x \cdot x) = \phi(\lambda_1 \cdot 1) + \phi(\lambda_x \cdot x) = \phi(\lambda_1) +\phi(\lambda_x) \cdot(z_2, X) $$

$$=(\lambda_1 \mod s, \lambda_1 \mod p^t) + (\lambda_x \cdot z_2 \mod s, (\lambda_x \mod p^t)\cdot X)$$ $$= ((\lambda_1 +\lambda_x \cdot z_2) \mod s, \lambda_1 \mod p^t +(\lambda_x \mod p^t)\cdot X) $$

We deduce that $z_k=(\lambda_1 +\lambda_x \cdot z_2) \mod s$ and $F_k =\lambda_1 \mod p^t +(\lambda_x \mod p^t)\cdot X).$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.