HHSS 混淆的限制:基于格的区分攻击

作者 Jung Hee Cheon,Minki Hhan,Jiseung Kim,Changmin Lee
时间 2018-04-30

不可分辨性混淆是一种有希望的工具,它能够以最少的泄漏来混淆程序,并生成各种应用程序,包括函数式加密。
最近,Halevi 等人在 ACM-CCS'17 上提出了一种基于分支程序矩阵 HHSS 的最先进的混淆器。

在这项工作中,本文描述了可以应用于 HHSS 混淆的第一种攻击算法,具体取决于分支程序矩阵的维数。当给出两个矩阵分支程序和一个使用 HHSS 混淆的混淆程序时,我们可以区分哪个分支程序用于制作混淆程序。

攻击使用分支程序矩阵乘积的左核。
如果在左内核中获得一个短矢量,将操纵零测试过程的结果,因为 HHSS 混淆会在初始化步骤中为其效率删除一个称为“标量绑定”的特殊设置。
更确切地说,zerotesting 过程公开了分支程序矩阵乘积的左核,所以可以在左核上使用一个采用格减小算法的属性。
事实上,使用晶格简化算法找到了一个简短的向量。
因此,本文可以在复杂性 $ 2 ^ {O( frac {d} {B- epsilon})} $中找到想要的矢量,其中 $d$ 是分支程序矩阵的维度和间隙参数 $B$ 和实际值 $\epsilon$ 给出。例如,可以找到一个应用 LLL 算法的短向量,该向量由$d = 100$ 的 HHSS 实现提出。这对混淆程序的评估进行预计算需要不到一秒的时间。

App

链闻 App

扫码下载

公众号 小程序