FutureNerd Steve Witham says:
I've looked it up in Schneier. There doesn't seem to be anything about this exact situation; will the following work?
Alice makes a 128-bit random string and asks Bob to take the MD5 of the file with her random string prepended. This is impossible for Bob to compute without the file. Right?
Alice, however, can precompute as many of these as she wants (as long as she keeps them secret) so she doesn't have to actually keep the file.
Sounds like it should work. The one provisio that I would make is that if you want to have the hashes work for years, you have to accept the fact that MD5 will become weaker and weaker as years wear on. I trust it today, but I'm not sure its good to trust it to last ten or fifteen years... Perry