Efficient Robust Private Set Intersection Questions

Question

I am trying to implement Efficient Robust Private Set Intersection using additive ElGamal.

I am trying to run the full protocol mentioned in Section 3.4 on the following inputs:

• $p = 17$ (prime)
• $g = 6$ (generator)
• $x = 5$ (private key)
• $k = g^x \pmod p = 6^5 \pmod{17} = 7$ (public key)

Suppose the clients inputs are 1, 2. Then $P(x) = (x-1)(x-2) = x^2-3x+2$, and therefore the coeffiecients to encrypt are $(1, -3, 2)$. I chose $y = 10$ and so the encrypted values are:

• $1$ becomes $(15,12)$
• $-3$ becomes $(15, 1)$
• $2$ becomes $(15, 4)$.

The Server Side Input Set $S=\{1\}$ and the random value $r0$ corresponding to $\{1\}$ is $r_0=2$.

---

With the above problem in context, I have some questions:

1. What does P 0,j refer to in Step 7. Can you please give an example?

2. In Step 8, suddenly variable i is introduced along with j. What does i, j, refer to?

3. In Step 8, ENC() function has a ; in between. How do we interpret ENC(a;b)?

Answer 1

In general, you might find it more useful to look at the full description of the protocol on page 137 of the paper you cite, rather than the general overview on the preceding pages.

To answer your specific questions:

1. From page 137, step 8 (which corresponds to step 7 in the general overview):

   "For each $y_j \in Y$, $S$ chooses a random polynomial $P_{0,j}$ of degree $k + k (\lfloor \log n \rfloor + 1)$ with constant coefficient equal to $0$..."

   To choose a random polynomial, you just choose every coefficient (except the lowest one, since that's specified to be zero) uniformly at random from the field you're using.

2. From page 137, step 9:

   "For each $y_j \in Y$, for $1 \le i \le 10k(\lfloor \log n \rfloor + 1)$, using the sharing polynomials obtained in Steps 6, 7, 8, and a random value $r_{i,j}$, $S$ computes: $Out_{i,j} = $..."

3. See section 2, "Definitions and Building Block Protocols" on pp. 127–128. It looks to me like the choice between using a comma or a semicolon to separate the arguments to $\rm ENC$ is merely a stylistic / typographical one: ${\rm ENC}(x,r)$ and ${\rm ENC}(x;r)$ should mean the same thing.

4. Yes, there presumably is, although I cannot absolutely confirm that for you without actually reading the whole paper.