Damn Cool Algorithms: Homomorphic Hashing

http://blog.notdot.net/2012/08/Damn-Cool-Algorithms-Homomorphic-Hashing

by moobirubi • 14 years ago

234 25 14 years ago

blog.notdot.net

pacaro• 14 years ago

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...

simcop2387• 14 years ago

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

nicksdjohnson3• 14 years ago

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

cyarvin• 14 years ago

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...

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.

sshconnection• 14 years ago

Listening to the RNC in another tab, read this as homophobic hashing. Sigh.

mindslight3• 14 years ago

^ This is your brain on mass media. Any questions?

xianshou• 14 years ago

Is it morally wrong for two threads to be writing files out of deadlock?

sproketboy• 14 years ago

Not that there's anything wrong with it.

kenferry• 14 years ago

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?

mindslight3• 14 years ago

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.

nicksdjohnson3• 14 years ago

Actually, it's even worse than that - with a rateless code like Fountain codes, you can generate an effectively unlimited number of encoded blocks, making pregeneration of hashes for them all completely impractical.

In all other particulars you're dead right.

csense• 14 years ago

Read up on fountain codes. A good starting point is the previous post on the same blog [1], actually linked in the first sentence of the article.

The basic idea is that, instead of sending N blocks in the content file f, you have a block generator gen_block(f) which can create an infinite number of blocks as random combinations of input blocks (plus a little "magic"). A peer who downloads any 1.01N or so blocks can reconstruct the original file (with high probability); because of the "magic," it doesn't matter which 1.01N blocks they are!

Fountain codes work beautifully in broadcast protocols, where the receiver has no way of communicating back to the sender (this is not generally true for TCP/IP outside of exotic scenarios, for example multicast).

For Bittorrent-like protocols (peer-to-peer large file distribution over TCP/IP), the practical problem that is addressed by fountain codes is making sure that the entire file will still usually be recoverable from data that exists within the network if all the seeders (peers with complete a copy) leave the network; in traditional Bittorrent, often there are a few missing blocks in this situation.

The practical problem addressed by homomorphic hashing is how a receiver can rapidly identify peers that are attacking a fountain-code-based P2P network by deliberately sending corrupt downloads (and as a side-effect can of course detect accidental corruption as well.)

[1] http://blog.notdot.net/2012/01/Damn-Cool-Algorithms-Fountain...

psykotic2• 14 years ago

If I'm understanding the application correctly, this would also work with Tillich-Zemor-style hashing based on matrix groups. The idea is to map the 0 and 1 message bits onto a pair of generators of a subgroup of the invertible 2x2 matrices with entries in some GF(2^n). The message hash is just the product of the generators corresponding to the message bits.

What's really cool is that matrix multiplication is associative, i.e. x(yz) = (xy)z, so you can perform the hashing in parallel: Hash the left half, hash the right half, and combine the results by multiplication. It also allows distributed multi-party hashing, as in this article's application.

Unfortunately, classical TZ hashing has fallen completely to practical collision attacks as well as first and second preimage attacks. However, those attacks all rely on very special properties of power-of-two Galois fields, so there's no reason generalized TZ-style matrix group hashing wouldn't be feasible.

breckinloggins2• 14 years ago

I just want to say how much I love this blog. I'm a self-taught programmer, which means that I tend to learn algorithms as I feel I need them (a big problem given that I have to know what I don't know before I can know it!). I've recently gotten more into computer science for its own sake, but books and papers about algorithms are often dry and unmotivating.

The pieces on this blog are always entertaining and clearly justify the excitement and purpose of the algorithm under discussion.

Computer science and the STEM world in general needs more stuff like this, and I'm happy that we are in fact seeing more and more of it. Well done.

psykotic2• 14 years ago

> books and papers about algorithms are often dry and unmotivating.

If you don't like standard textbook treatments like CLRS, you might like these: Introduction to Algorithms - A Creative Approach by Udi Manber (out of print but worth getting). Algorithm Design by Klein and Tardos. How to Think About Algorithms by Jeff Edmonds. Jeff Erickson's lecture notes on algorithms: http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/

Jon Bentley's Programming Pearls is about what I'd call algorithm engineering. The algorithms are never anything fancy but it's a good example of algorithms applied to real-world problems. It's possibly the best single book on programming I know. Make sure to do all the exercises.

breckinloggins2• 14 years ago

Thanks! I'll take a look. It's not so much that I don't like them, it's that I seem to be able to "get into" a paper or textbook after I understand what's so cool about what they're talking about.

lallysingh• 14 years ago

I'd like to shove in Skiena's Algorithm Design Manual. Very readable, great coverage.

nicksdjohnson3• 14 years ago

I can't express how awesome it is to hear that.

jfb• 14 years ago

I love your blog. That is all. Please keep it up -- you do an excellent job and have an appreciative audience.

ralph• 14 years ago

I'm also self-taught but find not all comp. sci. books are dry, particularly those with a Bell Labs background. Something about their writing style perhaps.

You may want to peruse Aho and Ullman's excellent C edition of Foundations of Computer Science. (That's Aho as in awk.) What you need for a good grounding all in one place. You can still pick up a paper edition if you want but they've also made it available as PDFs.

http://amazon.com/exec/obidos/ASIN/0716782847/mqq-20 http://i.stanford.edu/~ullman/focs.html

biomcgary• 14 years ago

Could this be used to secure a majority vote by asking people to submit their chunk of one of two files? The only way to get either file is by having the majority of the votes.

Damn Cool Algorithms: Homomorphic Hashing

Related Stories