# Efficient Robust Private Set Intersection Additive ElGamal [duplicate]

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

• Could you please clarify where your problem exactly lies in the mentioned step (e.g., by editing your question)? – DrLecter Jan 28 '14 at 11:48
• I just approved this edit suggestion from an anonymous user. (It still needs someone else to approve it.) I assume that was you? You might want to register an account here, so that you'll be able to edit your posts more easily. – Ilmari Karonen Jan 29 '14 at 8:06
• @figlesquidge Good find btw. (First time the chat showed me it's real value.) – e-sushi Jan 30 '14 at 11:56