随着信息技术的进一步应用,人们所面临的信息安全威胁日益增多。密码学作为解决信息安全问题的核心技术,也备受重视。如何在不同的应用环境中设计相对应的高安全密码学方案,一直都是学术界比较关心的话题。可证明安全性理论是一种设计和分析密码方案安全性的有效方法,它可以将求解一些公认的数学困难问题归约到攻破某一个具体的密码方案,以此完成对该密码方案的安全性证明过程。一般意义下的安全归约过程要求密码方案中的明文和私钥是相互独立的。但在较为复杂的应用场景下,例如全同态加密的Bootstrapping过程,确实会出现明文依赖于私钥的情况。如何在这种特殊情况下对密码方案的安全性进行证明是一个非常有意义的研究问题。消息依赖于密钥(Key-Dependent Message,简记为KDM)安全定义的提出就是为了更好地分析和解决在明文依赖于密钥情况下的安全性问题。本文通过对KDM安全加密方案的构造及其相关问题进行分析和研究,取得如下主要结果：1、在理想加密模型下,利用通用哈希函数,构造了一个新型的KDM安全的对称加密方案。本方案所允许的挑战函数集合是由任意多项式时间内可计算函数组成的。与已有的KDM安全的对称加密方案相比,该方案的优势是：构造非常简洁、挑战函数集合足够大、且能够抵抗主动攻击。该方案在理论上的意义是：提出了构造KDM安全对称加密方案的新思路。2、为保证损耗陷门函数在私钥相关信息(关于私钥的任意计算不可求逆的函数)提前泄露的情况下,仍然是可证明安全的,首先利用d线性假设,构造了一个新的损耗陷门函数,并利用扩展版的Goldreich-Levin定理,证明其是辅助输入安全的；然后对Peikert所构造的基于带差错的学习问题(Learning With Errors,简记为LWE)假设的损耗陷门函数进行适当改进,并证明其是辅助输入安全的。最后,从效率和安全性角度出发,对两个损耗陷门函数进行分析,并和已有的相关构造进行对比。3、在标准模型下,利用混合加密的概念提出了一个构造KDM安全的非对称加密方案的新方法。该新型构造方法首次对已有著名的基于随机预言机模型所构造KDM安全加密方案进行部分实例化。与已有的标准模型下相关构造方法相比,本方法最大的特点是直接利用损耗陷门函数作为方案构造的一个重要部分。同时,通过重新定义和利用损耗陷门函数的密钥泄露安全的性质,完成对所构造方案的‘KDM安全性证明。4、首次基于LWE问题假设构造了一个有效的通用哈希证明系统。然后利用该证明系统可以进一步基于LWE问题假设和非齐次小整数解(Inhomogeneous Small Integer Solution,简记为ISIS)问题假设,构造在适应性选择密文攻击下(Adaptive Chosen Cihpertext Attack,简记为CCA2)不可区分(Indistinguishability, IND)安全的公钥加密方案。通过分析该方案所具有的性质得知,该方案可以被证明是针对于特殊的挑战函数集合是KDM-CCA2安全的。