Computer Science Colloquia
Tuesday, April 26, 2011
Mona Sergi-Ph.D. Qualifying Exam Presentation
Advisor: abhi shelat
Attending Faculty: Jack Davidson; Gabriel Robins; David Evans
Olsson Hall Room 228E, 09:00:00
Threshold Fully Homomorphic Encryption and Secure Computation
Cramer, Damgard, and Nielsen(EUROCRYPT'01) show how to construct an efficient secure multi-party computation scheme using a threshold homomorphic encryption scheme that has four properties i) a honest-verifier zero-knowledge proof of knowledge of encrypted values, ii) proving multiplications correct iii) threshold decryption and iv) trusted shared key setup. Our goal is to modify their scheme using a fully-homomorphic encryption scheme, to attain improvements in round and communication complexity and to weaken the setup assumptions. To do this we show how to modify the constructions of van Dijk et al.( van Dijk, Gentry, Halevi, and Vaikuntanathan, EUROCRYPT'10) to be threshold encryption schemes. This takes care of the third requirement. The fact that the scheme is fully homomorphic removes the need to have proofs of knowledge relating to multiplication, so the second requirement is handled. The final requirement is that we have an honest-verifier zero-knowledge proof of knowledge of encrypted values.
We provide a weaker solution to the final requirement. We provide a 2-round blackbox protocol that allows us to prove knowledge of encrypted bits. Our protocol is not zero-knowledge, but it probably does not release any information about the bit being discussed, and this is sufficient to prove the correctness of a simulation in a method similar to Cramer et al.
We also directly construct secure protocols for sharing the secret key for our threshold scheme (thereby removing the setup assumptions) and for jointly decrypting a bit. All of these constructions are constant round and we thoroughly analyze their complexity. Altogether, we construct the first secure multi-party computation protocol that allows evaluation of a function f using communication that is independent of the circuit description of f.