0 sats \ 2 replies \ @VzxPLnHqr OP 7 Dec 2023 \ parent \ on: Challenge: encode a permutation via another permutation, with error correction? bitcoin
Thanks. I understand what you mean now. However, it does not quite capture what I am seeking. I want it to be a single message which is comprised of data (e.g. entropy for a cold wallet, which itself may include some of its own checksums, etc), and I want the whole thing to be represented as a permutation of {1,2,3,4,5...,M}. So what I want is definitions for encode and decode such that:
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}.
Continuing with the cold storage example: the sender "sends" f by putting the cards in the order determined by f and then destroying the underlying original entropy (the secret) since it is now represented by f. Maybe Sender then buries this deck of cards in a hole in the ground or something :-).
Then, some time later, the Receiver (which could be the Sender itself) digs up the deck of cards and writes down their order. Unfortunately the order the cards are now in, for whatever reason, turns out to be g which is not equal to f. In other words, there was an error in the transmission. However, all hope should not be lost.
So, the question is: can we endow f with enough error correction capabilities that even if the receiver receives g, the receiver can still find the underlying original secret data from g?
write
preview
10k sats \ 1 reply \ @zuspotirko 8 Dec 2023
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
reply
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