Challenges

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.

The time complexity describes the amount of computer time it takes to run an algorithm. It is estimated by counting the number of elementary operations performed by the algorithm. Since an algorithm’s running time may vary among different inputs of the same size, one commonly considers the worst-case time. Algorithmic complexities are classified according to the type of function appearing in the big O notation. Here are some examples:

Multiplication algorithms

Schoolbook multiplication

Consider this example $102 \times 257$:

Scalar multiplication

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}$.

1. Consider $105 \cdot G$. How many additions does it involve?
2. Now consider the binary decomposition of $105 = 2^6 + 2^5 + 2^3 + 2^0$. It can be written as

$105 = ((((((((((1 · 2 + 1) · 2) + 0) · 2) + 1) · 2) + 0) · 2) + 0) · 2) + 1$. Given that a doubling (multiplication by 2) has the same cost as an addition, how many additions $105 \cdot G$ involves?

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.

Primes are of great theoretical and practical value in cryptography. A primality test is an algorithm for determining whether an input number is prime or not.

Naive but deterministic

The simplest primality test is trial division: given an input number, $n$, check whether it is divisible by any prime number between 2 and $\sqrt{n}$. If so, then $n$ is composite. Otherwise, it is prime.

The prime number theorem: the distribution of primes is $π(n) \sim n/\log(n)$ where $π(n)$ is the prime-counting function (the number of primes less than or equal to $n$) and $\log(n)$ is the natural logarithm of $n$.

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.