A method performed by a first wireless communication device for exchanging identifiers, ID, with a second wireless communication device, comprising: sending a rolling proximity identifier A associated with the first wireless communication device to the second wireless communication device, wherein the rolling proximity identifier A is a privacy-preserving identifier that is exchanged with other wireless devices that come within a predetermined proximity threshold and acts as a contact ID of the first wireless communication device; receiving a rolling proximity identifier B associated with the second wireless communication device from the second wireless communication device, wherein the rolling proximity identifier B is a privacy-preserving identifier that is exchanged with other wireless devices that come within a predetermined proximity threshold and acts as a contact ID of the second wireless communication device; performing a cryptographic challenge response authentication with time-based distance-bounding on the rolling proximity identifiers A and B, wherein the cryptographic challenge response authentication with time-based distance-bounding is based on a hash value determined from the rolling proximity identifier A and the rolling proximity identifier B in accordance with a hash function, and wherein the cryptographic challenge response authentication with time-based distance-bounding is further based on a predetermined time threshold of a round trip time of transmission of each challenge response; and storing the rolling proximity identifier B in persistent memory on the first wireless communication device, optionally in a contact tracing log, in response to a successful cryptographic challenge response authentication. sending a rolling proximity identifier A associated with the first wireless communication device to the second wireless communication device, wherein the rolling proximity identifier A is a privacy-preserving identifier that is exchanged with other wireless devices that come within a predetermined proximity threshold and acts as a contact ID of the first wireless communication device; receiving a rolling proximity identifier B associated with the second wireless communication device from the second wireless communication device, wherein the rolling proximity identifier B is a privacy-preserving identifier that is exchanged with other wireless devices that come within a predetermined proximity threshold and acts as a contact ID of the second wireless communication device; performing a cryptographic challenge response authentication with time-based distance-bounding on the rolling proximity identifiers A and B, wherein the cryptographic challenge response authentication with time-based distance-bounding is based on a hash value determined from the rolling proximity identifier A and the rolling proximity identifier B in accordance with a hash function, and wherein the cryptographic challenge response authentication with time-based distance-bounding is further based on a predetermined time threshold of a round trip time of transmission of each challenge response; and storing the rolling proximity identifier B in persistent memory on the first wireless communication device, optionally in a contact tracing log, in response to a successful cryptographic challenge response authentication.