Methods that support deterministic random media access control (MAC) address rotation that allows sharing of an address identity with a trusted wireless network infrastructure by generating a next address based on a previously used address and a seed obtained from a previous association with the trusted network infrastructure. In these methods, a computing device obtains a request for a secure connection of an endpoint device to a wireless network. The computing device performs an access authentication for the secure connection and establishes the secure connection of the endpoint device to the wireless network based on successfully performing the access authentication, in which cryptographic information for encrypting one or more network messages is generated. The computing device further generates a subsequent device address for a subsequent secure connection of the endpoint device to the wireless network, based on a current device address obtained from the request and the cryptographic information.