原文标题：《密码学技术何以为信？深究背后的计算困难性理论 | 隐私保护周三见【第 3 论】》

　　撰文：李昊轩，微众银行区块链核心开发者

　　隐私保护为何选用密码学算法？密码学算法背后有哪些神奇的数学理论？3 何时比 9 大？计算可逆性错觉究竟是如何在数学领域被打破？

　　这里，我们将从密码学信任的理论基础出发，分享在隐私保护技术方案中应用密码学技术的一些思考：如何理解密码学算法的能力边界，如何客观地比较不同密码学算法对于隐私保护方案有效性的影响。

　　这一切，要从密码学神奇的「不对称性」说起。

　　神奇的「不对称性」

　　早在公元前，古埃及、古罗马、古希腊等古文明均已开始使用密码技术来保护信息的机密性，历史上最早的不对称性表现为选用特殊的信息编码方式，如果第三方不知道具体的编码方式，则难以解码对应的信息。

　　大约经过 4000 多年的发展，也就是近代 20 世纪初，现代密码学正式成型，引入了关于不对称性更为严谨的数学定义。比较有代表性的早期论文包括 1929 年 Lester S. Hill 在美国数学月刊上发表的《Cryptography in an Algebraic Alphabet》。

　　20 世纪末，随着因特网的普及，大量敏感数据在网络上进行传输，产生了大量的数据内容保护的需求，密码学技术也因此得到飞速发展。

　　在现代密码学中，关于不对称性，大家最熟悉的概念莫过于「公钥」和「私钥」。

　　以加密通信为例，主人公小华要向他的朋友美丽通过加密的方式发送一份电子邮件，可以先找到美丽的公钥，使用公钥对邮件内容进行加密，并将加密后的得到密文发送给美丽。美丽收到邮件内容的密文之后，通过自己的私钥进行解密，最终得到邮件内容的明文。

　　以上过程中，密码学算法神奇的不对称性体现在以下问题中：

　　为什么只有美丽可以解密邮件内容？

　　为什么其他人不能通过美丽的公钥反推出她的私钥？

　　这些问题的答案，都要归结于密码学中的计算困难性理论。

　　计算困难性理论

　　在隐私保护场景中，计算困难性理论具体表现为，对同一隐私数据主体，通过不同计算路径，获得相同信息的计算难度具有不对称性。不对称性中，相对容易的计算方式被用来构造授权的数据访问，而困难的计算方式被用来避免非授权的数据泄露。

　　构造这样的不对称性的方式有很多，最经典的方式之一，就是千禧年七大难题之一——P 和 NP 问题。

　　P 问题是确定性图灵机，即通用计算机计算模型，在多项式时间 (O(n^k)) 内可以计算获得答案的一类问题。NP 问题是确定性图灵机在多项式时间内可以验证答案的正确性，但不一定能计算出答案的一类问题。

　　关于同一份答案，验证过程比计算过程要容易很多，由此我们可以构造出密码学算法所需要的计算难度不对称性。

　　NP 问题是否能够通过有效的多项式时间算法转化成 P 问题，由此破解计算难度不对称性？目前学术界尚无定论。

　　理论研究进一步表明，对于 NP 问题集合中的核心问题，即 NP 完全问题，如果能够找一个有效的多项式时间算法来解决任何一个 NP 完全问题，那其他所有 NP 问题都可以基于这个算法来构造出有效的多项式时间算法。由此，之前提到的计算难度不对称性将不复存在。

　　幸运的是，经过将近 70 年的科学探索，这样的算法并没有被发现。在有限时间内，现代计算机难以求解这些问题的答案，所以现代密码学可以比较安全地基于这些 NP 完全问题来构造有效的密码学算法。

　　神奇的「计算困难问题」

　　形象地讲，计算困难性理论的核心就是构造一个迷宫，如果不知道捷径，是很难到达出口的。

　　我们日常所用的各类密码学算法，其有效性都与这一理论息息相关，这里重点以非对称密码学算法为例，介绍其中经典的迷宫构造蓝图，即三大计算困难问题：

　　大数分解困难问题

郑重声明：本文版权归天网查所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。