# Any reason to use Shamir given faster XOR threshold secret sharing algos?

## TL;DR:

Is the Kurihara algorithm really what it purports to be (dramatically faster but equally secure replacement for Shamir Secret Sharing)?

## Background

Shamir's secret sharing algorithm has the desirable properties of information theoretic security (possessing shares fewer than the threshold is no better than random data) and minimal storage (each distributed share is the same size as the original secret). However, it's very slow to compute, to the point that when dispersing a large file with Shamir you would typically use ordinary symmetric encryption for the file at large and protect only the symmetric key with Shamir.

As of around the year 2007 industrial researchers in Japan (Kurihara et alia at KDDI and others at Toshiba) and academics in China (Chunli et alia) have published papers showing how to use random numbers with simple XOR operations to accomplish the same level of information theoretic security and minimal storage, with performance hundreds of times better than Shamir Secret Sharing. Some of the algorithms offer arbitrary "(k, n)", aka "(threshold, sharecount)" flexibility, as Shamir also does.

Is there any reason to continue using Shamir versus the new XOR based threshold secret sharing algorithms?

• I would dispute that Shamir's method is "slow to compute"; given $k$ large files (each containing a set of shares for one particular id), the combination process is 'compute the coefficients $c_i$ based on the id's' (which you need to do once), and then 'for each position in the files, compute $c_1f_1 + c_2f_2 + ... + c_kf_k$. You might be able to faster than that, but not by a factor of hundreds. We typically don't do this, but mostly because there's no particular reason, if we're sharing a 1MByte file, to make each share 1 MByte big. Commented Aug 7, 2015 at 18:47
• Dispersal of 1 MB via Shamir is very slow, perhaps you're only considering the reassembly step? Commented Aug 7, 2015 at 19:11
• Re: "there's no particular reason, if we're sharing a 1MByte file, to make each share 1 MByte big", my question is in the context of wanting information theoretic security for the whole file. I don't know of any algorithm that claims to achieve that with a threshold secret sharing scheme that produces share sizes smaller than the original secret. Commented Aug 7, 2015 at 19:15
• As for generating the shares, well, assuming that the dealer has the original file, and the $k-1$ random file-sized values on hand (and for informational theoretic security, you need that much randomness), generating the share for a particular id is the same; compute the coefficients $c_i$ based on the id (in this case, $c_i = id^{i-1}$, and compute $c_1f_1 + c_2f+2 + ... + c_kf_k$ (and in this case, $f_1$ is the original file, and $f_2$ through $f_k$ are the random ones). Commented Aug 7, 2015 at 19:19
• I think the speed of Shamir's scheme is dependent on the field you are using, and it can be very fast. E.g., the Galois field in AES is typically implemented with table lookups and XORs. Commented Aug 8, 2015 at 8:16

Is the Kurihara algorithm really what it purports to be (dramatically faster but equally secure replacement for Shamir Secret Sharing)?

The algorithm being referred to is in this paper, and I believe that the speed benefits are at best marginal, if not nonexistent.

As for the speed benefits being marginal, well, normally we use secret sharing as a part of an overall algorithm achieving something else, and the time taken by the secret sharing algorithm is dominated by something else, and so the time taken doesn't really matter.

As for the speed benefits being marginal, well, that's because Shamir's method really is quite efficient; the generation of a share (once you've generated the randomess) is $k-1$ field multiplications and $k-1$ field adds; if you use the field $GF(256)$, this can be done with $2k-1$ table lookups, $k-1$ adds and $k-1$ xors. The recombination step (once you've converted the id's into coefficients) is $k$ field multiplications and $k-1$ field adds; similarly cheap.

Now, you ask, why does the paper claim to do so much better than Shamir? Well, that's because they were testing it against a Secret Sharing implementation that was never designed for performance. If you look into the implementation of SSSS, you'll see that it uses the GMP bignum library to perform the operations. Since the internal operations it uses are cheap (exclusive-or and shift left by one), the vast bulk of the time is spent in memory management (allocating and freeing memory). Furthermore, the field multiply implementation it uses is a generic one; if one is greatly concerned with speed, one could do better by optimizing for a specific field size (as I mentioned, a moderate sized field such as $GF(256)$ can be done quite fast using log and antilog tables).

Now, to be clear, I'm not saying that the SSSS implementation is bad; what I am saying that performance wasn't very high on the developers list. However, if speed is considered important, one can do quite a lot better.

As for your overall question, 'given that there are alternatives to Shamir, why do people generally stick with it?', well, I suspect that it's a combination of Shamir is good enough (a good implementation should run in a time that's competitive to Kulihara, and in any case, an I mentioned, we generally don't care), and that Shamir was the first (and people tend to stick with what's first - remember, people are still using RSA, even though we have better alternatives available).

• IIRC RSA was only the second public key encryption scheme. IIRC Knapsack based encryption was first. (although Knapsack is much harder to get right than RSA) Commented Aug 9, 2015 at 7:46
• @SEJPM: you sure? I thought RSA was first published in 1977; knapsack was first published in 1978. Commented Aug 10, 2015 at 2:44
• "The Merkle-Hellman knapsack encryption scheme (8.6.1) is important for historical reasons, as it was the first concrete realization of a public-key encryption scheme." - HAC, chapter 8.6 introduction. Commented Aug 10, 2015 at 8:05
• I guess the above sentence is referring to the fact that this (according to Wikipedia) was invented in 1974 (and published in '78) whereas RSA was invented in '77 and published in '78. Wikipedia HAC chapter Commented Aug 10, 2015 at 14:21
• @SEJPM: actually, if you go by 'first invented' and not 'first published' date, RSA still wins; a version of it was discovered by Clifford Cocks in 1973 (which he didn't publish until much later). In any case, as we're talking about public knowledge of a system, the 'first published' date would appear to be what's relevant. Commented Aug 10, 2015 at 14:43

Kurihara, Kiyomoto, Fukushima, and Tanaka (KKFT) claim a 900-fold speed increase over Shamir's scheme for $$(k,n)=(3,11)$$, which makes no sense since Shamir's scheme over $$GF(16)$$ is not that slow; 900 times faster would be far faster than memcpy. They must have used an extremely inefficient implementation of Shamir, and poncho's answer backs that up.

KKFT's scheme divides the secret into $$n_p-1$$ subblocks of equal length, where $$n_p$$ is prime and $$\ge n$$, and performs only aligned xors on those blocks and blocks of random bits thereafter. One can likewise write a transposed/bit-sliced implementation of Shamir's scheme that divides the secret into $$q$$ subblocks of equal length, where $$2^q$$ is the order of the Galois field ($$q > \log_2 n$$). In that form it's easier to compare the two.

In Shamir's scheme, to produce $$nq$$ subblocks of share from $$q$$ subblocks of secret and $$(k-1)q$$ random subblocks, you multiply the latter by an $$nq\times kq$$ matrix over $$\mathbb Z_2$$ in which the leftmost $$q\times q$$ subblocks are identity matrices and I suppose about half of the other entries are $$1$$. That's roughly $$\boxed{(k-1)q/2}$$ subblock-xor operations per output subblock if you multiply naively. To recover the secret you multiply by a $$q\times kq$$ matrix in which about half the entries should be $$1$$, so about $$\boxed{kq/2-1}$$ xors per output subblock.

In KKFT's scheme, to produce $$n_p-1$$ subblocks of share from $$n_p-1$$ subblocks of secret and $$(k-1)n_p-1$$ [sic] subblocks of random bits, you multiply by a $$(n_p-1)\times (kn_p-2)$$ matrix over $$\mathbb Z_2$$ in which each row has $$k$$ ones. That's $$\boxed{k-1}$$ xors per output subblock. To recover you multiply by a $$(n_p-1)\times k(n_p-1)$$ matrix in which about half the entries should be $$1$$, so about $$\boxed{k(n_p-1)/2-1}$$ xors per output subblock.

If the block-xor time dominates the run time, you'd therefore expect KKFT to be faster than Shamir for share generation by a $$O(\log n)$$ factor, and slower than Shamir for secret recovery by a $$O(n/\log n)$$ factor. The latter seems like it could be a problem for KKFT. Also, it's possible to improve the runtime of Shamir by exploiting special properties of Vandermonde matrices, and it's unclear whether similar optimizations are possible for KKFT.