姓名：凌裕超
学号：17020110044
原文链接：https://www.kepuchina.cn/more/202101/t20210111_2957850.shtml
嵌牛导读：不可区分混淆加密方式深入研究
嵌牛鼻子：不可区分混淆 存在性 可行性
嵌牛提问：什么是加密？什么是不可区分混淆加密？不可区分混淆加密是否具有可行性？
嵌牛正文：
几十年来，计算机科学家一直都想验证是否存在绝对安全的方法来加密计算机程序，让人们在使用计算机的同时却无法破解其程序。
在2020年底，几位学者成功找到了一种加密方式，让计算机用户无法通过获取代码破解程序。
加密程序代码首先要对其进行混淆
不可区分混淆（indistinguishability obfuscation，简称IO）是一种强大的加密算法，它不仅能隐藏数据集，还能隐藏程序本身，从而实现几乎所有的加密协议。
要想知道不可区分混淆是什么，我们不妨先来看一看混淆是什么。
对于程序员来说，最宝贵的自然是代码，一旦源代码被人获取，基本上就等于程序员编写代码花费的心血付诸东流，还会涉及到知识产权纠纷。为了保护代码，有的程序员会在导出程序之前采取一些手段来混淆程序。
当前程序混淆有两种方式，第一种是全文替换关键词，把整段代码中所有的“命名”全部替换成数字（例如将ui_controller替代为a0123456)；第二种是直接输出编译过后的代码，将人们可以看懂的源代码转换成电脑看得懂的机器码，这样别人就没法直接打开这个文件看到原本的代码了。
这两种方式的目的都是在导出程序的时候，把标注性的符号摘除。从而达到不暴露源码信息的效果。
但这两种方式并不是真正意义上的混淆，因为虽然人类难以理解这串代码到底要做什么，但如果把这样的代码放入编译器中，让编译器去分析整个编程语言的语法结构，把每一行指令所要做的事情都归纳出来的话，那么很容易就能看出些端倪。
真正意义上的混淆被称作虚拟黑盒（Virtual Black Box Obfuscation，VBB），相当于将一个程序C嵌入一个黑盒中，我们可以在黑盒的一端输入x，另一头会输出C（x）。因为整个程序都藏在黑盒中，我们完全无法得知任何C的构造信息，也无法从输出反推输入。
如果实现虚拟黑盒，用户可以使用程序却无法理解程序本身，那么就能让开发的程序永远不被破解，并且加密程序的过程也会十分高效。
但虚拟黑盒的概念提出不久后，很快就被泼了一盆冷水。2001年，7位研究者联手提出了一种特殊构造的程序，并证明通用的VBB混淆是绝对不可能的。
不过，这7位研究者的成果中，提出了一种混淆的新型定义——如果一对程序A和B具有相同的功能性，能否通过一种新的混淆算法，使第三方无法区分两个程序呢？对于这样的混淆，我们称之为IO。
其利用的原理是：如果把相同值输入程序A和B，计算得到O（A）=P和O（B）=P，在无法进入程序A或B的情况下，在计算上分辨P来自于A还是B是不可行的。
有了强大的不可区分混淆，我们就能完美加密已有的程序，使其永远不会被破解。
IO存在性被证实但还难以抵御量子计算
2013年，美国加州大学洛杉矶分校的阿米特·沙海教授联合其他5位学者提出一种IO协议，把一个程序拆分为几块，就像拼图游戏，单个碎片看上去毫无意义，但如果使用多线性配对方法将碎片正确地组合到一起，程序就能正常工作。
多线性配对本质上是一种利用多项式进行计算的方法，多项式是由不同变量和数字组成的数学表达式，如3xy+2yz2。为了保证其安全性，用户不能获知整个过程中任何参数。
多线性配对方法中，有一个重要的概念叫做“层数”，它可以理解为运算公式中变量的阶数，如3xy+2yz2为2阶多项式，即其层数为2；3xy+2yz4为4阶多项式，其层数为4。层数越多，多线性配对的安全性越差。
2016年，美国华盛顿大学副教授林惠嘉开始探索能否通过减少多线性配对的层数来实现IO。最初，她想出了如何用30层多线性配对构建IO。接下来，她和其他研究者逐渐实现了只用3层多线性配对来构建IO。
表面上看，这是一个巨大的进步。但有一个问题——从安全的角度来看，3层多线性配对和其他3层以上多线性配对一样不安全。
此前，研究人员只知道2层及以下的线性配对是绝对安全的。林惠嘉与阿米特·沙海联手，试图找出如何用2层线性配对构建IO，但是很长一段时间研究都没有突破。最终，他们想出了一个折中方案：既然实现IO需要3层线性配对，但为了安全需要减少到2层，那么中间是否存在2.5层呢？
研究人员设想了一个系统，使用户可以看到部分变量的值，这让整个机制不需要对太多变量进行加密。但多项式被隐藏的变量必须不能超过2阶，如3x2y+2yz4公式中，z的值可以让用户看到，而变量x、y的阶数由于没有超过2阶因此被隐藏。由此，研究人员在保证线性配对安全性的前提下，成功实现了IO。
虽然几位科学家联手证明了IO的存在性，但量子计算机的超强计算能力，会使得目前绝大部分加密算法都无法抵挡，这意味着所有的加密信息，都将会暴露在量子计算机的面前。现在研究者们正试图开发一条新的通往IO的潜在途径，希望能抵挡住量子攻击。
