3
$\begingroup$

I am looking for the function $y=f(x)$ that would map the integer interval $[0,n)$ into itself $[0,n)$. The function must be bijective, so it is a permutation of n elements. It should "randomize" the input variable, ie.

  • for every $x_1$ and $x_2$ that are close $|x_1 - x_2| < 100$ the outputs of the function should differ very much $|f(x_1) - f(x_2)| > n/{100}$
  • changing any digit in the input should change most of digits in the output
  • Shannon's Confusion and diffusion: http://en.wikipedia.org/wiki/Confusion_and_diffusion
  • There should be very little or no fixed points (for every $x$: $f(x) \neq x$).

or any combination of the above conditions.

I don't need the inverse function. It should also be easy to compute from the closed form expression (a maximum of a few thousands simple computer operations like addition, multiplication, modulo etc.) for $n=10^{100}$.

I found some examples in Google:

  1. Linear congruential generator. Equation:

$X_{n+1} = (aX_n + c) \mod m$

Wikipedia states that: "Provided that the offset $c$ is nonzero, the LCG will have a full period for all seed values if and only if:

  • $c$ and $m$ are relatively prime,
  • $a - 1$ is divisible by all prime factors of $m$,
  • $a - 1$ is a multiple of 4 if $m$ is a multiple of 4.

I've tried using another function $f(x) = (ax + c) \mod m$, because I wanted to get rid of the recursion, and as long as $m$ is prime and $a \ge 1$ I get the permutation. However the result is not that "wild" or "chaotic" as I expect it to be.

  1. Minimal perfect hash function

The concept is similar to what I'm looking for, but if I understand correctly the computation of this kind of function is very complicated and time-consuming and it cannot be expressed in a closed form as a simple expression for $n=10^{100}$.

  1. Substitution-permutation network

I am not sure how to apply S-boxes and P-boxes to the interval [0,n), but maybe it could be used.

The question is: Could you give me some examples of functions that satisfy the above conditions (or some pointers like the mathematical term for the object I am looking for)?

$\endgroup$
  • $\begingroup$ What do you need the function for? $\endgroup$ – Yuval Filmus Apr 8 '15 at 2:06
  • $\begingroup$ Generaly speaking, block ciphers should foot your bill. Round $n$ up to the nearest power of 2, and then apply a block cipher, possibly in blocks using a "mode of operation" such as CBC. $\endgroup$ – Yuval Filmus Apr 8 '15 at 4:08
  • $\begingroup$ I need to have many (hundreds) sequences that generate ids. I want to export the ids into the external system in encoded form without revealing which sequence the id comes from. I decided to use the formula $id1=whichSequence*10^{20}+sequenceIdFromTheSequence$. I also need to be able to discard large chunks of ids, so I figured I could do it in the same way, ie. $id2=chunk*10^{40}+id1$. Then I need to be able to replay parts of the sequences from last week starting with the particular sequenceIdFromTheSequence, so it has to be determininstic. There should be no collisions in encoded ids. $\endgroup$ – tafit3 Apr 8 '15 at 11:21
2
$\begingroup$

Yes, such things exist. They have been studied in the cryptographic literature: the key name is "format-preserving encryption".

To learn about this subject, I suggest taking a look at https://en.wikipedia.org/wiki/Format-preserving_encryption and https://crypto.stackexchange.com/q/16561/351 and https://crypto.stackexchange.com/q/504/351 and https://crypto.stackexchange.com/q/20035/351 and https://crypto.stackexchange.com/q/18988/351 and https://crypto.stackexchange.com/questions/tagged/format-preserving. You could also construct a suitable block cipher yourself using a Feistel construction, but it's probably better to use a standard scheme that has been analyzed in the literature.

There are many constructions. The best one will depend on the specific value of $n$ in your application. Take a look at the schemes in the cryptographic literature, then if you have a more specific question about how to use one of those schemes, you can ask either here or on Crypto.SE.

$\endgroup$
  • $\begingroup$ Don't construct a block cipher yourself. $\endgroup$ – Yuval Filmus Apr 8 '15 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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