The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science


             Walmart Lecture Series in Cryptography and Complexity

                    Seminar Room, Room 261, Ziskind Building
                          on Monday, February 14, 2011
                                 14:30 - 15:30





                                   Tal Malkin
                              Columbia University


                                 will speak on


                       Efficient Circuit-Size Independent
                        KDM Secure Public Key Encryption

Abstract:
Key Dependent Message (KDM) secure encryption is a new attractive research area
of cryptography and extensively studied in the past few years. A KDM secure
scheme w.r.t. a function set F provides security even if one encrypts a key
dependent message f(sk) for any f in F. The main result of this work is the
construction of an efficient public key encryption scheme which is KDM secure
with respect to quite a large function set F.  Proposing such a scheme is
significant because, although KDM security has practical applications, all
previous works in the standard model are either inefficient feasibility
results, or for a small set of functions such as linear functions.

Efficiency of our scheme is dramatically improved compared to the previous
feasibility results, and our function set is quite rich: Our function set
contains all rational functions whose denominator and numerator have polynomial
bounded degree and which can be computable by a Modular Arithmetic Circuit with
polynomial length.

Unlike previous schemes, our scheme is flexible in the sense that the size of
the ciphertext depends on the degree bound for the polynomial, and beyond this
all parameters of the scheme are completely independent of the size of the
program or the number of secret keys.

Joint work with Isamu Teranishi and Moti Yung.