0
$\begingroup$

Sorry if my question is trivial. My question is related to a post "Paillier Homomorphic encryption to calculate the means" where a member suggests Lagrange Gauss Reduction Algorithm for reducing a decrypted value to a rational number. How to use Lagrange Gauss Reduction Algorithm for reducing numbers? Here is the link to the original post: Paillier Homomorphic encryption to calculate the means.

$\endgroup$
1
$\begingroup$

Lagrange-Gauss algorithm can also be seen as LLL in dimension 2. Here is an implementation using GP/Pari:

\\ Given A modulo N, it returns a fraction u/v s.t. A = u/v (mod N)
Gauss(A,N) = {
  local(L,L3);

  L = [1,0;lift(A),N];
  L3 = L*qflll(L);

  return(L3[2,1]/L3[1,1]);
}

EDIT: Consider the lattice defined by the two column vectors $\begin{pmatrix}1\\A\end{pmatrix}$ and $\begin{pmatrix}0\\N\end{pmatrix}$. The vectors in the lattice are: $$\alpha \begin{pmatrix}1\\A\end{pmatrix} + \beta \begin{pmatrix}0\\N\end{pmatrix} = \begin{pmatrix}\alpha\\ \alpha A + \beta N\end{pmatrix}$$ As we are in dimension 2, LLL will return the shortest (non-zero) vector in the lattice.

Let's call $$\vec{v} := \begin{pmatrix}v_1\\v_2\end{pmatrix} = \begin{pmatrix}\alpha^*\\ \alpha^* A + \beta^* N\end{pmatrix} \in \mathbb{Z}^2$$ the vector returned by LLL: $v_1$ and $v_2$ are small. Clearly, we have $$v_2 = \alpha^* A + \beta^* N \equiv \alpha^* A \equiv v_1 A \pmod N$$ and thus $$A \equiv \frac{v_2}{v_1} \pmod N$$ with $v_1$ and $v_2$ small.

$\endgroup$
  • $\begingroup$ Can you elaborate this implementation a bit more as I am not used to GP/Pari or can you suggest some material about this algorithm? $\endgroup$ – Mosen Feb 2 '18 at 13:04
  • $\begingroup$ @Mosen: See the EDIT. Does it answer your question? $\endgroup$ – user94293 Feb 2 '18 at 17:38
  • $\begingroup$ Now I understand the algorithm. My question is about the implementation code you have given above in which some terms (lift(A), qflll) are not clear to me as it is written in GP/Pari. I am more familiar with MATLAB. Anyhow nice explanation. $\endgroup$ – Mosen Feb 3 '18 at 2:59
  • $\begingroup$ can you please explain the programming terms lift(A), qflll(L), and L3 in the above implementation? $\endgroup$ – Mosen Feb 5 '18 at 4:19
  • $\begingroup$ See pari.math.u-bordeaux.fr $\endgroup$ – user94293 Feb 5 '18 at 5:22

Your Answer

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

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