零知识证明是一种高级密码协议,它是指声称者要向验证者证明某一断言的真实性,却并不向验证者泄露任何与该断言有关的其他信息。零知识证明是构建安全密码协议的强大工具,它在密码学中得到了广泛的应用,尤其是在身份认证、数字签名方面。位承诺是实现零知识证明的重要工具。自Blum于1982年首先提出了位承诺[1]的概念后,它已经成为了密码学研究的一个活跃领域。密码学家指出如果有了好的加密算法,任何NP命题都有一个零知识证明[2]。这里的加密算法本质上就是位承诺算法。位承诺是构建零知识证明的重要子协议,不仅如此,位承诺的类型直接影响着其所构建的上层零知识证明的零知识类型。不可否认数字签名是个与零知识证明紧密联系的概念。在不可否认数字签名中,签名的接受者无法自行验证签名,双方通过执行一个签名验证协议,签名者可向签名的接收者零知识地证明签名是否有效。不可否认数字签名可用于防止数字签名的复制及传播,保护签名者的隐私。本文以几个身份识别的零知识证明为例,详尽地证明了它们的正确性、合理性,分析了它们所达到的零知识类型。总结了“验证者挑战”和“验证者提问”的两种零知识证明结构,指出在第二种结构下,通过使用一个全无泄露的位承诺,可构建出完善的零知识证明。从构建零知识证明的角度出发,将位承诺协议区分为全无泄露的、统计上无泄露的、计算上无泄露的不同类型。指出位承诺协议的类型决定着上层零知识证明的零知识类型,而全无泄露的位承诺是实现完善零知识证明的前提保证。基于本文提出的“离散对数对碰撞”问题理论,提出了一个新的全无泄露的位承诺协议,它的使用完全不会增加上层协议信息泄露的可能,是构建零知识证明的完美子协议。通过图的三着色命题的零知识证明实例,证明了以此新的全无泄露的位承诺协议可构建出NP问题的完善零知识证明。对David Chaum的零知识不可否认数字签名方案进行了改进,运用分割选择以及新提出的全无泄露的位承诺技术,构造了新的完善零知识的确认协议和否认协议。新的否认协议与Chaum的方案相比,在同样的安全级别下所需的模乘运算呈指数级别地降低。分别基于Schnorr签名和广义ELGamal型签名,提出了新的随机化的不可否认数字签名生成算法,消除了之前签名方案所具有的存在性伪造问题,同时可以复用之前的签名验证及否认协议。