I didn't read this paper very closely, but something seems catastrophically wrong, particularly with the authors' claimed speed for Shamir sharing.
The authors claimed that they tested the sharing systems on secrets of 4.5MB in length; their graph shows Shamir's scheme as taking about a hundred seconds for each individual operation.
I've just thrown together a script in Python, using my own (quite old) implementation of Shamir's scheme. The program generates a 4.5MB random string, and shares and reconstructs it once for each set of parameters they tested. The whole program, random number generation (I used RC4), splitting, joining, and all, for all six parameter sets, finishes in 20s on my aging 2.6GHz Pentium 4 machine.
I can now add (quick and dirty) timing to my program, calling the clock(3) function to count CPU seconds. (This is Linux; it counts in centiseconds.) Secret recombination is always too fast to measure; I'll round everything up. Splitting takes up to 6cs -- a bit over a twentieth of a second (this happens when creating 109 shares; their program takes a second to do this). The whole thing, not counting random number generation, takes 28cs.
Admittedly, I'm not using SSSS, and I'm not using 128 byte chunks. But why would I? Doing bignum maths here is crazy. Each individual byte is shared separately and independently, using Shamir in GF(2^8). I use discrete log() and exp() tables, and XOR. This is still just as secure (unless you have enough shares, each secret byte is uniform and independent of your view).
This wasn't my idea. I got it from shsecret.c, written by David Madore, and placed by him into the public domain: [quatramaran.ens.fr
]. Others have come up with the same idea elsewhere, I believe independently.
The implementation is my own, though, and I used a standard polynomial basis for GF(2^8) rather than the Conway multiplication that David used (not that it matters when you're just doing table lookups).
So: my old implementation (written in 2000, according to my revision control system, with a few cosmetic changes since) of Shamir's sharing system seems to knock the pants of Kurihara et al's shiny new one.
What's going on here? Where did the idea come from that Shamir is slow?