2015-zero-knowledge proofs and application.pdf

零知识证明及其应用是密码学中一个非常重要且影响深远的概念。这个概念最早由Goldwasser, Micali和Rackoff在1985年提出，其核心思想是证明某事“只证明其有效性，而不泄露任何其他信息”。本教材将通过两个讲座来探讨零知识证明的概念，并在此基础上讨论其在密码学中的应用。课程内容将包括基于零知识证明的构造，例如安全的身份认证方案和数字签名方案，以及如何构建NP问题的零知识证明。 我们从一个简化的运行示例开始，这将帮助我们抽象出一些基本属性，并引入Σ-协议的概念。Σ-协议在构建安全的身份识别方案中具有重要作用。随后，我们将进入密码学应用领域，特别是如何使用零知识证明来构建高效且可证明安全的身份识别和签名方案。此外，我们还将正式定义零知识，并概述构建所有NP问题零知识证明的主要成果。 在讲述零知识证明时，我们会涉及一些基础知识，包括Schnorr协议及其基础属性。Schnorr协议是解决“离散对数问题”的一种方法，该问题在密码学中具有重要意义。通过该协议，一方可以向另一方证明他/她知道一个秘密，而无需透露秘密本身是什么。该协议的应用可以推广到其他需要验证知识的情况中。 Σ-协议是零知识证明的一个子类，其特点是交互式证明系统，它们可以用来构造安全的身份识别方案。Σ-协议具有几个关键属性，包括OR证明和见证隐藏（Witness Hiding）能力，这些属性对于在不泄露更多信息的前提下验证知识的真实性至关重要。 在讨论安全身份识别的过程中，我们会探讨被动和主动安全性的区别。被动安全性仅要求在没有积极攻击的条件下系统保持安全，而主动安全性意味着在存在攻击者试图破坏安全性的条件下，系统仍然能保持安全。课程还将讨论如何从Σ-协议构造身份识别方案，并探讨在超越主动安全性之后的安全模型。 Fiat-Shamir启发式方法是将交互式证明系统转化为非交互式证明系统的一种技术，它极大地促进了零知识证明的实际应用。此启发式方法基于某些安全假设，并允许我们将一个交互式协议（比如基于零知识证明的协议）转化为一个非交互式方案，从而使协议在实际应用中更为方便和高效。 Fiat-Shamir变换是实现这一转化的关键技术，它依赖于一种被称为“随机预言机”（Random Oracle）的模型。这个模型中，密码学中的某些函数被假设为完全随机的，并且在每次被查询时都返回一个全新的随机结果。然而，围绕随机预言机模型的有效性以及实际安全性也存在一些争议。 课程还将探讨零知识在NP问题中的应用，以及如何构建这些零知识证明。NP问题是计算机科学中的一个重要概念，指的是可以在多项式时间内验证其解的问题。在密码学中，对于这类问题提供零知识证明的能力是保证系统安全的关键。 课程会提供进一步阅读的资源，以便有兴趣深入研究的学生能够获得更多的知识和信息。 为了奖励他们在零知识证明和其他密码学问题方面的杰出贡献，Shafi Goldwasser和Silvio Micali在2012年被授予了具有高度声望的ACM图灵奖。更多的相关成果和信息可以通过访问提供的网址获得。