有可能会改变所有区块链密码学基础的论文

密码学是许多区块链协议的核心。从传统的工作证明(PoW)到L2现代方法(如zk -rollup)，许多高级加密方法提供了区块链运行和协议的基础。因此，任何区块链体系结构的安全稳定性都是一个普遍存在的问题。我们天真地认为，区块链加密的实现在经受了复杂攻击后本质上是安全的，但这并不是经验证明。是否有更好的方法来验证安全算法的稳定性。答案似乎出现在一篇刚刚赢得美国国家安全局(NSA)“最佳网络安全研究论文竞赛”的新论文中，这在密码学研究界引起了很大的争议。

这篇题为“论单向函数和Kolmogorov复杂性”的论文为密码学五百年来的一个问题提供了答案。当前的问题与一个称为“单向函数”的数学构造的存在有关，该构造可以证明L2区块链中的零知识证明等方法是否具有密码保护。

论文地址：https://arxiv.org/abs/2009.11514

现代密码学的本质是在数据上创建密码，并希望它们保持安全。然而，我们如何确保它们是安全的呢？这个问题的理论答案出现在20世纪70年代，当时密码学家提出了单向函数的概念，单向函数是一种数学函数，很容易计算，但很难反转。说明下单向函数是如何工作的，假设有人让你将两个大素数(如485144和999983)相乘。得到485,135,752,552的答案可能需要一些工作，但我们有一个方法可以做到这一点。现在我们来做一个反题，从这个数开始试着确定它的质因数。这是一个极其困难的任务。这就是单向函数的本质。

L1和L2区块链中使用的加密技术的基础是以单向函数的存在为前提的。如果对于给定的问题存在单向函数，那么它的密码保护是安全的，如果没有，它很可能容易受到不同的攻击。然而，到目前为止，几乎不可能证明单向函数的存在。

Kolmogorov的复杂度

在康奈尔大学的研究论文中提出的答案本质上是，单向函数的存在与计算机科学中另一个被称为Kolmogorov复杂度(KC)的基本问题有关。KC理论与数字串的复杂性有关。如果你面对两个较大的数字，6666666666666666666666666666和123948109102912，你不能很好地证明哪个比另一个“更随机”，但直觉上你会认为第二个数字生成起来更复杂。苏联数学家安德雷·柯尔莫戈罗夫用这个想法开创了计算复杂性的新理论。本质上，KC 理论将数字字符串的复杂度定义为产生该字符串作为输出的最短程序的长度。回到我们的例子，生成第二个数字所需的程序从根本上来说比仅仅打印一个6序列要复杂得多。

KC理论比较复杂，但希望你们已经掌握了核心思想。几十年来，KC理论已经成为许多计算机科学领域的基础，但在密码学中并没有那么重要。直到康奈尔大学的研究小组证明单向函数的存在与给定问题的KC有关。简单地说，如果一个问题是KC复杂的，那么存在一个单向函数，如果不存在，很可能它就是不存在。

这个简单的陈述可能会成为现代密码学中最具革命性的发现之一。

这对区块链世界意味着什么?

康奈尔大学的论文提供了一种经验方法来评估L1和L2区块链中使用的加密技术的稳定性。考虑到基于加密技术（例如安全多方计算或零知识证明）的在 L2 运行时的出现，这一点变得尤其重要。判断一个算法是否KC复形比判断是否存在单向函数简单得多。当然，这个问题远远超出了区块链生态系统的范围，但如果我们谈论的是构建一个新的金融系统的轨道，密码稳定性是一种基本能力。

Source：https://medium.com/intotheblock/the-paper-that-can-change-the-foundations-of-all-blockchain-cryptography-6df9f077e9d3