4

Say we have a function that maps a string of size $n$ of some finite alphabet to another such string of size $n$. Or alternatively, a function that maps an $n$ dimensional real vector to another one.

I am looking for a term/concept that captures the notion of how "local" the transformation is. For example, if such a function maps a string of 5000 digits to the same string, except multiplying the 43'th digit by 2 or by 10 billion, then it is extremely local, since if you change one digit in the input, this will only change the same digit in the output.

But if we have a cryptographic hash function, then changing one digit even slightly, will completely change all the output digits, and all of them in different ways. So such a function is highly "non-local"

Is there a formal concept of this notion of "locality" of a transformation?

user56834
  • 12,925
  • The question and the title do not match. –  Apr 20 '18 at 16:15
  • 1
    The hash function non-locality is called an https://en.wikipedia.org/wiki/Avalanche_effect – Dap Apr 20 '18 at 17:52
  • @Dap, is there a kind of "metric" for the extent to which the avalanche effect holds? like, the identity function maybe has "zero avalanche" while a hash function has 100% avalanche. Is there a metric that can tell you that a function has, say 20% avalanche or something like that? – user56834 Apr 24 '18 at 10:46

1 Answers1

4

One measure of locality of a function $f:X^n\to Y^m$ would be the maximum value of $$ \frac{\|f(v)-f(w)\|_0}{\|v-w\| _0} $$ over all pairs $v,w\in X^n$ where $v\neq w$. Here, $\|v-w\| _0$ is the number of coordinates where $v$ and $w$ differ, also known as their Hamming distance. This quantity is more generally known as the Lipschitz norm of $f$, and is defined for any map between two metric spaces (provided one takes the supremum instead of the maximum).

For example, if this quantity was $1$, then changing any coordinate of the input would change at most coordinate of the output, indicating the function is very local. The largest it could be is $m$, indicating that there exists a vector whose output can be completely changed by altering a single coordinate.

A possible drawback is that this measure the worst case non-locality of $f$, instead of the average non-locality.

Mike Earnest
  • 75,930