Efficient Block-Wise PKE with Key Dependent Message Security
under Flexible SLP-Queries
Abstract:
Key Dependent Message (KDM) secure encryption is a new research area
extensively studied in 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
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 significantly
larger than the set of linear functions. Our function set contains all
rational functions whose denominator and numerator have polynomial
bounded degree and which can be computed by a Straight Line Program of
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.