Proper encryption algorithm to use when encrypting data before backing it up to untrusted hosts?
Why not gpg? The libraries are already written and open sourced, so you don't have to recreate the wheel.

Split the file into blocks, then add a control file adding whatever metadata you need to keep the files together and belonging to the correct person. Encrypt each block with the user's key, and put it on an untrusted host. He will then be the only person who can decrypt the files. Assuming the untrusted host doesn't delete the blocks.