## Jumboji Requirements:

**Problem 1, public key set PSI**
1. Take two sets of (baby jubjub ECDSA) signatures A, B with |A| = n, |B| = m, n != m necessarily.
2. Define the set of public keys that with signatures in A as A_pk and B as B_pk.
3. A_pk and B_pk are subsets of a fixed set T, which is the total set of "meaningful" public keys. Currently |T| = 201, interested in |T| for size 25,000
4. Within either set A or B, all the signatures are from different public keys (thus |A_pk| = n, |B_pk| = m)
5. **Determine the intersection of A_pk and B_pk**

**Problem 2, public key set PSI + signature verify**
Same setup as before, but question is:
1. Determine the intersection of A_pk and B_pk while verifying both were correctly derived from A and B.
2. In other words, verify the users actually have valid signatures when finding public key overlap

## Primer on levelled BFV

Levelled BFV is different from Fully homomorphic BFV because the parameters are fixed beforehand and circuit can only perform multiplications uptill a certain depth.

It is always convenient to think of a BFV ciphertext as a vector of plaintext slots. There can be (depending on security parameter and depth of circuit) many thousands of slots. Each slot contains a plaintext and plaintext has a space modulus some prime $p$. x,-,+ between two ciphertexts applies the same operation slot-wise. For example,
$$
Enc\begin{pmatrix}
a_0 \\
b_0 \\
c_0 \\
d_0 \\
e_0 \\
f_0 \\
g_0 \\
h_0 \\
\end{pmatrix}
\times
Enc\begin{pmatrix}
a_1 \\
b_1 \\
c_1 \\
d_1 \\
e_1 \\
f_1 \\
g_1 \\
h_1 \\
\end{pmatrix}=
Enc\begin{pmatrix}
a_0a_1 \mod{p} \\
b_0b_1 \mod{p} \\
c_0c_1 \mod{p} \\
d_0d_1 \mod{p} \\
e_0e_1 \mod{p} \\
f_0f_1 \mod{p} \\
g_0g_1 \mod{p} \\
h_0h_1 \mod{p} \\
\end{pmatrix}
$$

Apart from x,+,-, BFV ciphertexts have one extra trick: **rotations**.

For rotations, one must view vector of slots as a 2x(length_of_vector/2) matrix.
$$
Enc\begin{pmatrix}
a_0 & b_0 & c_0 & d_0 \\
e_0 & f_0 & g_0 & h_0 \\
\end{pmatrix}
$$

One can rotate each row right/left by arbitrary no. of slots. For example, rotating the above ciphertext to left by 1 transforms it to:
$$
Enc\begin{pmatrix}
b_0 & c_0 & d_0 & a_0\\
f_0 & g_0 & h_0 & e_0\\
\end{pmatrix}
$$

One can swap the rows as well. For example, swapping the rows transforms the ciphertext t0:
$$
Enc\begin{pmatrix}
e_0 & f_0 & g_0 & h_0 \\
a_0 & b_0 & c_0 & d_0 \\
\end{pmatrix}
$$

### Keys

**Public Key**
Anyone can encrypt a message using $pk$ so that only the one with access to corresponding secret key $sk$ can decrypt the output.

**Rilearization key**
Relinerization keys are special keys in levelled HE. They are needed to reduce the degree of ciphertext after mutliplication.

A fresh ciphertext $ct$ is usually referred to as a degree 1 polynomial $ct = (c_0, c_1)$. The reason it is called degree 1 is because the decryption structure of fresh ciphertext is $c_0 + c_1s$ with $s$, the secret, as the variable.

Multiplication of two degree 1 ciphertexts results in a degree 2 ciphertext. For example $ct_0 \times ct_1 = ct_0ct_1 = (c'_0, c'_1, c'_2)$. The decryption structure of $ct_0ct_1$ equals $c'_0 + c'_1s + c'_2s^2$. Unless we reduce degree of output ciphertext after multiplication, the degree will grow exponentially with respect to depth of the circuit (i.e. no. of multiplications)

The procedure to convert a degree 3 ciphertext to degree 2 ciphertext is referred to as relinearization. It calculates $c_2s^2$ homomorphically. To do so, we require relinerization key.

**Galois key**

We wouldn't need rotations for PSI, so understanding of galois keys isn't necessary.

Galois keys are required to rotate ciphertexts/ swap rows. The reason they are called "Galois" keys is because ciphertext rotations are derived from galois theorem.

## Multi-party BFV

Multi-party BFV differs from BFV in only the key generation and decryption procedure. In BFV since the secret key is held by a single client, the client can generate all the necessary keys and decryt the ciphertext. In MP-BFV the ideal secret key is sharded among multiple parties. Key generation and decryption are multi-party protocols.

**Collective public key generation**
A single round protocol that outputs the collective public key. Anyone can encrpt their private input using the public key to produce a BFV ciphertext. It is important to note that no one can decrypt the ciphertext unless all parties collectivly decrypt it.

**Collective relirization key generation**
A two round protocol that outputs relinearization key.

**Collective decryption**
A single round protocol that decrypts a given BFV ciphertext.

For more inforamtion on steps of each protocol I will direct you to [this](https://github.com/Janmajayamall/bfv/blob/pk/notes/Multi%20Party%20BFV.md) document.

## PSI using MP-BFV

Let there be two parties $P_1$, $P_2$, and a public set of public keys of size $N$. Denote $pk_x$ as the $x^{th}$ public key in set $N$. Let $P_i$ denote their bit vector $B_i$ as a vector of bits ${0,1}^{N}$ where $B_i[x] = 1$ if and only if $P_i$ has valid signature from public key $pk_x$. Otherwise $B_i[x] = 0$.

1. $P_1$ and $P_2$ run collective public key generation protocol to generate $pk$.
2. $P_1$ and $P_2$ run collective relinerization key generation protocol to generate a single relinerization key.
3. $P_1$ encrypts its bit vector $B_1$ using $pk$ to output $ct_1$. $P_1$ sends $ct_1$ to $P_2$.
4. $P_2$ encrypts its bit vector $B_2$ using $pk$ to output $ct_2$. $P_2$ sends $ct_2$ to $P_1$.
5. Both $P_1$ and $P_2$ have access to $ct_1$ and $ct_2$. Both of them individually multiply $ct_1$ and $ct_2$ to output $ct_1ct_2$. Note that since each party set 1 only at slots that are "active" for them, the output ciphertext $ct_1ct_2$ encrypts a vector where any slot equals 1 when the slot is "active" for both $P_1$ and $P_2$.
6. $P_1$ generates their share to collecticely decrypt $ct_1ct_2$ and sends it to $P_2$.
7. $P_2$ generates their share to collectively decrypt $ct_1ct_2$ and sends it to $P_1$.
8. With both $P_1$ and $P_2$ having access to shares necessary to decrypt $ct_1ct_2$. They can independently decrypt the ciphertext and learn the public keys that are in common.

Note: $P_2$ can abort after learning $P_1$'s share to decrypt the ciphertext and prevent $P_1$ from learning the PSI output. This is a general problem in any multi-party protocol.

Note: the protocol can be easily extended to many parties at the expense of increasing communication linearly with no. of parties during key generation protocols.

For the protocol to work correctly, we will also require zero knoledge proofs for various operations. To be specific, we will require:
1. Proofs to ensure that each party performs collective key generation correctly.
2. Proofs to ensure that each party performs collective relinerization key generation correctly.
3. Proofs to ensure that each party performs collective decryption correctly.
4. Proof to ensure that each party encrypts correctly formed bit vector B_i using pk.

We're wroking on 1, 2, 3. But will require some help with 4.

**Questions for jumboji team**
1. Is the set of public key publicly accessible? I am thinking of assigning each public key a fixed slot. To do so, we will need some source of truth.
2. To check bit vector is correctly constructed we will require to verify ECDSA signatures in circuit. How expensive is verifying a single ECDSA signature in circuit?

## Prototype

https://github.com/Janmajayamall/MP-PSI

The prototype implements MP-PSI for 2-parties with set $N=2^{15}$ (i.e. can accomodate $2^{15}$ public keys) but without zero knowledge proofs.