2
$\begingroup$

TL;DR:

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

https://scholar.google.com/scholar?q=kurihara+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?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – poncho
    Aug 7, 2015 at 18:47
  • $\begingroup$ Dispersal of 1 MB via Shamir is very slow, perhaps you're only considering the reassembly step? $\endgroup$
    – WolfRevokCats
    Aug 7, 2015 at 19:11
  • $\begingroup$ 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. $\endgroup$
    – WolfRevokCats
    Aug 7, 2015 at 19:15
  • $\begingroup$ 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). $\endgroup$
    – poncho
    Aug 7, 2015 at 19:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Chris
    Aug 8, 2015 at 8:16

1 Answer 1

Reset to default
5
$\begingroup$

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).

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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) $\endgroup$
    – SEJPM
    Aug 9, 2015 at 7:46
  • $\begingroup$ @SEJPM: you sure? I thought RSA was first published in 1977; knapsack was first published in 1978. $\endgroup$
    – poncho
    Aug 10, 2015 at 2:44
  • $\begingroup$ "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. $\endgroup$
    – SEJPM
    Aug 10, 2015 at 8:05
  • $\begingroup$ 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 $\endgroup$
    – SEJPM
    Aug 10, 2015 at 14:21
  • $\begingroup$ @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. $\endgroup$
    – poncho
    Aug 10, 2015 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.