Embodiments enable privacy protection for increasing service anonymity. A method comprises receiving a service discovery frame from a wireless device operating synchronously in a neighbor awareness network cluster, including scrambled values associated with service names, each of the scrambled values being a hash of an argument comprising the service name and a component value selected based on a current synchronous time shared with the wireless device. The received scrambled values are compared with scrambled values associated with maintained service names, each being a hash of an argument comprising a valid service name of a known service and a component value selected based on the current synchronous time. If any of the received scrambled values satisfies the comparison with a scrambled value associated with the service name, then the received scrambled value is determined to be associated with the known service.