You're right, any additively homomorphic encryption would do. I chose Paillier because it is was reviewed extensively and has a ton of libraries written for it. Unfortunately ElGamal is multiplicatively homomorphic so it can't be used.

BootstrapCoinDev: I advise you to read J. D. Bruce's paper. He explains in detail how new nodes decide which blockchain is the correct one. www.cryptonite.info/files/mbc-scheme-rev2.pdf.

mistercoin: Thank you! I haven't really thought about it, but it would be nice to see a coin using this scheme. Although it probably can be improved.

Maybe Cryptonite could be hard-forked but it would be difficult. It is easier to create a new coin.

This paper attempts to improve the mini-blockchain scheme and make it private and even more scalable. This is achieved by encrypting transaction amounts and accounts balances with homomorphic encryption, allowing it to perform addition and subtraction on encrypted values without revealing the plaintexts. Another aspect of this paper are ”expiration dates” on accounts so that users need to pay fees periodically to maintain their accounts. This way abandoned accounts are automatically pruned from the mini-blockchain.

https://drive.google.com/file/d/0B21vncLoIlIyaVpGVFN5c1VFdmM/view?usp=sharing

Edit (24/04/2015): After receiving some constructive criticism, I redesigned the scheme and rewrote the paper. The objective is still the same, to make a more private version of the mini-blockchain scheme. It can be found at the following link,

https://drive.google.com/file/d/0B21vncLoIlIyUldiZTRxSTYyNGc/view?usp=sharing