The idea is simple: if you have data, then you can generate the key from data itself to encrypt and decrypt than data. Then you use hash of encrypted data to look up if server (or just other side) has the same data. If hash exists, no need to send to server - just tell server to bump references. If hash does not exists, just upload data. The key derived from data needs to be stored locally - if you lose it, you will lose data too.
key = f(data);
Which is to say that every file has a globally 1-to-1 mapping to its encrypted version. I'm not sure how they are storing the (User, [(Filename,Key)]) data, but this is ideally encrypted on a per user basis, making any sort of per-user lookup attacks moot.