<jupyter_start><jupyter_text>Lagrange's interpolation is a purely algebraic result, and it also holds in fields other than the field of real numbers. [Shamir's Secret Sharing](https://en.wikipedia.org/wiki/Shamir's_Secret_Sharing) (SSS) is a scheme in cryptography based on Lagrange's interpolation in a finite field. We will consider a naive version of the scheme using integer arithmetic as in the [example](https://en.wikipedia.org/wiki/Shamir's_Secret_SharingExample) in Wikipedia.SSS is used to secure a secret in a distributed way, most often to secure other encryption keys. The secret is split into $n$ parts, called shares. These shares are used to reconstruct the original secret. To unlock the secret via SSS, a minimum number $k$ of the $n$ shares are needed. An adversary who discovers any number of shares less than $k$ will not have any information about the secured secret, this is called perfect secrecy.SSS works by choosing a polynomial of degree $k-1$$$f(x) = a_0 + a_1 x + \dots a_{k-1} x^{k-1}$$where an integer $a_0$ is the secret to be secured, and $a_1,\dots,a_{k-1}$ are randomly chosen integers. The $n$ shares are given by the pairs$$(i, f(i)), \qquad i=1,\dots,n.$$Given any $k$ distinct shares $(x_j, f(x_j))$, $j=1,\dots,k$, the secret can be recovered by forming the Lagrange interpolation polynomial $p \in \mathbb P_{k-1}$ through these points, and by evaluating $p(0)$.Implement this recovery algorithm as the function `recover_secret`. This function must return an integer, not a float. You can use [round](https://docs.python.org/3/library/functions.htmlround) to convert a float to an integer.(When the integer arithmetic is used, an adversary with access to less than $k$ shares has information on the secret since the possible values of the other shares must lie on a smooth polynomial curve of degree $k-1$. This weakness is eliminated by using the arithmetic in a finite field.)<jupyter_code>import numpy as np
import scipy.interpolate as interp

def recover_secret(xs, ys):
    '''Given k shares returns the secret 
        
        Shares are given in the form xs = [x_1, ..., x_k] and 
        ys = [f(x_1), ..., f(x_k)]
    '''
    return 0 # a placeholder, your code goes here
rng = np.random.default_rng()
high = 10000
def generate_shares(a0, n, k):
    '''Returns the shares [f(1), ..., f(n)]
    
        a0 is the secret, n is the number of shares, 
        and k is the minimum number of shares required to recover the secret
    '''
    # Generate k-1 random integers between 0 and high
    a = rng.integers(high, size=k-1)
    a = np.append(a, a0)
    x = range(1, n+1)
    return np.polyval(a, x)

# Example from the Wikipedia article: the secret is 1234 and 
# the shares are (2, 1942), (4, 3402), (5, 4414)
xs = [2, 4, 5]
ys = [1942, 3402, 4414]
assert(recover_secret(xs, ys) == 1234)

# Test against the above generator
ys = generate_shares(1001, 10, 4)
xs = np.array([1, 2, 3, 4])
assert(recover_secret(xs, ys[xs - 1]) == 1001)

# With too few shares, we shouldn't get the secret 
xs = np.array([1, 2, 3])
assert(recover_secret(xs, ys[xs - 1]) != 1001)

# The order of shares shouldn't matter
xs = np.array([2, 1, 10, 5])
assert(recover_secret(xs, ys[xs - 1]) == 1001)<jupyter_output><empty_output><jupyter_text>**How to hand in your solution**1. Run the whole notebook by choosing _Restart Kernel and Run All Cells_ in the _Run_ menu    - Alternatively you can click the ⏩️ icon in the toolbar2. Click the link below to check that the piece of code containing your solution was uploaded to pastebin    - Note that the below cell is executed only if your code passes the above tests    - If you have changed the order of cells in the notebook, you may need to change the number in the below cell to the one in the left margin of the cell containing your solution3. Copy the link and submit it in Moodle    - You can copy the link easily by right-clicking it and choosing _Copy Output to Clipboard_<jupyter_code># Upload the code in the first input cell to pastebin
%pastebin 1<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.0929889298892989, 'fraction_numerical': 0.026322263222632227, 'mean_word_length': 4.019753086419753, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '344697', 'license': 'CC-BY-4.0', 'n_tokens_mistral': 1315, 'n_tokens_neox': 1207, 'n_words': 583, 'path': 'interpolation/homework.ipynb', 'repo_name': 'rmsb/notebooks', 'size': '4065'}