ELC C01 Seminar Announcement
Date: Oct. 17th (Thu)
Time: 14:00 - (followed by some talk by Osamu Watanabe)
Place: CELC Seminar room
http://www.al.ics.saitama-u.ac.jp/elc/celc/

Title: On the complexity and security of homomorphic encryption
Speaker: Andrej Bogdanov (Chinese Univ. of Hong Kong) 

An encryption scheme is called homomorphic if given encryptions of 
several plaintexts, one can compute an encryption of some function of 
them (for example their sum) using public information only. This 
feature is useful for applications like electronic voting and secure 
outsourcing of computation.

We study homomorphic encryption from a complexity-theoretic 
perspective. We show that:

1. For any sufficiently "sensitive" function f, if an encryption 
scheme supports homomorphic evaluation of f, then this scheme cannot 
be proved NP-hard to break (under widely believed complexity 
assumptions).

2. For almost any function f, the ability to homomorphic evaluate f 
implies the ability to rerandomize ciphertexts (turn a ciphertext 
into another functionally equivalent but statistically independent 
one).

3. Certain encryption schemes (both private and public key) can be
implemented by circuits of small depth, but homomorphic evaluation of 
any nontrivial functionality requires large circuit depth.

Our results can be viewed as evidence that homomorphic encryption 
schemes are inherently more complex and possibly less secure than 
ordinary ones.

The talk is based on joint works with Chin Ho Lee.

END OF ANNOUNCEMENT