Join Log in
Score:0
caveman avatar Crypto

Non-overlapping seeded numbers generator for small output range

in flag
caveman

Seen this, but it's sort of useless as it allows for trivial solutions by increasing the size of the output's space up to a point any hashing function will achieve non-collision.

This question is trying to be the less useless version of that. I.e. to be about the case where the output range is small. Say that my outputs space is $\mathcal{S} = \{0, 1, \ldots, 10^{6}\}$. Here, collisions by using hashing functions will easily arise.

To reword the question: is there any function $f : \text{seed}, \text{range}, \text{state} \mapsto n$, such that:

  • Requirement 1: Output range can be small. E.g. from $0$ to $10^6$.
  • Requirement 2: No collisions for different seeds. I.e. for any seed and range, $f(\text{seed}, \text{range}, \text{state}_1) = f(\text{seed}, \text{range}, \text{state}_2)$ if and only if $\text{state}_1 = \text{state}_2$.
  • Requirement 3: Can't predict what the next number is unless one calls the function $f$. E.g. if $f(\text{seed}, \text{range}, \text{state}_1) = 3$, then can't know what the output is with $\text{state}_2$ without plugging it into the function $f$. This eliminates trivial solutions that may use definition $f' : \text{seed}, \text{range}, \text{state} \mapsto \text{seed} \times \text{state} \mod \text{range}$, where seed, range and state are all positive numbers.
26
1 + 0
Score:1
poncho avatar Crypto
my flag
poncho

is there any function $f : \text{seed}, \text{range}, \text{state} \mapsto n$,

Yes; they're known as Format Preserving Encryption functions. These are functions that are arbitrarily sized block ciphers:

  • Requirement 1: Output range can be small. E.g. from $0$ to $10^6$.

Yes, they can take quite small ranges. In my experience, FPE's tend not to like truly tiny ranges (e.g. a range of less than 100 values); a range of a million is plenty for the ones I know about

  • Requirement 2: No collisions for different seeds

If we use the seed as the FPE key, and the state as the FPE plaintext, this is guaranteed - the FPE operation is invertable (that is, by putting the FPE operation in decrypt mode and feeding it the same key, it converts the ciphertext back into the plaintext), hence two plaintexts cannot be converted into the same ciphertext

Requirement 3: Can't predict what the next number is unless one calls the function $f$

Also true; FPE is designed to be secure (unless you know the key), hence the only way to predict how the plaintext is transformed is to use the key.

FPE functions also take a 'tweak' (an additional input that need not be private that changes the mapping defined by the encryption) - I would suggest using the range as part of the tweak (in addition to modifying how the FPE function works internally) - that way, you don't have to worry about the function with one range leaking information about the function with a different range.

Now, if you need advise as to which FPE function to use, the best one I've found is the FF1 defined here function; from what I've seed, it appears to be fairly solid.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

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.