通用计算电路的不可区分混淆自动化构造方法
An Automatic Construction Method of Indistinguishable Obfuscation for Generic Computing Circuits
- 电子学报 2024年52卷第1期 页码：144-156
- 作者机构：
1.中国人民武装警察部队工程大学密码工程学院,陕西西安 710086
2.网络与信息安全武警部队重点实验室,陕西西安 710086
- 作者简介：
[ "朱率率 男，1985年出生，山东高青人.博士.武警工程大学密码工程学院.副教授.主要研究方向为密码算法设计、信息安全． E-mail: zsseupap@163.com" ]
[ "韩益亮 男，1977年出生，甘肃会宁人.武警工程大学密码工程学院教授，博士生导师.主要研究方向为公钥密码学、人工智能、算法设计．E-mail: Yilianghan@hotmail.com" ]
[ "李 鱼 男，1995年出生，重庆人.武警工程大学密码工程学院博士研究生.主要研究方向为密码协议，信息安全." ]
- 基金信息：陕西省自然科学基础研究基金(2021JM-252);武警工程大学科研创新团队基金(KYTD201805)
DOI：10.12263/DZXB.20211099
中图分类号： TP309.7;收稿：2021-08-16，
修回：2022-03-14，
纸质出版：2024-01-25
- 稿件说明：
移动端阅览
朱率率,韩益亮,李鱼.通用计算电路的不可区分混淆自动化构造方法[J].电子学报,2024,52(01):144-156.
ZHU Shuai-shuai, HAN Yi-liang, LI Yu.An Automatic Construction Method of Indistinguishable Obfuscation for Generic Computing Circuits[J].Acta Electronica Sinica, 2024, 52(01): 144-156.
朱率率,韩益亮,李鱼.通用计算电路的不可区分混淆自动化构造方法[J].电子学报,2024,52(01):144-156. DOI：10.12263/DZXB.20211099
ZHU Shuai-shuai, HAN Yi-liang, LI Yu.An Automatic Construction Method of Indistinguishable Obfuscation for Generic Computing Circuits[J].Acta Electronica Sinica, 2024, 52(01): 144-156. DOI：10.12263/DZXB.20211099
摘要
不可区分混淆（indistinguishability obfuscation，
<math id="M1"><mi>i</mi><mi mathvariant="normal">𝒪</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714119&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714109&type=
3.47133350
2.37066650
）的构造问题是多年来一直困扰密码学研究的一个难题.现有的基于多线性映射、函数加密、全同态加密等密码学原语的
<math id="M2"><mi>i</mi><mi mathvariant="normal">𝒪</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714128&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714124&type=
3.47133350
2.37066650
构造均存在不同程度的安全性问题，且存在构造过程不易实现、电路扩展效率不高等缺陷.本文从电路的自动化搜索的全新角度审视
<math id="M3"><mi>i</mi><mi mathvariant="normal">𝒪</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714146&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714131&type=
3.47133350
2.37066650
的设计问题，将电路设计映射到图神经网络构造问题中，基于图神经网络的自动演化技术，探索了一种可以实现限定性满足不可区分性和功能保持性的通用
<math id="M4"><mi>i</mi><mi mathvariant="normal">𝒪</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714168&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714175&type=
3.47133350
2.37066650
构造方法：AG
<math id="M5"><mi>i</mi><mi mathvariant="normal">𝒪</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714160&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714142&type=
3.47133350
2.37066650
（Adversarial Graphweualietwork based
<math id="M6"><mi>i</mi><mi mathvariant="normal">𝒪</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714166&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714162&type=
3.47133350
2.37066650
）.该
<math id="M7"><mi>i</mi><mi mathvariant="normal">𝒪</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714168&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714175&type=
3.47133350
2.37066650
的基本架构基于对偶的对抗性图神经网络架构，针对任意给定输入电路，通过图枚举得到备用的电路样本集合，然后使用以子电路为粒度的差分演化算法分别独立优化上述对偶的图神经网络，当自动化判定模型从统计上不能有效识别不同的输出电路时，达到所需不可区分的状态.测试结果表明，该AG
<math id="M8"><mi>i</mi><mi mathvariant="normal">𝒪</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714181&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714179&type=
3.47133350
2.37066650
架构简单，易于实现，较好地实现了输入电路的通用性和统计上的不可区分性.
Abstract
The construction of indistinguishability obfuscation (
<math id="M9"><mi>i</mi><mi mathvariant="normal">𝒪</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714206&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714203&type=
3.47133350
2.37066650
) is a long-term concern confusing the researchers. The existing
<math id="M10"><mi>i</mi><mi mathvariant="normal">𝒪</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714206&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714203&type=
3.47133350
2.37066650
constructions are based on primitives of multi-linear map
functional encryption
fully homomorphic encryption. These routines naturally inherent the shortages appeared in security
efficiency and generic abilities. To explore new approaches satisfying better generic functioning and indistinguishability from the angle of automatic searching
circuit design problems are mapped to the construction of graph neural network. In this paper
we present an
<math id="M11"><mi>i</mi><mi mathvariant="normal">𝒪</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714249&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714231&type=
3.47133350
2.37066650
framework called AG
<math id="M12"><mi>i</mi><mi mathvariant="normal">𝒪</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714249&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714231&type=
3.47133350
2.37066650
(Adversarial Graphweualietwork based
<math id="M13"><mi>i</mi><mi mathvariant="normal">𝒪</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714215&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714214&type=
3.47133350
2.37066650
）
which is based on dual adversarial neural network and can automatically generate sub-optimal
<math id="M14"><mi>i</mi><mi mathvariant="normal">𝒪</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714249&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714231&type=
3.47133350
2.37066650
with functional equivalence and generic circuit obfuscation. The AG
<math id="M15"><mi>i</mi><mi mathvariant="normal">𝒪</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714249&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714231&type=
3.47133350
2.37066650
achieved indistinguishability by circuit garbling which is a natural tool in constructing obfuscation. Then we design the graph-based automatic evolvement
which can well achieve sub-optimal circuit generalization. Through our test
the AG
<math id="M16"><mi>i</mi><mi mathvariant="normal">𝒪</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714249&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=56714231&type=
3.47133350
2.37066650
is simple to deploy and implement
while the efficiency is acceptable in achieving generalization and statistical indistinguishability.
关键词
Keywords
references
BOAZ B , ODED G , RUSSELL I , et al . On the (im)possibility of obfuscating programs [EB/OL]. ( 2001 )[2021]. https://eprint.iacr.org /2001/69.pdf https://eprint.iacr.org/2001/69.pdf .
ZHANG F G , ZHANG Z . Garbled circuits and indistinguishability obfuscation [J]. Journal of Cryptologic Research , 2019 , 6 ( 5 ): 541 .
YAO A C C . How to generate and exchange secrets [C]// 27th Annual Symposium on Foundations of Computer Science (SFCS 1986) . Piscataway : IEEE , 1986 : 162 - 167 .
DAN BONEH , SAHAI AMIT , AND WATERS BRENT . FunctioNal encryption: Definitions and challenges [EB/OL]. ( 2010 )[2021]. https://eprint.iacr.org/2010/543.pdf https://eprint.iacr.org/2010/543.pdf .
BRAKERSKI Z , SEGEV G . Function-private functional encryption in the private-key setting [J]. Journal of Cryptology , 2018 , 31 ( 1 ): 202 - 225 .
LIU X M , ZHAO Q S , ZENG Q K . Verifiable computation using re-randomizable garbled circuits [J]. Journal of Software , 2019 , 30 ( 2 ): 399 .
GARG S , GENTRY C , HALEVI S , et al . Candidate indistinguishability obfuscation and functional encryption for all circuits [J]. SIAM Journal on Computing , 2016 , 45 ( 3 ): 882 - 929 .
BITANSKY N , VAIKUNTANATHAN V . Indistinguishability obfuscation from functional encryption [C]// 2015 IEEE 56th Annual Symposium on Foundations of Computer Science . Piscataway : IEEE , 2015 : 1 - 37 .
戚珉 , 陈明 . 标准模型下基于身份的混淆乐观公平交换方案 [J]. 电子学报 , 2020 , 48 ( 8 ): 1516 - 1527 .
QI M , CHEN M . ID-based ambiguous optimistic fair exchange in the standard model [J]. Acta Electronica Sinica , 2020 , 48 ( 8 ): 1516 - 1527 . (in Chinese)
宋秀丽 , 周道洋 , 文爱君 . d维(t,n)门限量子同态加密算法的设计与仿真 [J]. 电子学报 , 2020 , 48 ( 5 ): 846 - 853 .
SONG X L , ZHOU D Y , WEN A J . Design and simulation of d dimensional (t, n) threshold quantum homomorphic encryption algorithm [J]. Acta Electronica Sinica , 2020 , 48 ( 5 ): 846 - 853 . (in Chinese)
GARG S , GENTRY C , HALEVI S . Candidate multilinear maps from ideal lattices [C]// Advances in Cryptology-EUROCRYPT 2013 (Lecture Notes in Computer Science) . Berlin : Springer , 2013 : 1 - 17 .
JEAN-SBASTIEN C , TANCRDE L , MEHDI T . Practical multilinear maps over the integers [C]// Advances in Cryptolog-CRYPTO 2013 (Lecture Notes in Computer Science) . Berlin : Springer , 2013 : 476 - 493 .
GENTRY C , GORBUNOV S , HALEVI S . Graph-Induced multilinear maps from Lattices [C]// Theory of Cryptography . Heidelberg : Springer , 2015 : 498 - 527 .
SAHAI A , WATERS B . How to use indistinguishability obfuscation: Deniable encryption, and more [C]// Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing . New York : ACM , 2014 : 475 - 484 .
GARG SANJAM , GENTRY CRAIG , HALEVI SHAI , et al . Two-round secure mpc from indistinguishability obfuscation [C]// Theory of Cryptography . Berlin : Springer , 2014 : 74 - 94 .
BONEH D , ZHANDRY M . Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation [J]. Algorithmica , 2017 , 79 ( 4 ): 1233 - 1285 .
CHEON J H , HAN K , LEE C M , et al . CryptaNalysis of the multilinear map over the integers [C]// Advances in Cryptology- EUROCRYPT 2015 . Berlin : Springer , 2015 : 3 - 12 .
CHEN Y L , GENTRY C , HALEVI S . CryptaNalyses of candidate branching program obfuscators [C]// Advances in Cryptology-EUROCRYPT 2017 . Berlin : Springer , 2017 : 278 - 307 .
BRAKERSKI Z , ROTHBLUM G N . Virtual black-box obfuscation for all circuits via generic graded encoding [M]// Theory of Cryptography . Berlin : Springer , 2014 : 1 - 25 .
BOAZ B , SANJAM G , YAEL T K , et al . Protecting obfuscation against algebraic attacks [C]// Advances in Cryptology - EUROCRYPT 2014 . Berlin : Springer , 2014 : 221 - 238 .
GARG S , MILES E , MUKHERJEE P , et al . Secure obfuscation in a weak multilinear map model [C]// Proceedings , Part II, of the 14th International Conference on Theory of Cryptography - Volume 9986 . New York : ACM , 2016 : 241 - 268 .
LIN H J . Indistinguishability obfuscation from constant-degree graded encoding schemes [C]// Advances in Cryptology-EUROCRYPT 2016 (Lecture Notes in Computer Science) . Berlin : Springer , 2016 : 28 - 57 .
LIN H J , TESSARO S . Indistinguishability obfuscation from trilinear maps and block-wise local PRGS [C]// Advances in Cryptology-CRYPTO 2017 (Lecture Notes in Computer Science) . Cham : Springer , 2017 : 630 - 660 .
ANANTH P , JAIN A , LIN H J , et al . Indistinguishability obfuscation without multilinear maps: New paradigms via low degree weak pseudorandomness and security amplification [C]// Advances in Cryptology- CRYPTO 2019 (Lecture Notes in Computer Science) . Cham : Springer , 2019 : 284 - 332 .
JAIN A , LIN H J , MATT C , et al . How to leverage hardness of constant-degree expanding polynomials over R to build iO [C]// Advances in Cryptology-EUROCRYPT 2019 . Cham : Springer , 2019 : 251 - 281 .
DÍEZ J , DEL COZ J J , LUACES O , et al . Using tensor products to detect unconditional label dependence in multilabel classifications [J]. Information Sciences: An International Journal , 2016 , 329 ( 1 ): 20 - 32 .
AGRAWAL S . Indistinguishability obfuscation without multilinear maps: New methods for bootstrapping and instantiation [C]// Advances in Cryptology-EUROCRYPT 2019 . Cham : Springer International Publishing , 2019 : 191 - 225 .
AGRAWAL S , PELLET-MARY A . Indistinguishability obfuscation without maps: Attacks and fixes for noisy linear FE [C]// Advances in Cryptology-EUROCRYPT 2020 . Cham : Springer International Publishing , 2020 : 110 - 140 .
BRAKERSKI Z , DÖTTLING N , GARG S , et al . Candidate iO from homomorphic encryption schemes [J]. JourNal of Cryptology , 2023 , 36 ( 3 ): 1 - 41 .
LINDELL Y , PINKAS B . A proof of security of Yao’s protocol for two-party computation [J]. Journal of Cryptology , 2009 , 22 ( 2 ): 161 - 188 .
BELLARE M , HOANG V T , ROGAWAY P . Foundations of garbled circuits [C]// Proceedings of the 2012 ACM Conference on Computer and Communications Security . New York : ACM , 2012 : 784 - 796 .
GOLDWASSER S , KALAI Y , POPA R A , et al . Reusable garbled circuits and succinct functional encryption [C]// Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing . New York : ACM , 2013 : 555 - 564 .
WU Z H , PAN S R , CHEN F W , et al . A comprehensive survey on graph neural networks [J]. IEEE Transactions on Neural Networks and Learning Systems , 2021 , 32 ( 1 ): 4 - 24 .
车向北 , 康文倩 , 邓彬 , 等 . 一种基于图神经网络的SDN路由性能测试模型 [J]. 电子学报 , 2021 , 49 ( 3 ): 484 - 491 .
CHE X B , KANG W Q , DENG B , et al . A prediction model of SDN routing performance based on graph neural network [J]. Acta Electronica Sinica , 2021 , 49 ( 3 ): 484 - 491 .
STORN R , PRICE K . Differential evolution - A simple and efficient heuristic for global optimization over continuous spaces [J]. Journal of Global Optimization , 1997 , 11 ( 4 ): 341 - 359 .
WANG D X , CUI P , ZHU W W . Structural deep network embedding [C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . New York : ACM , 2016 : 1225 - 1234 .
WANG J S . A general algorithm for enumerating some subgraphs of a simple graph [J]. Journal of Computers , 1986 , 1 : 39 - 45 .
HALEVI S , HALEVI T , SHOUP V , et al . Implementing BP-obfuscation using graph-induced encoding [C]// Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM , 2017 : 783 - 798 .
APON D , HUANG Y , KATZ J , et al . Implementing cryptographic program obfuscation [EB/OL]. ( 2014 )[2021]. https://eprint.iacr.org/2014/779.pdf https://eprint.iacr.org/2014/779.pdf .
0
浏览量
0
下载量
0
CSCD
- 网络PDF下载
- Meta-XML下载
- BibTeX下载
- Endnote下载
- RefMan 下载
- NoteExpress下载
- NoteFirst下载
关联资源
相关文章
相关作者
相关机构
- 技术支持由北京北大方正电子有限公司提供 京ICP备09064830号-19
京公网安备11010802024621 - 本系统建议在Chrome、 IE9+ 以上版本浏览器阅读本站内容，360浏览器请切换至极速模式
- Cookies帮助我们提供服务并提供个性化体验。使用本网站，即表示您同意我们使用Cookies