Provided by: Columbia University
Date Added: Feb 2011
Key Dependent Message (KDM) secure encryption is a new area which has attracted much research in recent years. Roughly speaking, 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 2 F. The authors present a construction of an efficient public key encryption scheme which is KDM secure with respect to a large function set F. Their function set is a function computable by a polynomial-size Modular Arithmetic Circuit (MAC); they represent the set as straight line programs computing multi-variable polynomials (an extended scheme includes all rational functions whose denominator and numerator are functions as above).