Institute of Information Science, Academia Sinica

In this talk, I will describe a generalization of the well-known problem of testing matrices equivalence: we are given two (square) matrices of size n, and we are asked to find two other matrices S and T such that TA=BS --- when they exist. This particulat problem is easy to solve. However, it becomes a lot more delicate if the two matrices A and B are replaced by two quadratic maps over the corresponding vector space. This new problem (the linear equivalence of quadratic maps) is known to be harder than Graph-Isomorphism, and its supposed hardness has been used to build public-key cryptographic schemes. In this talk, I will present the new algorithms I designed to solve various subcases of the problem, and I will discuss their cryptographic implications.