1
$\begingroup$

Given a list of base entities (B) with each of them having a universally unique identifier (UUID) of 128 bits.

I want to attach to them a list of ≤ 7 related entities (TE, UE, ..., ZE) with each of them having their own UUID. One requirement is that I should be able to get the UUID of the main entity from the related entities, and get the UUIDs of the related entity from the main entity.

Example:

  • given UUID(tbn), I can find UUID(bn)
  • given UUID(bm), I can find UUID(ubn)

One naive scheme to achieve that would be to generate 125 bits random bits which are shared between the base entity and the related entities and use a 3 bit suffix to differentiate between a base entity and its related entities. However, this scheme does not work if the base UUIDs already exist. Moreover the distribution of the UUIDs is not uniform.

Can you think of a better scheme with a uniform distribution?

$\endgroup$

2 Answers 2

2
$\begingroup$

A random UUID has 6 bits of overhead, so even if it is fully randomized it will only have 122 random bits. To understand the various versions of random UUID's you can read RFC 4122.

If a UUID needs to be uniform or not depends on the way it is used. If it is wrongly used as a token then you would expect it to be fully random. However, if it is just unique then a non-uniform distribution should be fine.

Please note that it is possible to have fully non-random UUID's that are dependent on the name. Maybe that would be a better option in your case.

If we stick to cryptography then maybe a 122 bit encryption / decryption of the 122 bits name would generate a "random" UUID from a named UUID. You'd need Format Preserving Encryption to accomplish that.

$\endgroup$
1
  • $\begingroup$ ChatGPT actually gave me a lot of code to perform the FPE operation in Python when I asked. Unfortunately most of it was in the wrong order, but it might be a good starting point. $\endgroup$
    – Maarten Bodewes
    Commented Jan 18, 2023 at 11:55
0
$\begingroup$

One possible idea (if you have enough control over the base UUIDs) is to find a 122-bit prime1, $p$, and treat all the UUIDs as numbers between $1$ and $p-1$. For each of the related entities, you attach a fixed number (say 2, 4, 8, 16, ...). To go from the base to the related entity, you multiply by the fixed number you assigned it. To go from the related entity to the base, you multiply by the inverse.


1As pointed out by Maarten in his answer, UUIDs have 6 bits of overhead.

$\endgroup$
1
  • $\begingroup$ UUIDs have versions, which is the overhead mentioned by Maarten in his answer, so it should be a prime slightly below 128 bits. $\endgroup$
    – DannyNiu
    Commented Jan 18, 2023 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.