Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Hamming Distance (HD) has been used to measure the distance of two numbers when they are converted into binary representations. e.g., $Ham(1, 2)=2$ as 0001'XOR'0010'='0011' while $Ham(128, 1)$ equals $2$ as well. Here we see HD does not work well as it falsely indicates that the distance between $1$ and $2$ is equal to the distance between $1$ and $128$.
So my question is if there are any other distance measurement methods (or encoding methods) that can deal with this issue?
Nothing is falsely indicated there!
The Hamming distance is between strings (vectors) of the same length in the space $\{0,1\}^n. $ However the integer representation of such vectors is in a different space and the distance there is different.
Besides integer distance $|x-y|$ between two integers you can have minimal cyclic distance $$\min \{|x-y|,|n-x+y|\}$$ for two elements modulo $n.$
Note Some such distances won't be a metric. The triangle equality or symmetry may be violated.
More generally since polynomials are also widely used in Crypto, you could have metrics depending on the Hamming distance of their truth tables, or value tables if non-binary.
Or the minimal degree of two polynomials minus the number of common roots they have.
Edit: Or edit distance (levenshtein distance) which is usually defined as the minimal number of $$(insertions+ deletions+substitutions)$$ required to map a string of length $m$ to a string of length $n$ where $n=m$ is not needed. Sometimes, a weight is put on the different operations and weighted cost is minimized.
