客服信息
我们支持 澳洲论文代写 Assignment代写、加拿大论文代写 Assignment代写、新西兰论文代写 Assignment代写、美国论文代写 Assignment代写、英国论文代写 Assignment代写、及其他国家的英语文书润色修改代写方案.论文写作指导服务
唯一联系方式Q微:7878393
热点文章
Shamir’s scheme
Why Shamir's scheme is perfectly secure?
“Shamir's Secret Sharing is an algorithm in cryptography. It is a form of secret sharing, where a secret is divided into parts, giving each participant its own unique part, where some of the parts or all of them are needed in order to reconstruct the secret.” A simple example would be suppose two people came upon a map that would lead them to an Island where ample amount of treasure is stored which will make them rich. Now to prepare for the adventurous expedition they would like to go home. The question arises i.e. who will keep the map since they both don't trust each other? An ideal solution to this situation would be to split the map in such a way that they both can't travel to the Treasure Island without each other. This concept basically defines Shamir's sharing scheme.
In Shamir's (k,n) threshold secret sharing scheme n participants hold shares generated from the secret s where any k of the parts are sufficient to reconstruct the original secret. A (k,n) threshold scheme has to satisfy the PERFECTNESS i.e. any information about s cannot be obtained from k − 1 or less shares and s can be completely recovered from k or more shares. This threshold scheme is an IDEAL secret sharing scheme if the maximum bit-size of share always equals the bit-size of s
Considering Shamir's scheme as an interpolating scheme based on polynomial interpolation as shown in the equation below:
F(x) = a0 + a1x + ... + ak - 1 xk-1
In the above equation coefficient a0 is the secret and all other coefficients are random elements in the field. In this the field is known to all participants. Each of the n shares is a point (xi, yi) on the curve defined by the polynomial, where xi not equal to 0. Given any k shares, the polynomial is uniquely determined and hence the secret a0 can be computed. However, given k - 1 or fewer shares, the secret can be any element in the field. Therefore, Shamir's scheme is a perfect secret sharing scheme
Figure 1 - Shamir's Interpolation Scheme
Hence, Sn = S1 + S2.
Similarly an interesting special case is perfect security: “an encryption algorithm is perfectly secure if a cipher text produced using it provides no information about the plaintext without knowledge of the key. If E is a perfectly secure encryption function, for any fixed message m there must exist for each cipher text c at least one key such that c = Ek (m).” Therefore, it would be necessary to combine all the key's k for each cipher text in order to obtain the original text or else it would be impossible for decryption to take place hence suggesting Shamir's theory to be perfect.
This scheme uses arithmetic in the field Zp, for some prime p (although any field could be used). The secret, K, is an element of this field. The dealer (the person who wants to share the secret), randomly selects k-1 elements of Zp, say, a1, a2, ..., ak-1 and forms the polynomial,
f(x) = K + a1x + a2x2 + ... + ak-1xk-1 (mod p)
For each of the participants, the dealer picks an element xi from Zp (but not 0) and calculates f(xi). The share given to participant i is the pair (xi, f(xi)
Now, if k participants pool their information, the polynomial f(x) can be reconstructed (for instance, by using the Lagrange interpolation formula) and the constant term (i.e., the secret) can be obtained by evaluating the polynomial at 0. If less than k participants combine their information, then the polynomial is not uniquely determined, and its constant term could be any element of the field. This scheme is thus a perfect (k,n)-threshold scheme.
Wikipedia - Shamir's Secret Sharing
Wikipedia - Information Theoretic Security
上一篇：The History On Spina Bifida Spinal Cord 下一篇：Pulmonary Edema Disease
