10k sats \ 1 reply \ @zuspotirko 8 Dec 2023 \ parent \ on: Challenge: encode a permutation via another permutation, with error correction? bitcoin
encode(data) = f decode(g) = data
where f and g are not equal, but f and g are permutations of {1,2,3,4,...,M}.
What this makes me think of as someone specialized in security in CS is "second preimage" from hash functions. Let's do a quick transformation:
decode(g) = data
<=>
encode(decode(g)) = encode(data)
<=>
g = encode(data)
=>
encode(data) = f
encode(data) = g
with f !=g
Functions that fulfill this property are insecure hashfunctions. Especially compressing hashfunction for which two preimages can easily be found (google "second preimage resistance"). I know this doesn't help you directly but maybe ths cryptographic perspective helps you searching
write
preview
0 sats \ 0 replies \ @VzxPLnHqr OP 8 Dec 2023
Right, that is actually why I am trying to focus more on the error-correction aspect of this. Using a secure hash function for checksum calculation (as in the bip39 spec) helps determine that there is an error but it does not identify where the error is nor help correct it.
Reed-Solomon error correcting codes are more what I am seeking, but it is non-trivial to make those work for permutations.
Anyway, there seems to be less interest/activity in this bounty thread than I was anticipating, so I went ahead and awarded the bounty to you!
reply