Systems for cellular network authentication utilizing unlinkable anonymous credentials are disclosed. In embodiments, a computer program product is provided including a computer readable storage medium having program instructions embodied therewith. The program instructions are executable by a computing device to cause the computing device to: contact a mobile device network with a request to connect to the mobile device network; conduct an interactive credential issuance protocol with an Issuer of the mobile device network to generate an unlinkable anonymous credential; connect to the mobile device network based on a Verifier of the mobile device network verifying the computing device based on the unlinkable anonymous credential; and store a temporary mobile subscriber identity assigned to the mobile device by the mobile device network, wherein the temporary mobile subscriber identity is filled with a null value.