Score:0

Can Alice verify a guess of Bob's number in this Homomorphic Encryption solution to the millionaire problem

jp flag

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?

Score:2
ru flag

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.

jp flag
I missed that entirely Thanks
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.