Private and secure service discovery via progressive and probabilistic exposure

The involvement of only the necessary users and service providers for service discovery in pervasive computing environments is challenging. Without prudence, users' and service providers; requests or service information, their identities, and their presence information may be sacrificed. We identify that the problem may be as difficult as a chicken-and-egg problem, in which both users and service providers want the other parties to expose sensitive information first. In this paper, we propose a progressive and probabilistic approach to solve the problem. Users and service providers expose partial information in turn and avoid unnecessary exposure if there is any mismatch. Although one or two bits of information are exchanged in each message, we prove that the process converges and that the false positive overhead decreases quickly. Experiments and hypotheses tests show that security properties hold. We implemented the approach and the performance measurements show that the approach runs efficiently on PDAs.