Oblivious Polynomial Evaluation and Encoding Payload

I am trying to parse this paper. I think I do come to understand the general concepts go into this type of Private Set Intersection, based on Oblivious Polynomial Evaluation. I was able to produce a workable prototype based, with just the straight forward exponential El Gamal encryption.

The point-by-point of the protocol can be found in the section 4.2 PM Semi-Honest Protocol. What struck me that single remark in the step 2. where it says

... (One can also encrypt some additional payload data py by computing Enc(rP(y) + (y|py)). C obtains py iff y is in the intersection.)

I got quiet excited because that's what I was looking for, but the symbol '|' doesn't get explained and I couldn't find what is it supposed to be. Given that the idea is that in the case of a root P(y) evaluates to 0, and so ENC(rP(y) + y) = ENC(y). This means that anything I do with the added 'y' value will stop C (the client) to find the matching values with her own private set.

Is this some special property of the Paillier encryption I don't know about (I don't know this crypto-system very well yet), or is it something I can make work with using the exponential El Gamal encryption system?


The bar is just concatenation of strings. As long as you are comfortable treating things both as bit strings and as group elements, there is nothing special about the encryption scheme being used here.

Without these payloads, the idea of the protocol is the following. Bob sends a set $Z$ of ciphertexts. Alice computers her output as $\{ \mathsf{Dec}(z) \mid z \in Z \} \cap X$. Items shared by Alice & Bob will be output by Alice in this way. Items not shared by Alice and Bob will result in a random value for $\mathsf{Dec}(z)$, so they are negligibly likely to be output by Alice.

Now, with the payloads, suppose the parties are doing PSI on items that are $\ell$ bits long. Now Alice would compute her output as $\{ \mbox{first $\ell$ bits of } \mathsf{Dec}(z) \mid z \in Z \} \cap X$. It is still the case that any item not shared by the parties is negligibly likely to be output by Alice (negligibly likely that its first $\ell$ bits match one of Alice's items). But you can use the remaining bits to encode a payload for each item.

This assumes is that the ElGamal/Paillier group is large enough to encode strings of this extra length. But without loss of generality you can always:

  • shorten the items: agree on a common hash function and do PSI on hashes of your items.

  • shorten the payloads: make $p_y$ a short key for a symmetric-key encryption, and send along an encryption of your actual (possibly huge) payload using this key.

edit: Oh, just saw that you're using exponential El-Gamal. You will have to alter things syntactically but not conceptually. As an example, let $V$ be the group element whose bitwise representation is the item+payload string $y | p_y$. Now $V$ has some discrete log (that exists but would be hard to compute) $V = g^v$. I claim that Bob should encrypt $rP(y) + v$ in the exponent. Fortunately you don't have to know $v$ to do it, just obtain an ElGamal encryption of $g^{rP(y)}$ in the way you already know, and use its homomorphic property to multiply by $V$, making a standard ElGamal encryption of $g^{rP(y)} \cdot V$. When Alice decrypts, she either sees a random thing, or else she gets group element $V$. Instead of trying to reason about $V$'s discrete log, Alice can just look at the bit-representation of $V$ and identify it by whether $y$ is a prefix.

The reason for all this is that the payload can't be conveyed in the exponent (Alice will never be able to get it back). Instead it must appear in the result of her standard ElGamal decryption. In exponential ElGamal, you can test whether decryption equals a value you already know (in the exponent), you can't decrypt to learn a value in the exponent that is new to you.

Comments (1)

  • +0 – Thank you for your answer. So, I'm not insistent on exponential El Gamal, but for now this is the one I understand. Basically the idea is to encrypt, along with the 'match' element, at the same position, some other data. This means, perhaps less efficient, that I can store a random number k with rP(y)+k at the same position, as the rP(y)+y is. I can use g^k as a symmetric key to store the payload, and thus the client can use the exponential function. (I find it PITA to increase the bit size, given that I'm very constrained in computation power. — Aug 27, 2016 at 13:54  

External Links

External links referenced by this document: