精选
尖端通信由数学曲线开启
一个简单的几何想法推动了信息论、密码学甚至区块链技术的发展。
Jordan Cepelewicz 著
左 芬 译
【译注：原文2022年9月19日刊载于QuantaMagazine，链接见文末。】
Reed-Solomon码驱动着大量信息技术。
给定空间中的一组点，你是否能找到某种类型的曲线穿过它们全部？这一问题——所谓插值问题的一个版本——从远古时期开始就吸引着数学家们。今年年初，Eric Larson与Isabel Vogt彻底解决了这一问题。
不过尽管这一工作在纯数学家中引起了轰动，插值还应该在远离几何王国的地方产生实际影响。插值处于核心地位的应用包括电子数据的存储和传输，加密方案的构建，不一而足。它正是为什么你用划破了的CD还能听音乐，把二维码弄脏了也能扫上的原因。它也是旅行者项目之类的空间任务能把清晰的数字图片传回地球的原因。它还使得计算机集群始终能执行复杂的计算，哪怕其中有一台计算机出了故障。
这些应用全都依赖于插值的一种极其优美而又在概念上简单的使用方式：所谓Reed-Solomon码，以及在其基础上构建的其它编码。
逐点法
假定你想要发送由两个数字2和7组成的一条消息。你在传输时一些数据可能会丢失或者损坏——例如，2可能翻转为-2。因此你不能光是发送数据本身，你还得加上额外信息来帮助接收者识别并纠正可能出现的错误。这就是所谓纠错码。
这种码最简单的例子就是重复多次传输相同的消息。为了让接收者识别是否有错误发生，将相同的消息发送两次：2,7,2,7。如果相应位置上的数字不匹配（比如说，接收到的是2,7,-2,7），接收者会知道其中一个出错了，但不知道是哪一个。要想让他们弄清错在哪并予以纠正，把同样的消息发送三次：2,7,2,7,2,7。接收者只需进行多数派投票就可以找出你的预定消息。
但这也意味着纠错码非常不高效。这儿有一个巧妙得多的方法：将消息编码成一条曲线，并发送刚好足够的信息让接收者能重建出曲线。
在我们传输2和7的简单情况下，曲线会是直线y=2x+7。将这一曲线在两个既定的x点上求值，并传输得到的y值。于是接收者有了两个点，而由于插值问题告诉我们两个点确定一条唯一的直线，他只需找到穿过接收到的点的直线。直线的系数就给出了预定消息。
为了避免错误，你再次添加上额外信息。这时，你发送另一个预定的x坐标处的y值。如果三个点没有落到同一条线上，就存在错误。而为了弄清错在哪里，你只需再发送一个额外的值——意味着你总共发送了四个数字，相比于前一种方法中的六个。
这一优势会随着消息的规模变大而增长。假定你想要发送一条更长的消息——1000个数字。前面低效的那种码需要发送2000个数字来识别错误，3000个数字来纠正它。但如果你使用通过给定点的插值多项式编码，你只需要1001个数字来找出错误，1002个来纠正它。（你可以加入更多的点来识别和纠正更多的潜在错误。）随着消息长度的增加，两种编码在效率上的差别变得更加鲜明。
这种更加高效的编码叫做Reed-Solomon码。在它1960年被发明之后，数学家们实现了进一步的突破，开发出能以更高效率纠正多个错误的算法。“它非常简练，清楚，具体，”多伦多大学的一名数学家兼计算机科学家Swastik Kopparty称，“可以在半个小时内教会一个二年级本科生。”
Reed-Solomon码在信息的电子存储和传输中极其有用。而同一概念在加密和分布式计算中也一样不可或缺。
拿秘密共享来说：假定你想要把一个秘密在多人之间分发，使得没有哪个人可以获取整个秘密，但他们合在一起则可以。（比如，一个加密密钥，或者导弹发射密码。）你可以把数字编码成一个多项式，在一组给定的点上计算多项式的值，然后把每个结果分发给一个不同的人。
最近，Reed-Solomon码在云计算和区块链技术等领域中得到使用。例如你需要执行一个计算，它过于复杂因而无法在你的手提电脑上完成，因此你找来一个大型的计算机集群来执行——但现在你需要验证你收到的计算是对的。Reed-Solomon码使你能要求额外信息，而这些信息如果集群没有正确执行计算的话很可能是无法给出的。“这里的运作方式非常神奇，”法国雷恩数学研究所的一名研究员Jade Nardi称，“这一过程简直妙不可言，而它[对这些编码]的依赖方式让我脑洞大开。”
在一个概念证明测试中，NASA的科学家们将名画蒙娜丽莎编码进一束激光中，并从地球表面发送到月球上的宇宙飞船。Reed-Solomon码被用于纠正由地球大气所引发的传输错误。
不过Reed-Solomon也有一个重大的限制。在它们的编码过程中，你只能在一组给定（并且通常相对较小）的点集上对你的多项式求值。也就是说，你被限制到使用一组特定的数来编码你的消息。这一集合——也就是所谓字母表——的大小反过头来会限制你能发送的消息的长度——而当你试着将字母表增大时，你解码这些消息所需的计算资源也会增多。
因此数学家们还在寻求更加合适的编码。
未来的编码
更一般、更强力的编码能让你存储或发送更长的消息，而无需扩大你的字母表的规模。对此，数学家设计了这样一种编码，它需要通过一种更加复杂的曲线上的给定点来插值一个函数，而该函数处在与该曲线相关联的一个特定空间中。这些所谓的代数几何码“凭空出现，并且比我们已知能[用小的字母表]构造的其它码都要好，”Kopparty说道，“它战胜了一切。这属实出人意料。”
只是有一个问题。在实践中，实现Reed-Solomon码比代数几何码要简单太多了。“现状就是这样，如何真正转化成实用技术还处在研究之中，”密码学家Simon Abelard说道，“它涉及非常抽象的数学，因此在计算机上处理这些编码有些困难。”
目前来说，这一点无需担忧：在现实世界的应用中，Reed-Solomon码和相关的编码形式已经足够。但情况可能不会一直如此。例如，如果强大的量子计算机在未来可供使用，他们可以破解当今的加密协议。因此，研究者们已经在寻求可以抵御量子攻击的方案。这类方案的一个热门竞争者需要用到比Reed-Solomon码更强的编码。某种版本的代数几何码可能恰好可行。其他研究者则寄厚望于代数几何码在云计算中可能会起到的作用。
但即便没有这些潜在的应用，“在数学的历史长河中，有时你会发现当前并没有实用的新东西，”荷兰埃因霍温理工大学专注于代数几何码的研究者Elena Berardini说道，“但过了50年后，你发现它对于某种完全没有预料到的事情是有用的”——正如插值这一古老问题本身。
原文链接：
https://www.quantamagazine.org/how-mathematical-curves-power-cryptography-20220919/
转载本文请联系原作者获取授权，同时请注明本文来自左芬科学网博客。
链接地址：https://wap.sciencenet.cn/blog-863936-1468339.html?mobile=1
收藏
