Protecting Your Secrets With Polynomials - Shamir's Secret Sharing скачать в хорошем качестве

Protecting Your Secrets With Polynomials - Shamir's Secret Sharing

Suppose there are n colleagues who all wish to have access to a secret. Giving the full secret to each person is too risky - one untrustworthy colleague can leak its entire contents. Splitting the secret into n parts and giving each colleague a piece is too impractical, as it would require all n participants to combine their pieces to recover the secret. Can we divide the secret into n parts, such that only a certain number of colleagues, k, need to combine their parts to recover the secret? C++ Implementation: https://github.com/emcapsulation/sham... This video explains how this is possible with Shamir's Secret Sharing, devised by Adi Shamir in 1979. The scheme provides a way to divide a secret into n parts (one share for each participant), such that the secret can be recovered if any k parts are combined. But, if fewer than k parts are combined, no information about the secret is revealed. This is my submission for the Summer of Math Exposition 4! #SoME4 Step 1. Choose a large prime, p, which is larger than n, k and your secret key, S. Step 2. Randomly select k-1 coefficients in the finite field F(p) - i.e., each coefficient is an integer in the range [0, p-1]. Use these coefficients to create the degree k-1 polynomial: P(x) = a_{k-1}x^{k-1} + a_{k-2}x^{k-2} + ... + a_{1}x^{1} + a_{0} (mod p) Ensure your secret is the y-intercept of this polynomial: P(0) = a_{0} (mod p) Step 3. Randomly select n distinct points on this polynomial (calculate the y-values modulo p). These are the shares. Give each participant one of these points. Shares = {(x_1, P(x_1)), (x_2, P(x_2)), ..., (x_n, P(x_n))} Step 4. When k or more people combine their shares / points, you can recreate the original degree k-1 polynomial using the Lagrange Interpolation Formula. Then the secret is simply the constant term, S = P(0) (mod p). ALL CHARACTERS PRESENTED ARE FICTIONAL. 00:00 Introduction 00:29 Idea #1: Encryption + Everyone Has the Key 01:26 Idea #2: Split the Key Into n Parts 02:22 Problem Summary 03:47 Overview of Shamir's Secret Sharing 04:28 How Many Points Define a Degree-k Polynomial? 07:40 Shamir's Secret Sharing Process 08:36 Example 10:04 Computer Representation 11:16 The Problem with Using Integers 14:18 Finite Fields 16:21 Adapting the Scheme to Use a Finite Field 18:26 Finite Field Benefits 19:53 Lagrange Interpolation Formula 25:33 Recovering the Secret Key 29:15 Explanation of Security 31:30 Proof of Interpolation Theorem 34:37 Conclusion