Incomplete character sums over finite fields and their application to the interpolation of the discrete logarithm by Boolean functions. (English) Zbl 0998.11070

The paper provides lower bounds on the degree and the sparsity of a Boolean function representing the rightmost bit of the discrete logarithm for almost all nonzero elements of a finite field. The proofs are based on a new upper bound for incomplete character sums over finite fields, which is established by a method due to H. Niederreiter and I. E. Shparlinski [Math. Comput. 70, 1569-1574 (2001; Zbl 0983.11048)].


11T23 Exponential sums
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
94A60 Cryptography
11Y16 Number-theoretic algorithms; complexity


Zbl 0983.11048
Full Text: DOI