---
# System prepended metadata

title: PETS T3 Group 12

---

# 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
