Derive related universally unique identifier (UUID) from a main UUID

DurandA

1/17/24, 7:51 PM

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 (T_E, U_E, ..., Z_E) 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(t_bⁿ), I can find UUID(bⁿ)
given UUID(b^m), I can find UUID(u_bⁿ)

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?

140

2 + 0

pseudo-random-function

Score:2

Crypto

Maarten Bodewes

1/17/24, 11:41 PM

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.

+ 1

Maarten Bodewes

1/18/24, 11:55 AM

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.

Score:0

Crypto

Aman Grewal

1/17/24, 11:19 PM

One possible idea (if you have enough control over the base UUIDs) is to find a 122-bit prime¹, $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.

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

+ 1

DannyNiu

1/18/24, 7:53 AM

UUIDs have versions, which is the overhead mentioned by Maarten in his answer, so it should be a prime slightly below 128 bits.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.