cipherchallenge@um6p ~ $

Secret Sharing

Miscellaneous 🧮

Question 1

Consider the following:

  • You have a random variable $X$, which is just a number (or a set of numbers) that is randomly chosen. In this case, $X$ is a string of n bits (where each bit is either 0 or 1), and each bit is chosen completely at random.
  • You also have another random variable $Y$, which is also an n-bit string. However, $Y$ doesn’t have to be random in the same way as $X$—it can follow any pattern. But $X$ and $Y$ are independent, meaning knowing $Y$ doesn’t tell us anything about $X$.
  • Now, we define a new random variable $Z$ by taking $X$ and $Y$ and combining them using something called the ”bitwise XOR operation” (written as $\oplus$). XOR works like this for each bit: – If the two bits are the same (both 0 or both 1), the result is 0. – If the two bits are different (one is 0 and the other is 1), the result is 1.

So, assuming we define $Z = X \oplus Y$, we apply this rule to each bit in the string separately.
Mashi 3la Raibi, 3la Jamila! đź’“

Polynomials are functions of the form: $$ f(x) = a_0 + a_1 x + \dots + a_n x_n $$ where $n$ is any non-negative integer and $a_0,\dots,a_n$ any fixed numbers with $a_n \ne 0$. We call:

  • $n$ the polynomial degree,
  • $a_0,\dots,a_n$ the polynomial coefficients and
  • $a_0$ the polynomial constant term.

Polynomial Interpolation

  1. Suppose that $f(x)$ is a polynomial of degree 2, i.e. of the form $f(x) = a_0 + a_1 x + a_2 x^2$. Let $f(1)=2$, $f(2)=5$, and $f(4)=2$. Find $f(x)$.
  2. Can you quickly write down a non-zero polynomial that vanishes at 1, 3 and 100?
  3. Same problem as before, but now with the two extra conditions: $f$ must have degree $\leq 3$ and also $f(50)=1$.
  4. Same problem as before, but now with the following conditions: $f$ must have degree $\leq 4$, $f(50)=1$ and $f(4)=3$.
  5. Now suppose that we have $n+1$ points $(x_0,y_0), (x_1,y_1), \dots, (x_n,y_n)$ such that $f(x_i)=y_i$ for $0 \leq i \leq n$. Can you generalize the above approach to find $f(x)$?

Secret Sharing

Raibi Jamila, often referred to simply as “Raibi,” is a beloved yogurt-based drink that has become a staple in Moroccan culture. Many have tried to replicate the drink, but none have succeeded in capturing its unique flavor. The secret recipe for Raibi is known only to a few select individuals, who have sworn to keep it a secret. To prevent these individuals from sharing the secret and to ensure it is never lost, we are going to construct a scheme that allows the secret to be shared among a group of people in such a way that the secret cannot be revealed unless a minimum number of the group’s members act together to pool their knowledge.