Disclosed is a method for address privacy protection for a first wireless device sharing a privacy key with a second wireless device. In the method, a first resolution tag is generated at the first wireless device using a pseudo-random function with the seed value and the privacy key as input arguments. The privacy key is only known to the first and second wireless devices. A privacy address is generated for the first wireless device based on the seed value and the first resolution tag. A packet is transmitted from the first wireless device to the second wireless device. The packet includes the privacy address and the first resolution tag.