Jubmoji PSI - HackMD

Jumboji Requirements:

Problem 1, public key set PSI

Take two sets of (baby jubjub ECDSA) signatures A, B with |A| = n, |B| = m, n != m necessarily.
Define the set of public keys that with signatures in A as A_pk and B as B_pk.
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
Within either set A or B, all the signatures are from different public keys (thus |A_pk| = n, |B_pk| = m)
Determine the intersection of A_pk and B_pk

Problem 2, public key set PSI + signature verify
Same setup as before, but question is:

Determine the intersection of A_pk and B_pk while verifying both were correctly derived from A and B.
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,

E n c (\begin{matrix} a_{0} \\ b_{0} \\ c_{0} \\ d_{0} \\ e_{0} \\ f_{0} \\ g_{0} \\ h_{0} \end{matrix}) \times E n c (\begin{matrix} a_{1} \\ b_{1} \\ c_{1} \\ d_{1} \\ e_{1} \\ f_{1} \\ g_{1} \\ h_{1} \end{matrix}) = E n c (\begin{matrix} a_{0} a_{1} \mod p \\ b_{0} b_{1} \mod p \\ c_{0} c_{1} \mod p \\ d_{0} d_{1} \mod p \\ e_{0} e_{1} \mod p \\ f_{0} f_{1} \mod p \\ g_{0} g_{1} \mod p \\ h_{0} h_{1} \mod p \end{matrix})

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.

E n c (\begin{matrix} a_{0} & b_{0} & c_{0} & d_{0} \\ e_{0} & f_{0} & g_{0} & h_{0} \end{matrix})

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:

E n c (\begin{matrix} b_{0} & c_{0} & d_{0} & a_{0} \\ f_{0} & g_{0} & h_{0} & e_{0} \end{matrix})

One can swap the rows as well. For example, swapping the rows transforms the ciphertext t0:

E n c (\begin{matrix} e_{0} & f_{0} & g_{0} & h_{0} \\ a_{0} & b_{0} & c_{0} & d_{0} \end{matrix})

Keys

Public Key
Anyone can encrypt a message using

p k

so that only the one with access to corresponding secret key

s k

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

c t

is usually referred to as a degree 1 polynomial

c t = (c_{0}, c_{1})

. The reason it is called degree 1 is because the decryption structure of fresh ciphertext is

c_{0} + c_{1} s

with

s

, the secret, as the variable.

Multiplication of two degree 1 ciphertexts results in a degree 2 ciphertext. For example

c t_{0} \times c t_{1} = c t_{0} c t_{1} = (c_{0}^{'}, c_{1}^{'}, c_{2}^{'})

. The decryption structure of

c t_{0} c t_{1}

equals

c_{0}^{'} + c_{1}^{'} s + c_{2}^{'} s^{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_{2} s^{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 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

p k_{x}

as the

x^{t h}

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

p k_{x}

. Otherwise

B_{i} [x] = 0

$P_{1}$ and
$P_{2}$ run collective public key generation protocol to generate
$p k$ .
$P_{1}$ and
$P_{2}$ run collective relinerization key generation protocol to generate a single relinerization key.
$P_{1}$ encrypts its bit vector
$B_{1}$ using
$p k$ to output
$c t_{1}$ .
$P_{1}$ sends
$c t_{1}$ to
$P_{2}$ .
$P_{2}$ encrypts its bit vector
$B_{2}$ using
$p k$ to output
$c t_{2}$ .
$P_{2}$ sends
$c t_{2}$ to
$P_{1}$ .
Both
$P_{1}$ and
$P_{2}$ have access to
$c t_{1}$ and
$c t_{2}$ . Both of them individually multiply
$c t_{1}$ and
$c t_{2}$ to output
$c t_{1} c t_{2}$ . Note that since each party set 1 only at slots that are "active" for them, the output ciphertext
$c t_{1} c t_{2}$ encrypts a vector where any slot equals 1 when the slot is "active" for both
$P_{1}$ and
$P_{2}$ .
$P_{1}$ generates their share to collecticely decrypt
$c t_{1} c t_{2}$ and sends it to
$P_{2}$ .
$P_{2}$ generates their share to collectively decrypt
$c t_{1} c t_{2}$ and sends it to
$P_{1}$ .
With both
$P_{1}$ and
$P_{2}$ having access to shares necessary to decrypt
$c t_{1} c t_{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:

Proofs to ensure that each party performs collective key generation correctly.
Proofs to ensure that each party performs collective relinerization key generation correctly.
Proofs to ensure that each party performs collective decryption correctly.
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

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

River Ruby

2023/12/14 23:50:23

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.

Yes it will be!

2023/12/14 23:53:33

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. 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?

Right now it is 3,039 R1CS constraints to verify an efficient ECDSA signature (a rewrite of the formula for cheaper ZK verification, research from me and dan!) We should assume people will have bitvectors with 100-5000 slots filled out. It might just be unattainable to do this in a ZKP client-side, as this will entirely happen on mobile phones. I'm okay for clients to be trusted to generate the right bitvector to do computation on. We should do some sanity check of <5000/25000 slots filled so people can't just read your collection by doing a bitvector of all 1s. but most people will not be adept enough to pull this off, and if people do that's probably a win that people are investigating that deeply!

Janmajayamall

2023/12/15 08:12:04

> 3,039 R1CS I really don't know how to translate this to proving time on phone ;) Okay, this looks good to me. So now we need to figure out how to integrate PSI with jumboji app. Let's discuss this over call :)

Jumboji Requirements:

Primer on levelled BFV

Keys

Multi-party BFV

PSI using MP-BFV

Prototype

Read more

Program obfuscation via local mixing

Obfuscation bounty

Phantom zone v0 blog post (old version)

ADP