石家庄工信部网站备案,上海网站备案核验,拓者设计吧账号,wordpress首页无变化来源#xff1a;数学中国图片来源#xff1a;Kiel Mutschelknaus for Quanta Magazine2018年#xff0c;加州大学洛杉矶分校的研究生Ayush Jain前往日本#xff0c;就他和同事正在开发的强大加密算法进行交流。当他讲述团队正在尝试实现不可区分混淆#xff08;indistingu… 来源数学中国图片来源Kiel Mutschelknaus for Quanta Magazine2018年加州大学洛杉矶分校的研究生Ayush Jain前往日本就他和同事正在开发的强大加密算法进行交流。当他讲述团队正在尝试实现不可区分混淆indistinguishability obfuscation简称iO时一位观众困惑地举起了手。“可我一直以为iO不存在”他说。当时这样的怀疑是普遍存在的。不可区分混淆如果可以被构建不仅能隐藏数据集还能隐藏程序本身从而构建一种可以实现几乎所有其他加密协议的加密算法。但对很多计算机科学家来说强大到如此地步让iO看起来难以实现。计算机科学家从2013年开始提出iO的候选版本。但是他们很快被泼了一盆冷水其他研究者发现了破解它安全性的方法。现在Jain与华盛顿大学的林惠嘉Huijia Lin音译以及Jain在加州大学洛杉矶分校的导师阿米特·沙海Amit Sahai一起证明了这种方法的可行性。在8月18日在网上公开的论文里这三名研究者首次展示了如何仅用“标准的”安全假设来构建不可区分混淆。从左至右依次为Jain、沙海和林惠嘉所有的加密协议都基于某些假设比如著名的RSA算法基于人们普遍认为的观点——标准计算机不能快速对大数进行质因数分解。加密协议的安全性和前提假设是绑定的而iO的前提假设建立在未经检验并且不牢固的基础上。相比之下新的加密协议建立在经过广泛检验的假设基础之上。虽然协议还远未能实用但从理论上讲通过它可以立即构建一系列以前遥不可及的加密方式。例如它支持创建可否认加密deniable encryption这种加密方式可以让你向攻击者发送和真实邮件完全不同的消息以及函数加密functional encryption这种加密可以让你向用户提供不同级别的访问权限从而用数据进行计算。以色列理工学院的尤瓦尔·伊沙伊Yuval Ishai说“现在不会有人怀疑不可区分混淆的存在了这似乎是个不错的结局。”皇冠上的宝石几十年来计算机科学家一直都想知道是否存在安全包罗万象的方法来混淆计算机程序让人们使用的同时无法破解。要想知道不可区分混淆是什么我们不妨先来看一看混淆是什么。例如对于程序员来说最宝贵的自然是代码一旦源码被别人看到了那么基本上花的心血和知识产权都被人一览无余。为了保护代码可以在导出程序之前采取一些手段来混淆程序现在一般有两种程序混淆方法即代码混淆Code Obfuscation和代码编译Compilation。代码混淆是为了防止程序代码本身给外人提供太多信息同时使程序的运行效率更高。在导出程序时会将所有标注性的符号symbols摘除掉。比较简单的方法是直接全文替代关键词例如将全文的ui_controller替代为a0123456这样程序的符号就无法暴露程序运转内容了。代码编译更简单直接输出编译后的代码将人们可以看懂的源代码转换成电脑看得懂的机器码。这个过程就相当于把上面提到的符号全部抹除了他人看到我们发布的可执行文件中的机器码时自然看不懂其中发生了什么。但对人的混淆并不是严格意义上的混淆这样的混淆在密码学的定义上是非常脆弱的。在电脑程序的分析下“混淆”后的程序会变得一览无余一下就能看出程序在干什么。真正意义上的混淆被称作虚拟黑盒Virtual Black Box ObfuscationVBB。将一个程序C嵌入一个黑盒中我们可以在黑盒的一端输入x另一头会输出C(x)。因为整个程序都藏在黑盒中我们完全无法得知任何C的构造信息。唯一可以做的就是提供输入x观察另一头的输出C(x)。我们称这样的黑盒为VBB混淆器O对于经过O混淆的程序C我们称其为O(C)。O(C)的输出C(x)并不会暴露任何关于C的任何信息。如果实现虚拟黑盒用户可以使用程序却无法理解程序本身那么就能让开发的程序永远不被破解或是用很简单地实现公钥加密。密码学中几乎所有比较高级的构造都可以非常简单地用虚拟黑盒实现。但虚拟黑盒的概念提出不久后人们很快就被泼了一盆冷水。2001年七位大牛联手对混淆这一概念做了系统性的研究并且发表了一篇文章On the (Im)possibility of Obfuscating Programs。在文章中他们提出了一种特殊构造的程序并证明其无法被混淆。而这等于是在说通用的VBB混淆是绝对不可能的。不过同样是在这篇论文中一种混淆的新型定义被提出来了——如果一对程序C1和C2具有相同的功能性能否通过一种新的混淆算法使第三方无法区分两个程序的混淆结果呢对于这样的混淆我们称之为不可区分混淆iO。虽然VBB不可能实现但是通过iO我们仍然可以非常完美地混淆一个程序。假如我们有一个程序P我们可以用五花八门的办法和技巧来混淆程序得到一个最强混淆功能却相同的P*。同时如果我们拥有iO那么完全不需要很多费劲的混淆操作可以直接得到相同的结果因为我们无法区分混淆后的iO(P)和iO(P*)。仅仅是给P套了一层iO得到的结果和最强混淆过后P*的iO是一样的。图片来源知乎用户Steven Yue这样一来如果我们想充分混淆一个程序P使其构造不被别人发现只需要输出iO(P)就行了。有了强大的不可区分混淆我们就能完美加密已有的程序使其永远不会被破解。同时由于iO密码学完备Crypto-Complete的特性我们可以轻易借其实现一系列强大的密码学构造。更少即是更多2013年沙海和五位合著者提出了一个iO协议将程序拆成几部分类似拼图然后他们使用多线性配对来找出这些拼图。单个碎片看上去毫无意义但如果将碎片正确地组合到一起程序就能正常工作。多线性配对本质上是用多项式计算的密码学方法——由不同变量和数字之积的加和组成的数学表达式如3xy2yz²。Jain表示这些配对有点类似于一个连接着多项式计算器的密码保险柜。用户输入数字看向最后一位看保险柜中隐藏的数值能否让整个多项式归零。为了保证计划的安全用户不能获知整个过程中任何参数。但是在所有可能的多线性配对候选中打开保险柜的过程都透露了计算过程中应该隐藏的信息。由于多线性配对机制全都有安全性问题林惠嘉开始探索能否通过约束多线性配对的层数来实现iO。这样更容易实现安全性四年前她想出了如何用30层多线性配对构建iO。接下来几年里她、沙海和其他研究者逐渐想出了如何只用3层多线性配对来实现iO。表面上看这是一个巨大的进步。但有一个问题——从安全的角度来看3层多项式配对和其他任意层一样不稳固。研究人员们只知道2层及以下的多线性配对是安全的。林惠嘉与Jain和沙海联手试图找出如何用2层多线性配对应设构建iO。但是“我们被困住了很久很久。“林惠嘉这样说。最终他们与加州大学圣巴巴拉分校的普拉汉汉·安纳思Prabhanjan Ananth区块链项目Concordium的克里斯蒂安·马特Christian Matt一起想出了一个折中方案既然iO需要三层但计算机科学家为了安全需要二层中间是否存在2.5层呢研究人员设想了一个系统其中保险柜上有窗用户可以看到部分密码的值。这让整个机制不需要隐藏太多信息。为了平衡多线性匹配的能力和二层的安全性这个机制允许计算高于二阶的多项式但有一个限制——多项式被隐藏的变量必须不能超过二阶。林惠嘉说“我们试图不去隐藏那么多。”图片来源quanta magazine但是从不太强的多项式配对到iO团队还缺少最后一块拼图——一种新型的伪随性数生成器它能将一串随机的数据转换成扩展成更长更随机的一串。而这正是Jain林惠嘉和沙海在新论文中想出来的。结果是iO协议最终避免了多项式配对的安全性漏洞。“他们的结果看起来几乎是完美的。”康奈尔大学的拉斐尔·帕斯Rafael Pass说。该方案的安全性基于四个数学假设这些假设已经被广泛的应用于其他加密方式中。即使是被研究最少的假设——“Learning Parity with Noise“假设——也和20世纪50年代以来一直被研究的问题有关。很可能只有一种东西能打破新的方案——量子计算机如果我们能造出真正的量子计算机的话。四个假设中的一个容易受到量子攻击但过去的几个月里帕斯和其他研究者分别独立地在论文中得到同一个结果这一结果提供了一条不同的潜在路径让iO在量子攻击下也能确保安全。研究人员表示相较于Jain林惠嘉和沙海的版本这些新版本的iO基于不太成熟的安全假设。哈佛大学的博阿兹·巴拉克Boaz Barak说“但它是有可能的。这两种尝试可能在接下来的几年融合创造一种基于标准安全假设上能抵御量子攻击的新版iO。伊沙伊预测Jain林惠嘉和沙海的创造可能吸引新的研究者进入该领域让该方案更加实用并作出一些新的尝试。他说“一旦你知道某件事原则上是可能的就会让这个领域的研究者在工作时心理上好受得多。”在协议或者是其变体可用于实际应用之前计算机科学家还有许多工作要做。但研究人员表示这是意料之中的。帕斯说“密码学中有很多概念当它们第一次出来的时候人们会说‘这只是纯理论它与实践无关。’然后10年20年后Google开始实施这些计划。”巴拉克说从理论突破到实际可用的协议还有很长一条路要走。“但是你可以想象。或许50年后密码学教科书上会说‘好吧这里有一个很简单的iO构造我们能从中得到其他所有加密方式。”他说。未来智能实验室的主要工作包括建立AI智能系统智商评测体系开展世界人工智能智商评测开展互联网城市云脑研究计划构建互联网城市云脑技术和企业图谱为提升企业行业与城市的智能水平服务。 如果您对实验室的研究感兴趣欢迎加入未来智能实验室线上平台。扫描以下二维码或点击本文左下角“阅读原文”
