Random but System-Wide Unique Unlinkable Parameters

Peter Schartner

.

DOI: 10.4236/jis.2012.31001                

Abstract

When initializing cryptographic systems or running cryptographic protocols, the randomness of critical parameters, like keys or key components, is one of the most crucial aspects. But, randomly chosen parameters come with the intrinsic chance of duplicates, which finally may cause cryptographic systems including RSA, ElGamal and Zero-Knowledge proofs to become insecure. When concerning digital identifiers, we need uniqueness in order to correctly identify a specific action or object. Unfortunately we also need randomness here. Without randomness, actions become linkable to each other or to their initiator’s digital identity. So ideally the employed (cryptographic) parameters should fulfill two potentially conflicting requirements simultaneously: randomness and uniqueness. This article proposes an efficient mechanism to provide both attributes at the same time without highly constraining the first one and never violating the second one. After defining five requirements on random number generators and discussing related work, we will describe the core concept of the generation mechanism. Subsequently we will prove the postulated properties (security, randomness, uniqueness, efficiency and privacy protection) and present some application scenarios including system-wide unique parameters, cryptographic keys and components, identifiers and digital pseudonyms.

Keywords

Randomness; System-Wide Uniqueness; Unique Cryptographic Parameters; Cryptographic keys; Digital Identifiers; Digital Pseudonyms; UUID; Universally Unique Identifiers; GUID; Globally Unique Identifiers

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	P. Schartner, “Security Tokens—Basics, Applications, Management, and Infrastructures,” IT-Verlag, Sauerlach, 2001.
[2]	M. Schaffer, P. Schartner and S. Rass, “Universally Unique Identifiers: How to Ensure Uniqueness While Protecting the Issuer’s Privacy,” Proceedings of Security and Management 2007, CSREA Press, Las Vegas, 2007, pp. 198-204.
[3]	R. L. Rivest, A. Shamir and L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM, Vol. 21, No. 2, 1978, pp. 120-126. doi:10.1145/359340.359342
[4]	T. ElGamal, “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,” IEEE Transactions of Information Theory, Vol. IT-31, No. 4, 1985, pp. 469-472. doi:10.1109/TIT.1985.1057074
[5]	S. Goldwasser, S. Micali and C. Rackoff, “The Knowledge Complexity of Interactive Proof Systems,” SIAM Journal on Computing, Vol. 18, No. 1, 1989, pp. 186- 208. doi:10.1137/0218012
[6]	G. Marsaglia, “The DIEHARD Test Suite 2003,” 2003.
[7]	A. J. Menezes, S. A. Vanstone and P. C. Van Oorschot, “Handbook of Applied Cryptography,” CRC Press, London, 1996.
[8]	D. Hankerson, A. J. Menezes and S. A. Vanstone, “Guide to Elliptic Curve Cryptography,” Springer-Verlag, Berlin, 2004.
[9]	National Institute of Standards and Technology—NIST, “FIPS Publication 46-3: Data Encryption Standard (DES),” NIST, Gaithersburg, 1999.
[10]	NIST, “FIPS Special Publication 800-38A: Recommendation for Block Cipher Modes of Operation—Methods and Techniques,” NIST, Gaithersburg, 2001.
[11]	ISO/IEC, “ISO/IEC 10116: Modes of Operation of an n-bit Block Cipher,” 1991. http://www.iso.org
[12]	NIST, “SKIPJACK and KEA Algorithm Specifications,” NIST, Gaithersburg, ver. 2.29, 1998.
[13]	NIST, “FIPS Publication 197: Advanced Encryption Standard (AES),” NIST, Gaithersburg, 2001.
[14]	NIST, “FIPS Publication 180-1: Secure Hash Standard (SHA),” NIST, Gaithersburg, 1995.
[15]	H. Dobbertin, A. Bosselaers and B. Preneel, “RIPEMD-160: A Strengthened Version of RIPEMD,” Proceedings of Fast Software Encryption (FSE), LNCS, Springer, Berlin, Vol. 1039, 1996, pp. 71-82.
[16]	NIST, “FIPS Publication 180-2: Secure Hash Standard,” NIST, Gaithersburg, 2002.
[17]	IPCOM, “Method of Generating Unique Quasi-Random Numbers as a Function of Time and Space,” PriorArtDatbase, IPCOM#000007118D, 2002.
[18]	P. Leach, M. Mealling and R. Salz, “RFC 4122: A Universally Unique IDentifier (UUID) URN Name-Space,” 2005. http://www.ietf.org/rfc/rfc4122.txt
[19]	Microsoft Developer Network, “Globally Unique Identifiers (GUIDs),” 2008. http://msdn.microsoft.com/en-us/librarycc246025.aspx
[20]	Republik ?sterreich, “Bundesgesetz über Regelungen zur Erleichterung des Elektronischen Verkehrs mit ?ffentlichen Stellen (E-Government-Gesetz—E-GovG),” BGBl. I 10/2004, 2010. http://www.ris.bka.gv.at
[21]	C. E. Shannon, “Communication Theory of Secrecy Systems,” Bell System Technical Journal, Vol. 28, No. 4, 1949, pp. 656-715.
[22]	M. Alani, “Testing Randomness in Ciphertext of Block-Ciphers using DIEHARD,” International Journal of Computer Science and Network Security—IJCSNS, Vol. 10, No. 4, 2010, pp. 53-57.
[23]	M. Schaffer, P. Schartner and S. Rass, “Efficient Generation of Unique Numbers for Secure Applications,” Technical Report TR-Syssec-07-01, Klagenfurt University, System Security Group, Klagenfurt, 2007.
[24]	P. Schartner and M. Schaffer, “Implementing Collision-Free Number Generators on JavaCards,” Technical Report TR-Syssec-07-03, Klagenfurt University, System Security Group Klagenfurt, 2007.
[25]	Giesecke and Devrient, “Sm@rtCafe JavaCards,” 2011. http://www.gi-de.com.
[26]	Intel, “Intel Processors Supporting AES-NI,” 2011. http://www.intel.com.
[27]	P. Schartner, “A Low-Cost Alternative for OAEP,” Proceedings of International Workshop on Security and Dependability for Resource Constrained Embedded Systems SD4RCES, ICPS Series, ACM Digital Library, in Print, 2011.
[28]	P. Schartner and M. Schaffer, “fficient Privacy-Enhancing Techniques for Medical Databases, BIOSTEC, Communications in Computer and Information Science, Springer, Berlin, Vol.25, 2008, pp. 467-478.
[29]	P. Schartner, “Unique Domain-Specific Citizen Identification for E-Government Applications,” Proceedings of the 6th International Conference on Digital Society— ICDS 2012, Valencia, 30 January-4 February 2011.