Giophantus distinguishing attack is a low dimensional learning with errors problem (Q5918198)

Giophantus is a public-key encryption scheme based on nonlinear indeterminate equations and it has continously evolved since 2004. It was submitted to the First Round Candidate Algorithms of NIST Post-Quantum Cryptography Standardization in 2017. There are several robustness criteria for ciphering protocols, e.g. indistinguishability of cipher texts with respect to uniform random data, and indistinguishability under chosen plaintext attack (IND-CPA) (given two plain messages and the cipher text corresponding to one of them, it cannot effectively be distinguished which is the encrypted plain text). In the reviewed paper a successful attack to Giophantus is reported, based on lattice reduction instead of statistical analysis. In a rather general way, let \(q\) be a prime power and \(F_q\) be the Galois field of order \(q\). Given \(n\), let \(R_{qn}=F_q[T]/(T^n-1)\). The message space is \(R_{qn}\) and the cipher space is \(R_{qn}(X,Y)\). The private keys are points \((u_x(T),u_y(T))\in R_{qn}^2\) and the corresponding public keys are polynomials \(p(X,Y)\in R_{qn}(X,Y)\) such that \(p(u_x(T),u_y(T)) = 0\). Thus the problem to recover a private key given a public key, is the so called Section Finding Problem, with no known solver in polynomial time, even for polynomials of degree 1, with respect to \(X\) and \(Y\). For a given message \(m(T)\), there are chosen a randomly chosen polynomial \(r(X,Y)\in R_{qn}(X,Y)\) and a ``small'' polynomial \(e(X,Y)\in R_{qn}(X,Y)\) (the involved polynomial coefficients in \(e(X,Y)\) have in turn coefficients in \(\{0,1,2,3\}\)). Then the cipher text is the polynomial \(c(X,Y) = p(X,Y)\,r(X,Y)+4e(X,Y)+m(T)\). In order to decrypt, the message is recovered as \(m(T) = c(u_x(T),u_y(T))\bmod 4\). By applying the homomorphism \(R_{qn}\to F_q\), consisting in polynomial evaluation at point \(1\in F_q\), and by expanding the involved polynomials the coefficients will determine an equation \(\mathbf{c} = P\mathbf{r} + 4\mathbf{e}\). Hence, in order to decide whether \(\mathbf{c}\) corresponds indeed to a cipher text it is enough to decide whether this last equation has solutions \(\mathbf{r}\) and \(\mathbf{e}\), with \(\mathbf{e}\) small. This problem is an instance of Learning With Errors (see: \textit{O. Regev} [J. ACM 56, No. 6, Article No. 34, 40 p. (2009; Zbl 1325.68101); ANTS-IX, Lect. Notes Comput. Sci. 6197, 3 (2010; Zbl 1231.94055)]), and for the resulting instances, the problem can be solved probabilistically by the lattice basis reduction algorithm LLL. Initially, the authors survey several attacks performed against Giophantus with different success levels. Then the attack is used to break IND-CPA and to distinguish cipher texts from uniform random data.