Collision-free Number Generation
Universally Unique Identifiers (UUIDs) -- standardized in ISO/IEC 9834-8:2005 -- are widely used to uniquely identify entities in modern IT-systems. Apart from what promised in the standard, UUIDs are not guaranteed to be unique while preserving the issuer's privacy. In this project we introduce a novel concept called collision-free number generation (CFNG) that can be used to locally generate UUIDs which are provably globally unique. Moreover, if the presented techniques are instanced carefully, a poly-bounded adversary is not able to efficiently identify the issuer of a UUID. Our approach is efficient in terms of communication, time and space. As a by-product, it can be applied in other areas where collisions have to be avoided (e.g. key generation, pseudonym systems and interactive proofs).
Especially when concerning key generation for the RSA encryption or signature schemes, CFNGs may be used to avoid common prime factors or poor randomness of the employed primes. Both, common primes and poor randomness, put the security of the RSA system at risk. One might arue, that the chance of duplicates when using 1024- or 2048-bit RSA keys is quite low, but ... see "Ron was wrong, Whit is right" at the Cryptology ePrint Archive.
UUID, GUID, uniqueness, duplicates, collisions, prime number generation, RSA, ElGamal, interactive proofs, key management, cryptographic keys, cryptographic parameters, digital identifier, digital pseudonyms, nyms.
Peter Schartner (Project Leader)
Martin Schaffer (Project Leader, now at NXP Semiconductors)
Stefan Rass
Mario Pivk (former Research Student - Programming Project)
Philipp Fleiss (former Research Student - Programming Project)