Deep learning as a service (DLaaS) has been intensively studied to facilitate the wider deployment of the emerging deep learning applications. However, DLaaS may compromise the privacy of both clients and cloud servers. Although some privacy preserving deep neural network (DNN) based inference techniques have been proposed by composing cryptographic primitives, the challenges on computational efficiency have not been well-addressed due to the complexity of DNN models and expensive cryptographic primitives. In this paper, we propose a novel privacy preserving cloud-based DNN inference framework (namely, "PROUD"), which greatly improves the computational efficiency. Finally, we conduct extensive experiments on two commonly-used datasets to validate both effectiveness and efficiency for the PROUD, which also outperforms the state-of-the-art techniques.