2.3. OTHER MATHEMATICAL PRIMITIVES 25
2.3.2 SHAMIR’S SECRET SHARING
In secret sharing, a data item ı is divided into n parts and distributed to n participants such that
any k parts can be used to reconstruct the data. e knowledge of k 1 parts does not provide
any information useful for reconstructing ı.
To create shares of a data item ı using Shamir’s [92] scheme, a prime number p is chosen
such that p > max.ı; n/. A random k 1 degree polynomial is then created, where the coeffi-
cients a
1
; : : : ; a
k1
are chosen randomly from a uniform distribution over the integers in Œ0; p
and a
0
D ı. is polynomial !.x/ D a
0
x
0
C a
1
x
1
C : : : C a
k1
x
k1
is then sampled at points
x D 1; : : : ; n to create shares !.1/; : : : ; !.n/. ese shares are called secret shares.
Any k out of the n shares created this way can be used to create a k 1 degree polynomial
!
0
.x/ using a polynomial interpolation method such as Lagrange’s. To reconstruct the original
data !
0
.x/ is evaluated at x D 0.
Shamir’s secret sharing is information theoretically secure. It is also additive homomorphic
in nature, which means that shares from two secrets can be added to add the secret. is property
of secret sharing is used in Chapter 5 to add data secured by the shares.
2.3.3 BLOOM FILTER
Bloom filter is a versatile space efficient probabilistic data structure used primarily to verify set
membership [122]. e Bloom Filter consists of an array of bits, initialized to 0 and k different
hash functions. To add an element to the Bloom Filter, the k hash functions are used to hash
the element to obtain k array positions. ese array positions are then set to 1. To verify an
element’s membership, it is hashed using the k hash functions and each resulting array position
is checked. If any of the bits at these positions are found to be 0, the element is not a member.
If all the bits are set to 1, it is a member. We have used Bloom Filter as a means of verification
in Chapter 7.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.