On Sat, Oct 3, 2009 at 12:42 AM, Kevin W. Wall <kevin.w.w...@gmail.com> wrote: > > The question that a colleague and I have is there any cryptographic > purpose of computing the independent coefficients over the finite > field, Zp ?
Here is a concrete example of information leakage when not using Zp. Assume that the secret and each additional coefficient is a positive integer less than 3 (intentionally picking a very small range to keep the math simple). Assume there are two shares and that both shares are needed to recover the secret. a0 = the secret and a1 is randomly chosen in the same range. q(x) = a0 + a1*x We can make a table of all possible coefficients (a0, a1) and share values (q(1), q(2)): (a0, a1, q(1), q(2)) = { (0, 0, 0, 0) (0, 1, 1, 2) (0, 2, 2, 4) (1, 0, 1, 1) (1, 1, 2, 3) (1, 2, 3, 5) (2, 0, 2, 2) (2, 1, 3, 4) (2, 2, 4, 6) } >From this table, it is possible to deduce a0 (the secret) knowing only q(2), assuming that q(2) is not 4 or 2. Even then, you know that the secret is not odd. Knowing only q(1) leaks a little less information, but you can still fully determine the secret if q(1) = 0 or 4, and partially determine the secret if q(1) is 1 or 3. Intuitively, the information leakage occurs because the range of q(x) is larger than the range of the secret a0. Conversely, when using the set of integers mod 3, the table looks like this: (a0, a1, q(1) mod 3, q(2) mod 3) = { (0, 0, 0, 0) (0, 1, 1, 2) (0, 2, 2, 1) (1, 0, 1, 1) (1, 1, 2, 0) (1, 2, 0, 2) (2, 0, 2, 2) (2, 1, 0, 1) (2, 2, 1, 0) } It's easy to confirm by visual inspection that knowledge of q(1) or q(2) alone does not reveal any information about the secret a0. > > The only reason that we can see to doing this is to > keep the sizes of the shares Si bounded within some reasonable range > and it seems as though one could just do something like allowing T > choose random coefficients from a sufficient # of bytes and just > do all the calculations without the 'mod p' stuff. In any real implementation, you'd want to use a binary finite field, such as GF(2^8) or GF(2^16). This is way faster than using a non-binary finite field. The 'mod p' stuff would be optimized into a series of fast table lookups. For example, if you want to generate shares for a 512-bit ECC Key, you would first divide it into 64 bytes (each of which fits inside GF(2^8)), and then compute 64 independent shares. Each multiply would be a couple table look-ups and your done. Conversely, If you were using a non-binary finite field, your best bet is probably using 2^521-1 (a.k.a., P-521 or the 13th Mersenne prime). However, this is way slower than 64 GF(2^8) operations because the time required to multiply two large integers grows with the square of the size n. (Technically you can do it in n log n operations by using Fourier Transforms, but this is only useful with really big integers and you have to watch for rounding errors). The modulo computation with P-521 would just be a couple BIGNUM subtractions. Even worse, if you used the set of integers (Z), the evaluated points on the polynomial would require about d*64 bytes of storage, where d is the degree of your polynomial (i.e., the threshold number of shares needed to recover the secret). The time required to do all these multiples would roughly grow quadratically with the threshold (or rather n log n because at this point, using Fourier transforms starts to become appealing). This is all moot, though, because using Z is not secure. > > We thought perhaps > Shamir did the calculations of Zp because things like Java's BigInteger > or BigDecimal weren't widely available when came up with this > scheme back in 1979. > Even today, I don't see why anyone would use BigInteger or BigDecimal for Shamir's Secret Sharing. As I mentioned above, the time required for a BigInteger operation grows faster than linearly with the size of the secret (either n log n or n^2), as opposed to linear growth with a binary field. You might argue that BigInteger and BigDecimal are 'easy to use', but when considering the substantially slower execution time and the extra burden of dealing with very large shares, it's really not a net savings. Besides, there are many useful implementations of Shamir Secret sharing that you could import into Java with much less work required than reimplementing the algorithm from scratch. Cheers, -Matt Matt Ball, Chair, IEEE P1619 Security in Storage Working Group Staff Engineer, Sun Microsystems, Inc. 500 Eldorado Blvd, Bldg #5 BRM05-212, Broomfield, CO 80021 Work: 303-272-7580, Cell: 303-717-2717 --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com