基于合理假设的不可区分性混淆技术

《Journal of the ACM》:Indistinguishability Obfuscation from Well-Founded Assumptions

【字体: 大 中 小 】 时间:2025年12月15日 来源:Journal of the ACM

编辑推荐:

   摘要 不可区分性混淆(indistinguishability obfuscation)由[Barak等人于2001年在Crypto会议上提出],其目标是在保持程序功能的同时将其编译成难以理解的代码。这一技术非常强大,已被证明可以实现许多

  

摘要

不可区分性混淆(indistinguishability obfuscation)由[Barak等人于2001年在Crypto会议上提出],其目标是在保持程序功能的同时将其编译成难以理解的代码。这一技术非常强大,已被证明可以实现许多新的密码学目标以及其他应用。然而,到目前为止,构建不可区分性混淆的方法仍然难以找到,所有其他提案都依赖于启发式方法或新提出的难度假设。
在这项工作中,我们展示了如何基于四个具有良好理论基础的假设来构建不可区分性混淆。我们证明了以下定理(非正式表述):假设存在一组常数 τ ∈ (0, ∞), δ ∈ (0, 1), ? ∈ (0, 1),使得以下假设具有亚指数级别的安全性:
•
具有亚指数级模数噪声比的错误学习(Learning With Errors, \(\mathsf {LWE}\))假设,其中模数噪声比为 \(2^{k^\epsilon}\),噪声的大小与 k(\(\mathsf {LWE}\) 的维度)成多项式关系。
•
在一般素数域 \(\mathbb{Z}_p\) 上的带噪声的奇偶性学习(Learning Parity with Noise, \(\mathsf {LPN}\))假设,需要多项式数量的 \(\mathsf {LPN}\) 样本,且错误率为 1/?^δ,其中 ? 是 \(\mathsf {LPN}\) 的维度。
•
存在一个属于 \(\mathsf{NC}^0\) 类的布尔伪随机生成器(Boolean Pseudo-Random Generator, \(\mathsf{PRG}\),其扩展因子为 \(n^{1 + \tau}\),其中 \(n\) 是 \(\mathsf{PRG}\) 种子的长度。
•
关于素数阶对称双线性群的决策线性(Decision Linear, \(\mathsf{DLIN}\))假设。
因此,对于所有多项式大小的电路,都可以实现(亚指数级安全的)不可区分性混淆。
此外,即使仅假设上述假设具有多项式级别的安全性,也可以为所有多项式大小的电路实现抗共谋的公钥功能加密。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号