In this paper we introduce two normalized versions of non-perfect security for private-key encryption: one version in the framework of Shannon entropy, another version in the framework of Kolmogorov complexity. We prove the lower bound on either key entropy or key size for these models and study the relations between these normalized security notions.
