If I can assume that the output of a block cipher like AES is a PRandom distribution, can I assume that Benford's law will hold if I partition that output into integer data?

  • 2
    $\begingroup$ From what I read on Wikipedia it only applies to natural data and encrypted data is not "natural" but uniformly random. $\endgroup$
    – SEJPM
    Mar 10 '17 at 13:38
  • $\begingroup$ I saw that as well, but I guess I wasn't exactly sure what "natural" number distributions meant $\endgroup$
    – Derek
    Mar 10 '17 at 13:41

No, Benford's law does not hold.

As a simple example, assume a block size of $8$ bits, so the values are uniformly distributed in the half-open interval $[0, 256)$. Benford's law predicts that the probability of a leading digit occurring is strictly decreasing for increasing digits. However, it's easy to see that values leading with any digit $d \geq 3$ is equally likely.

For $d=3$, the only choices are $x \in [30, 39]$ and $x = 3$, while for $d=4$ the choices are $x \in [40, 49]$ and $x = 4$, and so on for every $d \geq 3$. All of these have exactly $10 + 1 = 11$ choices that occur with equal probability. This contradicts Benford's law's prediction that the probability is strictly decreasing.

We do have a higher chance of $d=1$ and $d=2$, but this is strictly because of the choice of our base. If we chose a base $b$ such that $b^k = 256$ for some integer $k$, then every leading digit is equally likely.


From Wikipedia:

For example, in sets which obey the law, the number 1 appears as the most significant digit about 30% of the time, while 9 appears as the most significant digit less than 5% of the time.

Clearly, such a distribution cannot be pseudorandom.


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.