The paper studies the potential of Chebyshev polynomials in the context of privacy preserving data mining: First the secure computation of the mean in a two-party scenario, second the secure distributed learning of a decision tree in both the two-party and the multi-party case. The investigations demonstrate that considerable gains in efficiency can be achieved in the design of the protocols owing to the better approximation quality of the truncated Chebyshev series in comparison to the truncated Taylor series.