Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Damn Cool Algorithms: Homomorphic Hashing

blog.notdot.net

Post reply on HN
Print view View original

1–10 of 26 posts

Re: Damn Cool Algorithms: Homomorphic Hashing

#2

Post by pacaro »

Cool stuff, my head hurts less than expected from the description, I can't speak for the accuracy of the explanation, but the clarity was just about where I needed it.

It might help that I've recently been re-reading "The Mathematics of Ciphers" by S.C. Coutinho[1] which has the best easy-on-ramp introduction to the number theory behind RSA that I've encountered.

[1] http://www.amazon.com/The-Mathematics-Ciphers-Number-Cryptog...

Re: Damn Cool Algorithms: Homomorphic Hashing

#3

Post by simcop2387 »

One thing probably worth keeping in mind is that you can keep everything in much saner terms for CPU by doing something like [1]. This is how most implementations of RSA handle large exponents also. It can make it very much more efficient compared to handling some 2k bit numbers for multiplication in intermediate steps.

[1] http://en.wikipedia.org/wiki/Modular_exponentiation

Re: Damn Cool Algorithms: Homomorphic Hashing

#4

Post by nicksdjohnson »

simcop2387 wrote: post #3

One thing probably worth keeping in mind is that you can keep everything in much saner terms for CPU by doing something like [1]. This is how most implementations of RSA handle large exponents also. It can make it very much more efficient compared to handling some 2k bit numbers for multiplication in intermediate steps. [1] http://en.wikipedia.org/wiki/Modular_exponentiation

Absolutely. It's still pretty expensive to take a 257-bit power of a 1024-bit number with modular exponentiation, though.

Re: Damn Cool Algorithms: Homomorphic Hashing

#5

Post by cyarvin »

Best of all, the authors seem to have somehow evaded MIT's IPR office. (Shh!) At least, I get squat for the lead author, Maxwell Krohn:

https://www.google.com/search?tbo=p&tbm=pts&hl=en&#3...

Not-patenting a (practically, not legally) patentable algorithm doesn't come easily to academic researchers these days. The authors deserve kudos (unlike the rapacious Michael Luby, fountain code inventor) for trying to make sure people can use their algorithm sometime in the next 20 years.

Re: Damn Cool Algorithms: Homomorphic Hashing

#8

Post by kenferry »

This seems cool, but I don't understand how the given algorithm addresses the use case he gives.

The stated goal is to be able to verify pieces of a file that has been chunked up. But the first step in the algorithm is get a list of hashes for each chunk from a central server - if you have that, aren't you done?

Re: Damn Cool Algorithms: Homomorphic Hashing

#9

Post by mindslight »

kenferry wrote: post #8

This seems cool, but I don't understand how the given algorithm addresses the use case he gives. The stated goal is to be able to verify pieces of a file that has been chunked up. But the first step in the algorithm is get a list of hashes for each chunk from a central server - if you have that, aren't you done?

The paper includes details that show the motivation a bit better. Broadcast erasure codes will multiply the number of blocks by a large amount, say 16. With traditional hashing, you have to generate all of these extra 'check blocks' to hash them as part of the publishing process. Using this technique, you only have to hash the actual file and can then generate all of the other hashes using the homomorphism.

edit: actually, the receiver should be able to use the homomorphism to generate hashes for the check blocks as well. so the list of authoritative hashes to download should only be for the original chunks. the goal of the technique is to be able to verify the check blocks before being able to reconstruct the original blocks.

Post reply on HN