Institute of Information Science Academia Sinica
Topic: Quadratic Maps Linear Equivalence
Speaker: Dr. Charles Bouillaguet (University of Versailles)
Date: 2012-07-09 (Mon) 10:30 – 12:00
Location: Auditorium at CITI Building
Host: Bo-Yin Yang

Abstract:

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.