  Specialized worker profiles of crowdsourcing platforms may contain a large
amount of identifying and possibly sensitive personal information (e.g.,
personal preferences, skills, available slots, available devices) raising
strong privacy concerns. This led to the design of privacy-preserving
crowdsourcing platforms, that aim at enabling efficient crowd-sourcing
processes while providing strong privacy guarantees even when the platform is
not fully trusted. In this paper, we propose two contributions. First, we
propose the PKD algorithm with the goal of supporting a large variety of
aggregate usages of worker profiles within a privacy-preserving crowdsourcing
platform. The PKD algorithm combines together homomorphic encryption and
differential privacy for computing (perturbed) partitions of the
multi-dimensional space of skills of the actual population of workers and a
(perturbed) COUNT of workers per partition. Second, we propose to benefit from
recent progresses in Private Information Retrieval techniques in order to
design a solution to task assignment that is both private and affordable. We
perform an in-depth study of the problem of using PIR techniques for proposing
tasks to workers, show that it is NP-Hard, and come up with the PKD PIR Packing
heuristic that groups tasks together according to the partitioning output by
the PKD algorithm. In a nutshell, we design the PKD algorithm and the PKD PIR
Packing heuristic, we prove formally their security against honest-but-curious
workers and/or platform, we analyze their complexities, and we demonstrate
their quality and affordability in real-life scenarios through an extensive
experimental evaluation performed over both synthetic and realistic datasets.
