Abstract
We concern schemes designed for user authentication in different systems (called sectors) with a single private key so that activities of the same person in different sectors are not linkable. In particular, we consider Restricted Identification scheme implemented on personal identity cards (neuer Personalausweis) issued by German authorities. The schemes we concern are devoted for practical application on personal identity cards where limitations of memory size is a critical issue.
Unlinkability for German Restricted Identification is silently based on random oracle model. We prove that the construction can be simplified by eliminating hiding certain values with hash functions: we show that unlinkability can be based on a problem that we call Linking Diffie-Hellman Problem (LDHP). We prove that LDHP is as hard as Decisional DHP. Thereby we justify unlinkability in the standard model.
We also introduce and analyze a variant of German Restricted Identification providing active authentication. This protocol is intended for application areas where the right to access a sector is not by default (as for German Restricted Identification) and can be both granted and blocked. It is intended to serve as anonymous identity for sectors such as access to medical data and law enforcement, where prevention of Sybil attacks is a fundamental requirement.
The paper was partially supported by Polish Ministry of Science and Higher Education, grant N N206 1842 33. Later it was supported by Fundation for Polish Science, Programme “MISTRZ”.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Camenisch, J., Groß, T., Heydt-Benjamin, T.S.: Rethinking accountable privacy supporting services: extended abstract. In: Bertino, E., Takahashi, K. (eds.) Digital Identity Management, pp. 1–8. ACM (2008)
Backes, M., Camenisch, J., Sommer, D.: Anonymous yet accountable access control. In: Atluri, V., di Vimercati, S.D.C., Dingledine, R. (eds.) WPES, pp. 40–46. ACM (2005)
Bundesamt für Sicherheit in der Informationstechnik: Advanced Security Mechanisms for Machine Readable Travel Documents 2.05. TR-03110 (2010)
Abdalla, M., Bellare, M., Rogaway, P.: The Oracle Diffie-Hellman Assumptions and an Analysis of DHIES. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 143–158. Springer, Heidelberg (2001)
Bresson, E., Chevassut, O., Pointcheval, D.: Group Diffie-Hellman Key Exchange Secure against Dictionary Attacks. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 497–514. Springer, Heidelberg (2002)
Bao, F., Deng, R.H., Zhu, H.: Variations of Diffie-Hellman Problem. In: Qing, S., Gollmann, D., Zhou, J. (eds.) ICICS 2003. LNCS, vol. 2836, pp. 301–312. Springer, Heidelberg (2003)
Abdalla, M., Pointcheval, D.: Interactive Diffie-Hellman Assumptions with Applications to Password-Based Authentication. In: Patrick, A.S., Yung, M. (eds.) FC 2005. LNCS, vol. 3570, pp. 341–356. Springer, Heidelberg (2005)
Szydlo, M.: A Note on Chosen-Basis Decisional Diffie-Hellman Assumptions. In: Di Crescenzo, G., Rubin, A. (eds.) FC 2006. LNCS, vol. 4107, pp. 166–170. Springer, Heidelberg (2006)
Cheon, J.H.: Security Analysis of the Strong Diffie-Hellman Problem. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 1–11. Springer, Heidelberg (2006)
Cash, D., Kiltz, E., Shoup, V.: The twin Diffie-Hellman problem and applications. J. Cryptology 22(4), 470–504 (2009)
Shoup, V.: Sequences of games: a tool for taming complexity in security proofs (2006), http://www.shoup.net/papers/games.pdf
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kutyłowski, M., Krzywiecki, Ł., Kubiak, P., Koza, M. (2012). Restricted Identification Scheme and Diffie-Hellman Linking Problem. In: Chen, L., Yung, M., Zhu, L. (eds) Trusted Systems. INTRUST 2011. Lecture Notes in Computer Science, vol 7222. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32298-3_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-32298-3_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32297-6
Online ISBN: 978-3-642-32298-3
eBook Packages: Computer ScienceComputer Science (R0)