I'm looking at https://link.springer.com/content/pdf/10.1007%2F11496137_31.pdf and it seems like in the protocol they propose if Alice can guess Bob's number, she can pretty easily verify that guess. (Section 3: Our Protocols)

Bob isn't performing any private operation besides generating the random encryptions to fill out the items he's sending back to her. So Alice could do the exact same thing Bob is doing (multiplying together the encryptions corresponding to the digits she thinks are in his number for each zero-bit), and see if they match up to a subset of the terms he sent.

What am I missing here?


The key step is in section 3 where the protocol is described. In step 2, Bob "scalarises" the $c_t$ values which converts them to a set of random $c_t'$ values where $\mathrm{Dec}(c_t)=\mathrm{Dec}(c'_t)$. Unfortunately, the authors have given the scalarised $c_t$ the same notation as the unscalarised, which is confusing.

Alice can recreate the unscalarised $c_t$ values, but cannot reproduce the randomly scalarised $c'_t$ values and so cannot identify a subset of repeated terms.

  • $\begingroup$ I missed that entirely Thanks $\endgroup$
    – dspyz
    Sep 14 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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