The Stasi documents are probably the biggest project in this category:
"The Stasi files are something else entirely. In 2000, the BStU collected them and sent them to Magdeburg, a decaying East German industrial city 90 miles west of Berlin. In hand-numbered brown paper sacks, neatly stacked on row after row of steel shelves, they fill a three-story, 60,000-square-foot warehouse on the northern edge of town. Each sack contains about 40,000 fragments, for a total of 600 million pieces of paper (give or take a hundred million). And each fragment has two sides. That's more than a billion images."
Though it has dark side: I heard rumours that the reconstructions is deliberately slowed down by low-tech. The Stasi (east German secret police) amassed documents that could embarrass powerful people.
It's entirely possible if you're working with a reasonably small amount of material. Not even that hard to do. It's easier than a jigsaw puzzle. It's also possible to build a primitive crossbow out of pencils, rubber bands, and paper clips. (had a boring office job for a few years)
I'd have thought that the security services, NRO for example, have software that receives scans of paper strips and does edge matching to reconstruct the page.
It doesn't seem too hard algorithmically (to this non-programmer) to do that, something like: take all strips and analyse them for position of edge markings; take all edges and compare the edge-marking positions giving a matching score by pair, match up the best scores and display to a user for final arrangement.
If you were looking at fragments of paper I'd probably go with a letter matching based on pre-analysis of the font used (by machine). use the letter matching to arrange the fragments as if they were strips and proceed from there.
If you need to have something be permanently "shredded", you should consider a "high security" shredder. That is, one that not only shreds vertically, but horizontally as well. After that is finished, but the little pieces into water and turn it into mash.
The other option is using acid, or....
not writing things down that will get you put in prison.
But by diamond shredding you are only increasing N the same method of reconstruction by edge analysis still works. Like nuking from orbit, burning, pulping, or other method of complete destruction is the only way to be safe.
It is typically not feasible to burn a large amount of paper inside of an office without anyone noticing. You could turn the paper into mash in an office. You could not do the same by burning it.
People think of shredding as destroying a document, but in fact it's just scrambling it. And with enough time, someone will be able to unscramble it. Documents which truly need to be destroyed should probably be burned or pulped.
Good thing I put my shredded paper in my worm compost bin. (Well, actually I do that because it's beneficial to mix some lower-nitrogen waste in with the higher-nitrogen waste (vegetable scraps).
But it really does destroy the shreds nicely, even if it takes a few weeks.
Ecch. Years ago, working on genomics stuff, it occurred to me that the same kind of approach could unshred documents. I didn't pursue it, because I didn't think of who the market would be. (Well, that and the usual other million distractions.)
In some contexts it may be easier to find a hard drive with the electronic original text of the document that was subsequently printed, filed for a while, and then shredded.
http://en.wikipedia.org/wiki/Paper_shredder#Unshredding