2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Could you please clarify where your problem exactly lies in the mentioned step (e.g., by editing your question)? $\endgroup$ – DrLecter Jan 28 '14 at 11:48
  • 1
    $\begingroup$ 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. $\endgroup$ – Ilmari Karonen Jan 29 '14 at 8:06
  • $\begingroup$ @figlesquidge Good find btw. (First time the chat showed me it's real value.) $\endgroup$ – e-sushi Jan 30 '14 at 11:56