In this paper, we describe privacy-preserving protocols for a scheduling service in eHealth applications. We are integrating our proposal into a pervasive home assistance system that allows patients or elderly people to stay longer at home. This pervasive eHealth system offers a multitude of services to its users, such as health monitoring, communication with caregivers, but also assigning requested tasks to appropriate caregivers. The scheduling mechanism that we propose protects sensitive information that is handled by the system. However, it still allows for a fair distribution of tasks and restricting the task assignment to caregivers with specific qualifications. Therefore, this service can be offered by a commercial company without fear for privacy issues.