Let Enc() be an public-key encryption scheme that is additively homo- morphic. (a) Let Zn be...

 

Transcribed Image Text:

Let Enc() be an public-key encryption scheme that is additively homo- morphic. (a) Let Zn be the space of messages of Enc(). Let p(x) = po + Px + +psas be a polynomial with coefficients in Zn. For any r, b Zn, show that it is possible to compute Enc(r p(b) + b) ... from r, b, Enc(po),..., and Enc(ps). (b) Discuss the relevance of this property in the Freedman-Nissim-Pinkas protocol for private-set intersection. (c) Discuss whether the homomorphic encryption scheme used in the protocol is CCA-secure. (d) Discuss why we can have false-positives. Let Enc() be an public-key encryption scheme that is additively homo- morphic. (a) Let Zn be the space of messages of Enc(). Let p(x) = po + Px + +psas be a polynomial with coefficients in Zn. For any r, b Zn, show that it is possible to compute Enc(r p(b) + b) ... from r, b, Enc(po),..., and Enc(ps). (b) Discuss the relevance of this property in the Freedman-Nissim-Pinkas protocol for private-set intersection. (c) Discuss whether the homomorphic encryption scheme used in the protocol is CCA-secure. (d) Discuss why we can have false-positives.