A non-interactive protocol is provided for evaluating machine learning models such as decision trees. A client can delegate the evaluation of a machine learning model such as a decision tree to a server by sending an encrypted input and receiving only the encryption of the result. The inputs can be encoded as vector of integers using their binary representation. The server can then evaluate the machine learning model using a homomorphic arithmetic circuit. The homomorphic arithmetic circuit provides an implementation that requires fewer multiplications than a Boolean comparison circuit. Efficient data representations are then combined with different algorithmic optimizations to keep the computational overhead and the communication cost low. Related apparatus, systems, techniques and articles are also described.