Prev: Sexual Contact Privacy
Next: Call for Papers: International Conference on Chemical Engineering ICCE 2010
From: Jason on 16 Jun 2010 16:10
Hi,

Say my secret is an n-bit number, under Shamir's scheme I need a
prime, the first prime larger than the secret, then I work in GF(p).
(Think that's correct)

Now in terms of a practical implementation, lets say im secret sharing
arbitrarily long data in 64-bit blocks. I have to assume my secret
could be all 64 bits, which means I will need a 65-bit prime.

What im trying to understand is what is the most efficient way to
share arbitrarily long data in small broken down blocks. i.e if I use
64-bit blocks then how big should my prime be to avoid bit-wasting.

Will 64-bit blocks with a 65-bit prime work ok? Or should I use 63-bit
blocks with a 64-bit prime. Because im working with 8-bit ASCII
secrets, it's obviously easier to work with 64-bit data blocks.

Please could someone give me some pointers on how to do this
correctly, ideally I want to hardcode a prime for my application
rather than searching for one bigger than the secret on each block.

Additionally how complex is it to compute shares in GF(p) from a
programming perspective? Will I have to use lookup tables? Any help
here is much appreciated, I'm not a mathematician and don't have
access to any field-calculation libraries for this project, so have to
do the calculations manually from the ground up.

Thanks for any help.
From: Maaartin on 16 Jun 2010 17:40
On Jun 16, 10:10 pm, Jason <tntcod...(a)hotmail.com> wrote:
> Say my secret is an n-bit number, under Shamir's scheme I need a
> prime, the first prime larger than the secret, then I work in GF(p).
> (Think that's correct)

You need a GF, but not necessarily a prime. Since any input can be
written conveniently as a sequence of bytes, working with GF(256) is a
good idea. This limits you to 255 shares, but this should be enough
for most purposes (if not then switch to GF(2**16)). One advantage of
using GF(256) is that the secret doesn't get expanded.

> Now in terms of a practical implementation, lets say im secret sharing
> arbitrarily long data in 64-bit blocks. I have to assume my secret
> could be all 64 bits, which means I will need a 65-bit prime.
>
> What im trying to understand is what is the most efficient way to
> share arbitrarily long data in small broken down blocks. i.e if I use
> 64-bit blocks then how big should my prime be to avoid bit-wasting.
>
> Will 64-bit blocks with a 65-bit prime work ok? Or should I use 63-bit
> blocks with a 64-bit prime. Because im working with 8-bit ASCII
> secrets, it's obviously easier to work with 64-bit data blocks.

Whatever prime you use, you end either with unconvenient input or with
unconvenient output sizes. You loose only about 1.5% but it's a lot of
bit fiddling. Using GF(256) or GF(2**64) wastes nothing in your case.

> Please could someone give me some pointers on how to do this
> correctly, ideally I want to hardcode a prime for my application
> rather than searching for one bigger than the secret on each block.
>
> Additionally how complex is it to compute shares in GF(p) from a
> programming perspective? Will I have to use lookup tables?

For such a large prime you can hardly use lookup tables, and you need
none. The most complicated part is the division using extended
Eulerian algorithm.

For GF(256) everything can be done using two small tables with 256
entries each (one for discrete log and one for exponentiantion).

> here is much appreciated, I'm not a mathematician and don't have
> access to any field-calculation libraries for this project, so have to
> do the calculations manually from the ground up.

I implemented it once in Java, the GF256 class is 44 lines and the
SecretSharing is 66 lines. You can have it to you if you want to.
There's nothing Java specific there.
From: Jason on 16 Jun 2010 18:06
On 16 June, 22:40, Maaartin <grajc...(a)seznam.cz> wrote:
> On Jun 16, 10:10 pm, Jason <tntcod...(a)hotmail.com> wrote:
>
> > Say my secret is an n-bit number, under Shamir's scheme I need a
> > prime, the first prime larger than the secret, then I work in GF(p).
> > (Think that's correct)
>
> You need a GF, but not necessarily a prime. Since any input can be
> written conveniently as a sequence of bytes, working with GF(256) is a
> good idea. This limits you to 255 shares, but this should be enough
> for most purposes (if not then switch to GF(2**16)). One advantage of
> using GF(256) is that the secret doesn't get expanded.
>
> > Now in terms of a practical implementation, lets say im secret sharing
> > arbitrarily long data in 64-bit blocks. I have to assume my secret
> > could be all 64 bits, which means I will need a 65-bit prime.
>
> > What im trying to understand is what is the most efficient way to
> > share arbitrarily long data in small broken down blocks. i.e if I use
> > 64-bit blocks then how big should my prime be to avoid bit-wasting.
>
> > Will 64-bit blocks with a 65-bit prime work ok? Or should I use 63-bit
> > blocks with a 64-bit prime. Because im working with 8-bit ASCII
> > secrets, it's obviously easier to work with 64-bit data blocks.
>
> Whatever prime you use, you end either with unconvenient input or with
> unconvenient output sizes. You loose only about 1.5% but it's a lot of
> bit fiddling. Using GF(256) or GF(2**64) wastes nothing in your case.
>
> > Please could someone give me some pointers on how to do this
> > correctly, ideally I want to hardcode a prime for my application
> > rather than searching for one bigger than the secret on each block.
>
> > Additionally how complex is it to compute shares in GF(p) from a
> > programming perspective? Will I have to use lookup tables?
>
> For such a large prime you can hardly use lookup tables, and you need
> none. The most complicated part is the division using extended
> Eulerian algorithm.
>
> For GF(256) everything can be done using two small tables with 256
> entries each (one for discrete log and one for exponentiantion).
>
> > here is much appreciated, I'm not a mathematician and don't have
> > access to any field-calculation libraries for this project, so have to
> > do the calculations manually from the ground up.
>
> I implemented it once in Java, the GF256 class is 44 lines and the
> SecretSharing is 66 lines. You can have it to you if you want to.
> There's nothing Java specific there.

Thanks very much, that helps a lot. If I can use GF(256) I can see it
will be ideal and simplify things no end as I can just share on a byte-
by-byte basis (0-255).

Is it definitely ok security wise to use GF(256)? It's just that
Shamir's paper originally recommended GF(p). I'm afraid I don't
currently understand fields well enough to know of any issues that may
arise from this?

I would really appreciate having a look at your Java implementation if
you have it handy somewhere.

Thanks again.

From: Maaartin on 16 Jun 2010 19:10
On Jun 17, 12:06 am, Jason <tntcod...(a)hotmail.com> wrote:
> Thanks very much, that helps a lot. If I can use GF(256) I can see it
> will be ideal and simplify things no end as I can just share on a byte-
> by-byte basis (0-255).
>
> Is it definitely ok security wise to use GF(256)?

I'm no cryptographer, but I'm quite sure it doesn't matter. I hope,
others will comfirm.

> It's just that Shamir's paper originally recommended GF(p).

I can't tell why.

> I'm afraid I don't currently understand fields well enough to know
> of any issues that may arise from this?

When you have any field, you can use polynomials over it, and there's
nothing more in Shamir's secret sharing. It works, since given enough
shares you can uniquely determine the result. It's perfectly secure,
since missing a single share the result can be anything. There's no
cryptography there.

> I would really appreciate having a look at your Java implementation if
> you have it handy somewhere.

You can find it here:
http://dl.dropbox.com/u/4971686/100617/GF256.java.txt
http://dl.dropbox.com/u/4971686/100617/SecretSharing.java.txt
http://dl.dropbox.com/u/4971686/100617/SecretSharingTest.java.txt

Instead of the log and exp tables I allocated a multiplication table,
this could be easily changed if necessary. It's uncommented, so feel
free to ask.
From: Bryan on 16 Jun 2010 22:44
Maaartin wrote:
> Jason wrote:
> > Is it definitely ok security wise to use GF(256)?
>
> I'm no cryptographer, but I'm quite sure it doesn't matter. I hope,
> others will comfirm.

Yes, as Maaartin wrote:

> When you have any field, you can use polynomials over it, and there's
> nothing more in Shamir's secret sharing. It works, since given enough
> shares you can uniquely determine the result. It's perfectly secure,
> since missing a single share the result can be anything.


--
--Bryan
 |  Next  |  Last
Pages: 1 2
Prev: Sexual Contact Privacy
Next: Call for Papers: International Conference on Chemical Engineering ICCE 2010