# PETS T3 Group 12

* assignment sheet: https://iaik.tugraz.at/pets
- `CatDogHamsterBirdGecko`
* testsystem: https://pets.student.iaik.tugraz.at/result-T3.html

## Theory Questions (15 points)

### 1.4.1 Shamir Secret Sharing (2 points)

* $a$ ... random values forming the coefficients of the polynomial (secret, not shared)
* $\alpha$ ... x-coordinates of shared points
* if they are the same for all shares, the Lagrange Constants are also the same (see Algorithm 1)

To be able to compute linear functions on the shares (see 1.2.1), the $\alpha_i$ used to compute the points ($\alpha_i, \Phi(\alpha_i)$) need to be the same for all shares (while the $a_i$ defining the polynomial are different) so that the Lagrange Constants are also the same (see Algorithm 1), and what remains (sum in $reconstruct$) has the desired linearity properties (because both $a$ and $b$ are multiplied with the same $c$).

Given the Lagrange Constants $c_1 , ..., c_n$ of the points' $x$ coordinates $\alpha_1, ... \alpha_n$:

* reconstruct one share:
* $a = reconstruct(\Phi(a_1), ..., \Phi(a_n)) = \sum_{i=1}^{n} c_i \Phi(a_i)$
* reconstruct sum of two shares $<s> = <a> + <b>$
* (we use the variable $s$ for the sum, while section 1.2.1 reuses $c$)
* $r = a + b$
* $=reconstruct(\Phi(a)) + reconstruct(\Phi(b))$
* $=\sum_{i=1}^{n} c_i \Phi(a_i)$ + $\sum_{i=1}^{n} c_i \Phi(b_i)$
* $= \sum_{i=1}^{n} [ c_i \Phi(a_i) + c_i \Phi(b_i) ]$
* $= \sum_{i=1}^{n} c_i (\Phi(a_i) + \Phi(b_i))$
* $= \sum_{i=1}^{n} c_i \Phi(s_i)$
* $= reconstruct(\Phi(s)) = s$
* so $\Phi(s_i) = \Phi(a_i) + \Phi(b_i)$
* ... this is for $k = l = 1$ and $m=0$. Check if this matches with formulas in 1.2.1
* $s_i = k a_i + l b_i + m$
* $s = \sum_{i=1}^{n} [ c_i * (k a_i + l b_i + m)]$
* $= \sum_{i=1}^{n} [ c_i * k * a_i + c_i * l * b_i + c_i * m]$
* $= \sum_{i=1}^{n} [ c_i * k * a_i ] + \sum_{i=1}^{n} [ c_i * l * b_i] + \sum_{i=1}^{n} c_i * m$
* $\sum_{i=1}^{n} c_i * m$
* $m \sum_{i=1}^{n}c_i$
* $m * 1 = m$
* because the sum of the Lagrange (interpolation) coefficients is [always](https://math.stackexchange.com/a/1325342) 1
* $= k \sum_{i=1}^{n} [ c_i * a_i ] + l \sum_{i=1}^{n} [ c_i * b_i] + m$
* $= k * reconstruct(a) + l * reconstruct(b) + m$
* $= k * a + l * b + m$

### 1.4.2 Parameter Selection (3 points)

You can specify following parameters:
* degree of polynomial
* the greater the more secure
* the smaller the faster
* coefficient modulus
* specfices the amount of budget regarding the noise (important for the number of multiplications possible)
* the bigger the more budget
* the smaller the more security
* plaintext modulus
* =2 for boolean cicuits
* otherwise choose depending on size of the numbers your working with (to evade computation overflows)
* the bigger the more noise (more budget consumption)

+----------------------------------------------------+
| poly. degree | max coeff. modulus bit-length |
+---------------------+------------------------------+
| 1024 | 27 |
| 2048 | 54 |
| 4096 | 109 |
| 8192 | 218 |
| 16384 | 438 |
| 32768 | 881 |
+---------------------+------------------------------+

plaintext modulo choice:
TODO c in impl

### 1.4.3 SIMD encoding (3 points)

One can use the batch encoder to multiply for all images all batches with the one-hot encoded array and then sum up over all images.
If every server does this, it can be quiet an improvement.

TODO: check if possible to use decrypt and reconstruct with batch encoder

### 1.4.4 PIR overhead (3 points)

TODO: redo with l different servers not just one

#### Communication overhead:
* the query instead of an index is one-hot encoded and therefore of bit-size == the max # images that can be stored
* ~~the send back list of words is the same size as the picture. Here should no significant overhead be~~

#### Computational overhead:
* key generation
* one-hot encoded array encryption client side
* max image index * pixel number homo. multiplicaitons
* number of pixel rows homo. addtions
* number of blocks homo. encryptions, reconstructions and concatenations.

### 1.4.5 PIR with HE (2 points)

bo?
* parallelize
* fault tolerance

### 1.4.6 Resilience of the Protocol (2 points)

TODO: look Vo