In this paper, we attack the recent NIST submission Giophantus, a public key encryption scheme. We find that the complicated structure of Giophantus's ciphertexts leaks information via a correspondence from a low dimensional lattice. This allows us to distinguish encrypted data from random data by the LLL algorithm. This is a more efficient attack than previous proposed attacks.

In this paper, we prove that the degree of regularity of square systems, a subfamily of the HFE systems, over a prime finite field of odd characteristic q is exactly q and, therefore, prove that inverting square systems algebraically using Gröbner basis algorithm is exponential, when q = \Omega(n), where n is the number of variables of the system.

In this paper we analyze the Kahrobaei-Lam-Shpilrain (KLS) key exchange protocols that use extensions by endomorpisms of matrices over a Galois field proposed in \cite{Kahrobaei-Lam-Shpilrain:2014}. We show that both protocols are vulnerable to a simple linear algebra attack.

In this paper, we give an almost complete classication of toric surface codes of dimension less than or equal to 7, according to monomially equivalence. This is a natural extension of our previous work [YZ], [LYZZ]. More pairs of monomially equivalent toric codes constructed from non-equivalent lattice polytopes are discovered. A new phenomenon appears, that is, the monomially non-equivalence of two toric codes C P(10)7and CP(19)7 can be discerned on Fq, for all q  8, except q = 29. This sudden break seems to be strange and interesting. Moreover, the parameters, such as the numbers of codewords with dierent weights, depends on q heavily. More meticulous analyses have been made to have the possible distinct families of reducible polynomials.

In this paper, we consider the harmonic extension problem, which is widely used in many applications of machine learning. We formulate the harmonic extension as solving a Laplace-Beltrami equation with Dirichlet boundary condition. We use the point integral method (PIM) to solve the Laplace-Beltrami equation. The basic idea of the PIM method is to approximate the Laplace equation using an integral equation, which is easy to be discretized from points. Based on the integral equation, we found that traditional graph Laplacian method (GLM) may fail to approximate the harmonic functions in the classical sense. For the Laplace-Beltrami equation with Dirichlet boundary, we can prove the convergence of the point integral method. The point integral method is also very easy to implement, which only requires a minor modification of the graph Laplacian. One important application of the harmonic extension in machine learning is semi-supervised learning. We run a popular semi-supervised learning algorithm by Zhu et al. over a couple of well-known datasets and compare the performance of the aforementioned approaches. Our experiments show the PIM performs the best. We also apply PIM to an image recovery problem and show it outperforms GLM. Finally, on a model problem of Laplace-Beltrami equation with Dirichlet boundary, we prove the convergence of the point integral method.