2
$\begingroup$

Let say I have three sequences:

S1 = {1,2,3,4,5,6,7,8,9,10}

S2 = {3,7,1,9,4,10,5,8,6,2}

S3 = {8,3,10,2,6,7,1,5,9,4}

i.e. S2 and S3 are just the permutations of S1. Is there any method to check how much these sequences are random to each other? I need to check their randomness using any randomness test. I found NIST test suite which is for bit-stream but not able to find any test for permuted sequences.

Keeping in mind that the sequence is big {1,2.3,...,n} and have 'm' sequences.

Edit: Here; m < n

And permutations are key-based permutations.

$\endgroup$
1
  • $\begingroup$ You really need to add that $n = 202,500$ as it makes quite a difference to the technique. And how large is $m$? Randomness is a function of sample size which makes the scale of the data set important. $\endgroup$
    – Paul Uszak
    Jun 19, 2019 at 10:47

4 Answers 4

7
$\begingroup$

There is no such thing as randomness of a sequence (or of a permutation, or of a string, etc.). There is only randomness of a process for choosing sequences (permutations, strings, etc.), which is intrinsically not something you can test by looking at its outputs.

What you can do is write a decision procedure that will, with some probability, return a different answer depending on which of two different random processes generated the outputs. Of course, the probability distribution on its decisions depend on the probability distribution on its inputs! Here's a couple examples:

    • Input data: String of $n$ bits $b_i \in \{0,1\}$.
    • Procedure:
      1. Compute $$\chi^2 = \frac{(\#\{b_i = 0\} - n/2)^2}{n/2} + \frac{(\#\{b_i = 1\} - n/2)^2}{n/2},$$ where $\#\{b_i = 0\}$ is the number of zero bits and $\#\{b_i = 1\}$ is the number of one bits.
      2. If $\chi^2 \leq 3.841$, return 0; otherwise return 1.
    • Probability distributions:

        • A1: independent uniform Bernoulli trials, $\theta = 1/2$
        • B1: independent Bernoulli trials biased by $\theta = 1/3$

        If the inputs are distributed by A1, then the probability of returning 0 is 95% and the probability of returning 1 is 5%. In statistics jargon, if we take A to be the null hypothesis and 1 to mean rejection or an alarm, the statistical significance or false alarm rate is 5%.

        If the inputs are distributed by B1, then the probability of returning 0 is considerably lower and the probability of returning 1 is considerably higher. (Exercise: Compute these quantities. In statistics jargon, if we take B to be the alternative hypothesis to our null hypothesis A, the probability of returning 1 given B is called the statistical power of the test.)

        • A2: independent uniform Bernoulli trials, $\theta = 1/2$
        • B2: alternating 0 and 1 bits, either 01010101… or 10101010… with equal probability $1/2$

        If the inputs are distributed by A2, then as above the probability of returning 1 is 5%—obviously, this is the same test and the same distribution A1 as above, so the false alarm rate is 5% as above.

        If the inputs are distributed by B2, then the probability of returning 0 is 100% and the probability of returning 1 is 0%. That is, the test has no statistical power whatsoever to detect B2!

    What this illustrates is that the utility of any distinguishing test depends entirely on the distributions you are trying to distinguish. You cannot simply ask: ‘Is this sequence random?’ or ‘Is this sequence independent uniform Bernoulli trials?’

    • Input data: String of eight Smarties in unique colors.
    • Procedure:
      1. If a mauve candy appears before a yellow candy, return 0; otherwise return 1.
    • Probability distributions:

      We hypothesize that a factory, which produces the colors in alphabetical order [blue brown green mauve orange pink red yellow], has not been randomly permuting them with all possible permutations—specifically, it has been permuting the first four as a group, and the last four as a group, but never interchanging anything in the first group with anything in the last group. So we have:

      • A3: Smarties with uniform permutation
      • B3: Smarties with blue/brown/green/mauve permuted uniformly, followed by orange/pink/red/yellow permuted uniformly.

      Under distribution A3, there is a 50% chance of mauve appearing before yellow, and a 50% chance of yellow appearing before mauve. So the procedure returns 0 and 1 with equal probability, 50%.

      Under distribution B3, there is a 100% chance of mauve appearing before yellow, and a 0% chance of yellow appearing before mauve. So the procedure returns 0 with 100% probability, and returns 1 with 0% probability.


In cryptography, we usually work with distributions that are so similar that any procedure to distinguish them has almost the same probability of returning 1 for both distributions—so that even procedures that were designed by extremely smart cryptanalysts with knowledge of how your system works can't tell the distributions apart with more than negligible probability. In other words, if the NIST tests can break your system, then it can be broken by someone so stupid that they don't even know they're trying to break your system—and I mean that quite literally: a programmer at NIST, who is not stupid in the general sense but specifically lacks knowledge of your system, was able to devise a test years ago that would break it before you even designed your system.

So, we can't help you find a test for randomness of your permuted sequences—that is a nonsensical question, on its face. It's also not really interesting to try to psychoanalyze you to guess what processes might have generated your permutations and then derive tests based on those. But if you can describe the candidate processes, or describe a process and compare it to the uniform distribution on permutations, maybe then there is a test that will distinguish them.

For example, maybe you're trying to permute $\{0,1,2,\dots,2^{128} - 1\}$, and your permutation is chosen by (a) picking a 256-bit key $k$ uniformly at random, and then (b) selecting $\operatorname{AES}_k$ as the permutation. In that case, you have no hope of distinguishing it from a uniform random permutation of $\{0,1,2,\dots,2^{128} - 1\}$ (barring side channel attacks).

$\endgroup$
12
  • 2
    $\begingroup$ There have been up to ten, I think, but the white ones were only a stand-in a few years ago while Smarties was looking for an acceptable blue dye, and the light brown ones haven't seen the light of day in a few decades. $\endgroup$ Jun 19, 2019 at 14:48
  • 3
    $\begingroup$ I don't understand what your criticism even means. Example 1 is not about sequence of integers; it's about sequence of bits, and its purpose is to illustrate decision algorithms and probability distributions. In A3, ‘uniform permutation’ of an eight-element sequence means every permutation has equal probability $1/8! = 1/40 320$, in contrast to B3 where there are only 576 permutations (24 for the first group of four, and independently 24 for the second group of four) with equal probability $1/4!^2 = 1/576$. $\endgroup$ Jun 19, 2019 at 14:51
  • 2
    $\begingroup$ @ZeeshanAbbas What I'm giving you is not a test that answers your stated question directly, but rather the background to understand why your stated question has no answer, unless you provide the additional information of what two probability distributions you are trying to distinguish. (Consider it an extended ‘unclear what you're asking’ comment.) If, on the other hand, you are actually asking ‘How can I generate permutations randomly?’, then the Knuth (Fisher–Yates) shuffle is a reasonable answer; to make it keyed just use a PRNG with the key as the seed. $\endgroup$ Jun 19, 2019 at 19:21
  • 1
    $\begingroup$ @ZeeshanAbbas You can do that, and it will give an answer, just like if you ask Google ‘why do colorless green ideas sleep furiously?’ it will return a page of results, but you won't get a meaningful answer to your question. One could compute the probability under uniform permutations of bytes that the NIST tests return 0 or 1 like the decision algorithms above. But that won't tell you anything about the process you used to permute the bytes and whether it is actually uniform. It is not meaningful to ask of a sample of data whether the sample is random or not. $\endgroup$ Jun 20, 2019 at 12:54
  • 2
    $\begingroup$ There's a standard distinguisher for uniform random draws with replacement (i.e., uniform random function) from uniform random draws without replacement (i.e., uniform random permutation), which is how, e.g., sweet32.info works. There's also a standard distinguisher for uniform random permutations from uniform random derangements (i.e., permutations with no fixed points), which is part of how the Bletchley crowd broke the Enigma; see crypto.stackexchange.com/a/67473 for details in modern language. $\endgroup$ Jun 20, 2019 at 21:07
-1
$\begingroup$

Just 10 samples of a sequence, couldn't depict any thing about randomness .In real, testing randomness, need a long sequences. NIST tools are one of the best ways to deducing which a sequence is pseudorandom or not,however they need at least 10^6 sequences and the input should be in bit form.

$\endgroup$
2
  • $\begingroup$ As I mentioned "Keeping in mind that the sequence is big {1,2.3,...,n} and have 'm' sequences." The sequence is not of 10 digits only. To be exact it's {1,2,3,...,202500}. Yeah I found the NIST test which needs the input in binary, but I need to check the randomness of the permutation here not the bits... $\endgroup$ Jun 19, 2019 at 9:04
  • 1
    $\begingroup$ This doesn't seem to address permutations, nor provide any perspective on the question. $\endgroup$ Jun 19, 2019 at 14:59
-1
$\begingroup$

The solution to generating the permutation is simply a Fisher–Yates shuffle, where Fisher–Yates is fed a source of random numbers from an AES or HKDF based RNG. The issue is just ensuring a bias free random selection from a range which can be accomplished inefficiently with sample rejection, or something cleverer. If the implementation is correct, there is no need to NIST test them as they will be fully random wrt each other. That's the shuffle's raison d'être. If you wanted, you'd just NIST test the RNG itself. And if you use the standard/approved RNG constructions below, then you don't even need that, other than to debug.

So to get randomly permuted sequences $S_i$ keyed on $k_i$, build:-

$$ \text{Original key,}\operatorname{k_i} \to \operatorname{SHA256(k_i)} \to \text{256 bit key,} {k^\prime} \to \operatorname{AES_{k^\prime}(n)} \to \text{random bytes} \to \operatorname{Shuffler(S1)} \to S_i $$

or perhaps better/simpler,

$$ \operatorname{HKDF-SHA256_{k_i}(n)} \to \text{random bytes} \to \operatorname{Shuffler(S1)} \to S_i $$

where $k_i$ are the keys for the individual permutations, and $n$ is just a counter for the AES or HKDF based RNGs.

The generally accepted approach (if you build the above) is to simply confirm the randomness of the RNG driving the shuffling process.


If you do require a 'randomness' test of the permutations wrt themselves, I think that you're going to have to redefine randomness to something specific to your problem. The NIST test suite (nor any other) doesn't apply to permutations or inter-permutation testing. You're going to have to mathematically and explicitly define how the $S_i$ sequences are "random to each other". Otherwise how can you test against a hypothesis? And you'll then have to relate that hypothesis to a range of $p$ values indicating the certainty of the null hypothesis, from 0 to 1. That's required as randomness is pesky and hard to pin down empirically. The $p$ value indicates with what certainty might have that thingie arisen by chance.

$\endgroup$
4
  • 3
    $\begingroup$ The question does not ask how to generate permutations, so why is half of this answer about how to do so? $\endgroup$
    – Ella Rose
    Jun 19, 2019 at 14:46
  • $\begingroup$ @EllaRose If you follow the random bits upstream to the generator, it proves that the permutation of the sequences themselves must be _random_by deduction. Therefore no funky mathematical formulae have to be created from scratch for inter-permutation randomness tests. You just test (or not) the RNG. You can then use accepted tests which output indicative $p$ values, and hey presto... $\endgroup$
    – Paul Uszak
    Jun 19, 2019 at 15:54
  • $\begingroup$ @PaulUszak is this " Fisher–Yates shuffle" a keyed permutation? $\endgroup$ Jun 19, 2019 at 16:54
  • $\begingroup$ @ZeeshanAbbas No and yes. The shuffle algorithm isn't; that's just random swapping. But the generator creating the random numbers is uniquely seeded, and that could be interpreted as keying. As in a stream cipher... $\endgroup$
    – Paul Uszak
    Aug 4, 2019 at 12:54
-1
$\begingroup$

Yes, you can check randomness between sets by comparing their position relative to one another. This is called a positional randomness test.

Comparing your two sets to your control set, using a positional method. The set, (3,7,1,9,4,10,5,8,6,2) shows a higher entropy, (better randomness), excludes the fact that you should have at least one repeating number.

$\endgroup$
7
  • $\begingroup$ This is a contradiction in terms. There's no probability distribution; there is no notion of entropy—except, of course, in the trivial sense that a trivial probability distribution, which assigns probability 1 to one specific value like (3, 7, 1, 9, 4, 10, 5, 8, 6, 2) and probability 0 to every other possible value in any space, has zero entropy. $\endgroup$ Aug 5, 2019 at 2:03
  • $\begingroup$ No contradiction. His original question was in comparison to his two sets. The only way to compare that i know of is through a positional randomness test which after running does not return a series of numbers 1 through 10 but shows their positions how they were placed, (would be glad to clarify this more if unclear). Using this method you get a more random distribution with the set i mentioned. $\endgroup$
    – Jon Hutton
    Aug 5, 2019 at 3:56
  • $\begingroup$ @JonHutton thanks and it seems a good one. But how can I check this for long sequences using any algo? Because the actual sequence is almost 260,000 values length. Also, we need to compare multiple such sequences, not just two. $\endgroup$ Aug 7, 2019 at 17:28
  • $\begingroup$ There is no code for this process, since i invented it, but unfortunately i do not code. The process is great for finding kolmorgovo differences within small or large data sets. You are welcome to try if you code. Let me know. $\endgroup$
    – Jon Hutton
    Aug 7, 2019 at 18:06
  • $\begingroup$ It is precisely because the question is about ‘comparing two sets’, without reference to a probability distribution, that any answer about randomness or entropy is a contradiction in terms. A deterministic computation on a specific sample can lead one to weigh one hypothesis about the distribution from which the sample came over another one, or may enable you to estimate parameters in a hypothesis family which determines entropy for that estimate—but for this to be meaningful, you must, as a premise, have such hypotheses about distributions that the sample may have come from. $\endgroup$ Aug 21, 2019 at 16:17

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.