Create alternative blockchain with proof-of-work For learning purposes, I want to create an alternative special-purpose blockchain. It would use a proof-of-work function that is different than the one in Bitcoin.

Short of forking bitcoin and going from there, where should I look into starting? 

The data that the blockchain would be storing are public keys.

Bitcoin wiki: https://en.bitcoin.it/wiki/Alternative_chain
What you're asking to do here is actually the definition of forking bitcoin.
Short of doing this yourself in code, there are services such as http://coincreator.net/ that will accomplish your goal. CoinCreator allows for you to pick your proof-of-work function from a set of predefined functions.

Good Luck!