Optimal Polynomial Intersection and Leakage Resilient Secret Sharing

In this talk, I'll introduce two problems, tell you what they have to do with each other, and also share some recent progress on both. The first problem is Optimal Polynomial Intersection (OPI). OPI is a discrete optimization problem based on polynomials over finite fields: Given subsets S_0, ..., S_n of a finite field F_p, the goal is to find a low-degree polynomial f so that f(a_i) lies in S_i for as many i as possible, where a_1,...,a_n are fixed distinct elements of F_p. OPI was introduced recently in the context of quantum algorithms: in some parameter regimes, a quantum algorithm (Decoded Quantum Interferometry, or DQI), can find significantly better solutions than any known efficient classical algorithm. The second problem is Locally Leakage Resilient (LLR) Shamir Secret Sharing. This problem is also about polynomials over finite fields, but in a different context: suppose that each of n parties holds a Shamir share of some secret, which can be viewed as an evaluation of a low-degree (say, degree k-1) polynomial over F_p. The point of Shamir secret sharing is that any k parties can recover the secret, while any k-1 learn nothing about it. But what if each party leaks a single bit out of the approximately log(p) bits they are holding? Is the secret still secure?

It turns out that (somewhat surprisingly) there is a connection between these two problems, and that similar techniques can be used to make progress on both of them. In this talk, I'll describe the connection and our progress. The punchlines include improved quantum algorithms for OPI, as well as improved leakage-resilience guarantees for Shamir LLR.

This talk is based on joint work with Yihang (Kimi) Sun.