Remote deep learning paradigm enables to better leverage the power of deep neural networks in pervasive health monitoring (PHM) applications, especially by addressing the constrained client-side environment. However, remote deep learning in the context of PHM requires to ensure three properties: (1) meet the high accuracy requirement of the healthcare domain, (2) satisfy the client-side constraints, and (3) cope with the privacy requirements related to the high sensitivity of health data. Different privacy-preserving solutions for remote deep learning exit in the literature but many of them fail to fully address the PHM requirements especially with respect to constrained client-side environments. To that end, we propose PRIviLY, a novel privacy-preserving remote inference solution, designed specifically for the popular Fully Connected Deep Networks (FCDNs). PRIviLY avoids the use of encryption for privacy preservation of sensitive information, in order to fully prevent accuracy loss, and to alleviate the server-side hardware requirements. Besides, PRIviLY adopts a non-colluding two-server architecture, and leverages the linear computations of FCDNs along with reversible random perturbation and permutation techniques in order to preserve privacy of sensitive information, while meeting low overhead requirement of constrained client-sides. At the cloud server, efficiency evaluation shows that PRIviLY achieves an improvement ratio of 4 to more than 15 times for communication, and a minimum improvement ratio of 135 times for computation overhead. At the intermediate server, the minimum improvement ratio is at least more than 10,900 for computation, while for communication, the improvement ratio varies from 5 to more than 21 times. As for the client-side, PRIviLY incurs an additional overhead of about 27% in terms of communication, and between 16% and at most 27% in terms of computation. [ABSTRACT FROM AUTHOR]