Efficient Circuit-Size Independent KDM Secure Public Key Encryption

Tal Malkin, Columbia University


Key Dependent Message (KDM) secure encryption has been 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 and flexible 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 and theoretical 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 of polynomial size. 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

Time and Place

May 9 2011 (Monday) at 1630 hrs
Gates 463A