The application of modern electronic identity documents is not limited to local authentication, but they can be used to remotely access online services. In order to protect user's activities in different services, a pseudonymous identification system must be used. Standard cryptographic primitives are to complex for embedded devices, thus the restricted identification protocol was proposed in the German eID project. Unfortunately, the protocol is flawed and requires strong assumptions about secure memory of the used hardware. On the other hand, various fixes to this introduce new ones, e.g. complex operations or large public key infrastructure. In this paper we propose our work-in-progress protocol, which is the first practical replacement for restricted identification.