Interpolation of the Discrete Logarithm in Finite Fields by Boolean Functions

Recently, Shparlinski proved several results on the interpolation of the discrete logarithm in finite prime fields by Boolean functions. In this extended abstract we present extensions to arbitrary finite fields of odd characteristic. More precisely, we sketch the proofs of some complexity lower bounds for Boolean functions representing the least significant bit of the discrete logarithm in a finite field.