Abstract: Key-Dependent Message (KDM) security was introduced to address the case where message is a function of secret key of encryption scheme. By using universal hash function, this paper presents a stateless symmetric encryption scheme that is information-theoretically KDM secure based on an extended version of left-over hash lemma in the standard model. The scheme is secure in face of a bounded of nearly exponent number of encryptions for which the messages depend in an arbitrary way on the secret key. Finally, through choosing parameters properly and comparing with existing schemes, the security and efficiency of the constructed scheme are proved to be improved.