Timeline for Does there exist a compression function (from four 32-bit words to one 32-bit word) that always detects any modification of a single word?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 8, 2019 at 6:34 | comment | added | lyrically wicked | @SqueamishOssifrage: [2/2] Regarding the cryptographic context, I explained it in the edit. I was reading about the attacks on EnRUPT and XXTEA, and I was interested in the structure of the round function. Also I have a question about the unbalanced Feistel networks (but I cannot ask this question without gathering some preliminary information). | |
| Apr 8, 2019 at 6:34 | comment | added | lyrically wicked | @SqueamishOssifrage: [1/2] The basic non-cryptographic context is given, for example, here or here. Just a 32-bit hash for an unsigned 128-bit integer, with the additional property of detecting any error if this error is in a single 32-bit word. | |
| Apr 8, 2019 at 5:50 | review | Close votes | |||
| Apr 24, 2019 at 11:12 | |||||
| Apr 8, 2019 at 5:47 | comment | added | Squeamish Ossifrage | Well, you can try to pick a CRC polynomial with sufficient guaranteed error-detection capacity, but it may be a tall order to demand that every possible single-word error is detected. You're still not saying why you need this, and the amount of effort you're putting forth to conceal your purpose is not promising. Can you step back, forget the diffusion and nonlinearity and words and hashing, and give the actual context? | |
| Apr 8, 2019 at 5:39 | comment | added | lyrically wicked | @SqueamishOssifrage: I need it to detect single-word errors in 128-bit keys. | |
| Apr 8, 2019 at 5:28 | comment | added | Squeamish Ossifrage | What are you planning to do with this? Suppose it's fast; what do you need it for then? ‘Hashing function’ doesn't narrow it down—that could mean any of umpteen different things. Are you using it for a hash table? For a message authentication code? For content-addressed storage? For error detection in a nonmalicious noisy channel? | |
| Apr 8, 2019 at 5:23 | comment | added | lyrically wicked | @SqueamishOssifrage: I edited the question to explain the connection to cryptography. What do I want this for? The answer depends on the performance of a function with the described property. If the algorithm is fast, then at least it can be used as a non-cryptographic hashing function for 128-bit integers... | |
| Apr 8, 2019 at 5:12 | history | edited | lyrically wicked | CC BY-SA 4.0 |
added 399 characters in body
|
| Apr 7, 2019 at 20:48 | comment | added | Squeamish Ossifrage | You can use the parity of the bits: guaranteed to change under single-bit errors (and as a bonus, errors of any odd Hamming weight); cheap to compute using only XOR; extends naturally to larger error-detecting capacity as a special case of any CRC over a polynomial with $x + 1$ as a factor. But there's no cryptographic content here. What do you want this for? What is the connection to cryptography? | |
| Apr 7, 2019 at 19:44 | answer | added | dave_thompson_085 | timeline score: 2 | |
| Apr 6, 2019 at 8:04 | comment | added | lyrically wicked | @forest: I used the term "bitwise operations" as related to a practical implementation of a function. For example, Keccak block permutations use only bitwise operations, but a practical implementation of a block transformation in SHA-2 also uses additions, hence does not use "only bitwise operations". | |
| Apr 6, 2019 at 7:50 | comment | added | forest | The operations you specified make the system Turing complete, so you could describe any algorithm as NOT+AND. Also, what you're looking for is a property called "burst detection", which is in the realm of CRCs. | |
| Apr 6, 2019 at 7:45 | history | asked | lyrically wicked | CC BY-SA 4.0 |