Constructions

Let $\mathbb{G}$ be a commutative group under the addition law ($+$) and let $G \in \mathbb{G}$ be its generator. The group has an order $p$. We define a scalar multiplication $k \cdot G$ as $\underbrace{G+…+G}_\text{$k$~times}$.

Now assume that given an element $Q \in \mathbb{G}$ it is computationally unfeasible to find $k$ such that $Q = k \cdot G$. We have seen in a different challenge that it is easy to go from $G$ to $k \cdot G$ but now we are assuming that it is hard to go from $k \cdot G$ to $G$. This is called a one-way function. In this challenge, we will build a signature scheme and an encryption scheme based on this function.

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.