Wouldn't it be possible to make use of all those
~250 Phash/s of computer power that we today waste on solving fabricated algorithms? The essence of the Internet is information, so if we are looking for something concrete to be mined, encrypted information seems like a valid contender.
What is there to decrypt? The first thing that comes to my mind is Wikileaks. There are X amounts of encrypted documents that still remain hidden from us.
"What's Wikileaks hiding in its 400GB of 'insurance' files?""The triumvirate of files are locked with NSA-approved AES encryption and weigh in at a beefy 3.6GB, 49GB and 349GB respectively.
Without a secret key to decrypt them (or a time machine and a very powerful computer) the files are useless blobs of ones and zeros that allow the safe dispersal of secret information beyond the reach of anyone who might want to interfere with Wikileaks."
Mining is one the biggest flaws of Bitcoin, because it's not used productive in any way. It's a common thing to hear that, "Bitcoin seems like a complete waste of resources".
As stated there are already coins that support this kind of work, Gridcoin probably being the most versatile. You could easily create a BOINC project to do this kind of decrypttion work in a distributed manner and Gridcoin supports BOINC projects. Creating a Proof of Work though that only directs itself to this purpose is questionable though, since it would lead to an insecure and unstable function. So Gridcoin is probably the only platform that currently has the theoretic ability to do this kind of work.
Another apporach for a more useful Proof of Work is basically Little Duke's IDCoin proposal. Here the Proof of Work involves maintaining PGP keys, so it also becomes a track record for identification and good or bad actors. I believe the Zennet project is also looking to integrate a similar kind of Proof of Work for their project, since it requires some form of trust record.