其它技术

密码学领域涉及到的技术还有许多,这里总结一些还在发展和探讨中的话题。

零知识证明

零知识证明(Zero Knowledge Proof),是这样的一个过程,证明者在不向验证者提供任何额外信息的前提下,使验证者相信某个论断(Statement)是正确的。

证明过程包括交互式(Interactive)和非交互式(Non-interactive)两种。

零知识证明的研究始于 Shafi Goldwasser,Silvio Micali 和 Charles Rackoff 在 1985 年提交的开创性论文《The Knowledge Complexity of Interactive Proof-Systems》,三位作者也因此在 1993 年获得首届哥德尔奖。

论文中提出了零知识证明要满足三个条件:

  • 完整性(Completeness):真实的证明可以让验证者成功验证;

  • 可靠性(Soundness):虚假的证明无法保证通过验证。但理论上可以存在小概率例外;

  • 零知识(Zero-Knowledge):如果得到证明,无法(或很难)从证明过程中获知除了所证明信息之外的任何信息,分为完美零知识、概率零知识。

交互式零知识证明相对容易构造,需要通过证明人和验证人之间一系列交互完成。一般为验证人提出一系列问题,证明人如果能都回答正确,则有较大概率确实知道论断。

例如,证明人 Alice 向验证人 Bob 证明两个看起来一样的图片有差异,并且自己能识别这个差异。Bob 将两个图片在 Alice 无法看到的情况下更换或保持顺序,再次让 Alice 识别是否顺序调整。如果 Alice 每次都能正确识别顺序是否变化,则 Bob 会以较大概率认可 Alice 的证明。此过程中,Bob 除了知道 Alice 确实能识别差异这个论断外,自己无法获知或推理出任何额外信息(包括该差异本身),也无法用 Alice 的证明(例如证明过程的录像)去向别人证明。注意这个过程中 Alice 如果提前猜测出 Bob 的更换顺序,则存在作假的可能性。

非交互式零知识证明(NIZK)则复杂的多。实际上,通用的非交互式完美或概率零知识证明(Proof)系统并不存在,但可以设计出计算安全的非交互式零知识论证(Argument)系统,具有广泛的应用价值。

Manuel Blum、Alfredo De Santis、Silvio Micali 和 Giuseppe Persiano 在 1991 年发表的论文《Noninteractive Zero-Knowledge》中提出了首个面向“二次非连续问题”的非交互的完美零知识证明(NIPZK)系统。

2012 年,Nir Bitansky、Ran Caneetti 等在论文《From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again》中提出了实用的非交互零知识论证方案 zk-SNARKs,后来在 Z-cash 等项目中得到广泛应用。目前,进行非交互式零知识论证的主要思路为利用所证明论断创造一个难题(一般为 NP 完全问题如 SAT,某些情况下需要提前或第三方提供随机数作为参数)。如果证明人确实知道论断,即可在一定时间内解决该难题,否则很难解答难题。验证人可以通过验证答案来验证证明人是否知晓论断。

零知识证明如果要能普及,还需要接受实践检验,另外需要考虑减少甚至无需预备阶段计算、提高可扩展性,同时考虑抵御量子计算攻击。

可验证随机函数

可验证随机函数(Verifiable Random Function,VRF)最早由 Silvio Micali(麻省理工学院)、Michael Rabiny(哈佛大学)、Salil Vadha(麻省理工学院)于 1999 年在论文《Verifiable Random Functions》中提出。

它讨论的是一类特殊的伪随机函数,其结果可以在某些场景下进行验证。一般可以通过签名和哈希操作来构建。

例如,Alice 拥有公钥 Pk 和对应私钥 Sk。Alice 宣称某可验证随机函数 F 和一个输入 x,并计算 y = F(Sk, x)。Bob 可以使用 Alice 公钥 Pk,对同样的 x 和 F 进行验证,证明其结果确实为 y。注意该过程中,因为 F 的随机性,任何人都无法预测 y 的值。

可见,VRF 提供了一种让大家都认可并且可以验证的随机序列,可以用于分布式系统中进行投票的场景。

安全多方计算

安全多方计算(Secure Multi-Party Computation,SMPC 或 SMC)由 Andrew Chi-Chih Yao(姚期智)于 1986 年在论文《How to generate and exchange secrets》中提出。其假设的场景为多个参与方都拥有部分数据,在不泄露自己数据的前提下,实现利用多方的数据进行计算。这一问题在多方彼此互不信任而又需要进行某些合作时(如保护隐私的前提下进行数据协同),十分有用,有时候也被称为隐私保护计算(Privacy-preserving Computation)。

根据参与方的个数,可以分为双方计算或多方计算;根据实现方法,可以分为基于噪音(如 differential privacy,差分隐私)、基于秘密共享(Secret Sharing)、基于混淆电路(Garbled Circuit)和基于同态加密(Homomorphic Encryption)。

一般来说,基于噪音的方案容易实现,但使用场景局限,基于密码学技术的方案更通用,但往往需要较大计算成本。

不经意传输

不经意传输(Oblivious Transfer,OT)协议由 S. Even,O. Goldreich,A. Lempel 等人 1983 年在论文《A Randomized Protocol for Signing Contracts》中提出。后来应用在安全多方计算等场景下。

该协议所解决的问题是发送方将信息发送给接收方,但要保护双方的隐私:发送方无法获知接收方最终接收了哪些信息;接收方除了能获知自己所需的信息外,无法获得额外的信息。

例如,银行向征信公司查询某个客户的征信情况以决定是否进行贷款,银行不希望征信公司知道该客户来到该银行申请贷款(属于客户隐私),同时,征信公司不希望银行拿到其它客户的征信数据。

一种简单的实现是发送方发送 N 个公钥给接收方,接收方随机选择一个公钥加密一个对称密钥并将结果返回发送方。发送方分别用 N 个私钥进行解密,其中 1 个结果为对称密钥,N-1 个为随机串,但发送方无法区别。发送方用 N 个解密结果分别加密 1 条消息(共计 N 条)并返回给接收方。接收方只能解密其中 1 条消息。如果双方提前约定好 N 对结果进行盲化的随机串,接收方还可以挑选只接收某个特定信息。

另外一种简单实现是接收方提供 N 个随机串作为公钥,并证明自己只知道其中 K 个串对应的私钥。发送方采用这些随机串加密 N 个信息,然后发给接收方。这样,接收方只能解开其中的 K 条信息。

差分隐私

差分隐私(Differential Privacy)是一种相对实用的隐私保护机制。

最初问题是研究如何分享一个数据集而保护数据集中个体的隐私,在 2006 年由 Cynthia Dwork、Frank McSherry、 Kobbi Nissim 和 Adam Smith 在论文《Calibrating Noise to Sensitivity in Private Data Analysis》中提出。由于在隐私保护问题上的应用前景,近些年成为研究热点。

主要思想是在数据集中巧妙的添加一些噪音扰动,使得对修改后数据集进行计算不太影响统计结果,但无法将其中任意个体追溯回原始个体信息。例如,将数据集中删掉任意一条记录,查询结果不受影响。

目前可行的方案主要包括添加拉普拉斯噪音(适合于数值型)和指数噪音(适合于非数值型)等。

量子密码学

量子密码学(Quantum Cryptography)随着量子计算和量子通信的研究而被受到越来越多的关注,被认为会对已有的密码学安全机制产生较大的影响。

量子计算的概念最早是物理学家费曼于 1981 年提出,基本原理是利用量子比特可以同时处于多个相干叠加态,理论上可以同时用少量量子比特来表达大量的信息,并同时进行处理,大大提高计算速度。量子计算目前在某些特定领域已经展现出超越经典计算的潜力。如基于量子计算的 Shor 算法(1994 年提出),理论上可以实现远超经典计算速度的大数因子分解。2016 年 3 月,人类第一次以可扩展的方式,用 Shor 算法完成对数字 15 的质因数分解。

这意味着目前广泛应用的非对称加密算法,包括基于大整数分解的 RSA、基于椭圆曲线随机数的 ECC 等将来都将很容易被破解。当然,现代密码学体系并不会因为量子计算的出现而崩溃。一方面,量子计算设备离实际可用的通用计算机还有较大距离,密码学家可以探索更安全的密码算法。另一方面,很多安全机制尚未发现能加速破解的量子算法,包括数字签名(基于 Hash)、格(Lattice)密码、基于编码的密码等。

量子通信则可以提供对密钥进行安全协商的机制,有望实现无条件安全的“一次性密码”。量子通信基于量子纠缠效应,两个发生纠缠的量子可以进行远距离的实时状态同步。一旦信道被窃听,则通信双方会获知该情况,丢弃此次传输的泄露信息。该性质十分适合进行大量的密钥分发,如 1984 年提出的 BB84 协议,结合量子通道和公开信道,可以实现安全的密钥分发。

注:一次性密码:最早由香农提出,实现理论上绝对安全的对称加密。其特点为密钥真随机且只使用一次;密钥长度跟明文一致,加密过程为两者进行二进制异或操作。

社交工程学

密码学与安全问题,一直是学术界和工业界都十分关心的重要话题,相关的技术也一直在不断发展和完善。然而,即便存在理论上完美的技术,也不存在完美的系统。无数例子证实,看起来设计十分完善的系统最后被攻破,并非是因为设计上出现了深层次的漏洞。而问题往往出在事后看来十分浅显的一些方面。

例如,系统管理员将登陆密码贴到电脑前;财务人员在电话里泄露用户的个人敏感信息;公司职员随意运行来自不明邮件的附件;不明人员借推销或调查问卷的名义进入办公场所窃取信息……

著名计算机黑客和安全顾问 Kevin David Mitnick 曾在 15 岁时成功入侵北美空中防务指挥系统,在其著作《The Art of Deception》中大量揭示了通过社交工程学的手段轻易获取各种安全信息的案例。