We consider the problem of authentication of biometric identification documents via mobile devices such as mobile phones or personal digital assistants (PDAs). We assume that the biometric identification document holds biometric data (e.g., face or fingerprint) in the form of an image and personal data in the form of text, both being printed directly onto the identification document. The proposed solution makes use of digital data hiding in order to cross-store the biometric data inside the personal data and vice versa. Moreover, a theoretical framework is presented that should enable analysis and guide the design of future authentication systems based on this approach. In particular, we advocate the separation approach, which uses robust visual hashing techniques in order to match the information rates of biometric and personal data to the rates offered by current image and text data hiding technologies. We also describe practical schemes for robust visual hashing and digital data hiding that can be used as building blocks for the proposed authentication system. The obtained experimental results show that the proposed system constitutes a viable and practical solution.