On the hidden shifted power problem
(joint work of Jean Bourgain, Moubariz Garaev and Sergei Konyagin)
Igor Shparlinski, Macquarie University
10 de febrero, 2012, 12:00 h., Sala Naranja ICMAT (cartel).
Abstract. We consider the problem of recovering a hidden element s of a finite field {tex}F_q{/tex} of {tex}q{/tex} elements from queries to an oracle that for a given {tex}x \in F_q{/tex} returns {tex}(x+s)^e{/tex} for a given divisor {tex}e|q-1{/tex}. This question is motivated by some applications to pairing based cryptography. Using Largange interpolation one can recover s in time {tex}ep^{o(1)}{/tex} on a classical computer. In the case of {tex}e = (q - 1)/2{/tex} an efficient quantum algorithm has been given by W. van Dam, S. Hallgren and L. Ip. We describe some techniques from additive combinatorics and analytic number theory that lead to more efficient classical algorithms than the naive interpolation algorithm, for example, they use substantially fewer queries to the oracle. We formulate some questions and discuss whether quantum algorithms can give further improvement.