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

  • $\begingroup$ Section 3.4 of what? Step 7 of what? I have no idea what you are referring to. What have you tried? Do you understand what it means to work in a finite field? I suggest you go back and review the basics, like finite fields and modular arithmetics. $\endgroup$
    – D.W.
    Jan 30, 2014 at 2:56
  • $\begingroup$ @D.W.: I am trying to run the Private Robust Set Intersection protocol mentioned in the below paper, ece.umd.edu/~danadach/MyPapers/set-int.pdf $\endgroup$
    – user11706
    Jan 30, 2014 at 4:28
  • $\begingroup$ user11706, The etiquette on this site is to edit the question to include this information into the question. When asked for clarification, don't just add a comment; edit the question to make it self-contained. People shouldn't need to read the comment thread to understand everything needed to understand the question. Looks like figlesquidge has done that for you, but you should do it yourself in the future. $\endgroup$
    – D.W.
    Jan 30, 2014 at 20:14

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.