2:00 pm, Seminar Hall
Polynomial equivalence over rings
Ramarathnam Venkatesan
Cloud + AI, Microsoft.
25-01-19

---

Abstract

A multivariate polynomial f(x) over n variables is said to be equivalent to g(x) over a ring R if there is nonsingular matrix A with entries from R such that g(x) = f(Ax). Kayal considered this problem over algebraically closed fields and showed that one can compute A in polynomial time using an elegant randomized algorithm that relied on factoring polynomials. We show that over the integers modulo N = pq and show that computing A is tantamount to computing the automorphism group Aut(f) which in turn allows us to factor N. We indicate cryptographic applications of this newly formulated trapdoor function based on polynomial projections. With Jonathan Lee (Microsoft Research) and Sriram Raghuraman (MIT)