I have been working on a project implementing LT codes with Homomorphic hashing (inspired from http://blog.notdot.net/2012/08/Damn-Cool-Algorithms-Homomorphic-Hashing and http://blog.notdot.net/2012/01/Damn-Cool-Algorithms-Fountain-Codes).

Here's what I have understood from those links.

Suppose the message to be sent and verified is a text Hello or ['H','e','l','l','o'] (ASCII values [72, 101, 108, 108, 111]).

An LT code scheme will create unlimited number of encoded chunks, one of which could be $c_1 = \mathrm{'H'} \oplus \mathrm{'e'}$.

Now transforming it to a homomorphic scheme, it becomes $c_1 = (\mathrm{'H'} + \mathrm{'e'}) \bmod q = (72 + 101) \mod 257 = 173$. 173 is sent and received by the receiver which verifies the block on-the-fly using homomorphic hashing. $$h(c_1) = (h(\mathrm{'H'}) \cdot h(\mathrm{'e'})) \bmod p$$

If it matches, it stores the encoded block otherwise it discards it. (Assuming it already stores the hashes of the individual blocks, in this case block size is assumed to be 1)

Suppose some other encoded block is $c_2 = \mathrm{'H'} = 72$. It is verified at the receiver and LT decoder decodes it to 'H' and 'e' as follows:

$c_1 = 173 = \mathrm{'H'} \oplus \mathrm{'e'}$ and $c_2 = 72 = \mathrm{'H'}$ so $c_1 - c_2 = 102 = \mathrm{'e'}$, and so on and so forth.

Is this the right way to go about it? Am I missing something in the implementation? Can we use $\oplus$ (xor) instead of addition while sending the encoded blocks?

As per above link, Nick discussed verifying file in batches of blocks. So continuing the same example, assume we'd use homomorphic hashing after receiving the first 3 bytes ('H', 'e', 'l'). After we receive first 3 bytes, we'd apply a homomorphic hash the same way as applied to string Hello as in Nick's blog. If the hash matches , we're good but if hash doesn't match (say because we had received 'I', 'e', 'l'), how do we figure out that it's the first byte that is corrupted?

  • $\begingroup$ Dumb question: What does the symbol ⊕ mean? $\endgroup$ Apr 22, 2013 at 14:15
  • 1
    $\begingroup$ @makerofthings7 ⊕ is one customary way of writing xor (exclusive or). $\endgroup$
    – dr jimbob
    Apr 22, 2013 at 14:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.