An Automatic Construction Method of Indistinguishable Obfuscation for Generic Computing Circuits

ZHU Shuai-shuai; HAN Yi-liang; LI Yu

doi:10.12263/DZXB.20211099

您当前的位置：

首页 >

文章列表页 >

An Automatic Construction Method of Indistinguishable Obfuscation for Generic Computing Circuits

PAPERS | 更新时间：2026-04-10

- An Automatic Construction Method of Indistinguishable Obfuscation for Generic Computing Circuits
- ACTA ELECTRONICA SINICA Vol. 52, Issue 1, Pages: 144-156(2024)
- 作者机构：
  
  1.中国人民武装警察部队工程大学密码工程学院,陕西西安 710086
  2.网络与信息安全武警部队重点实验室,陕西西安 710086
- 作者简介：
- 基金信息：
  
  Natural Science Foundation of Shaanxi Province(2021JM-252);Innovative Research Team Project of Engineering University of APF(KYTD201805)
- DOI：10.12263/DZXB.20211099
  CLC： TP309.7;
- Received：16 August 2021，
  
  Revised：2022-03-14，
  
  Published：25 January 2024
- 稿件说明：
移动端阅览
朱率率,韩益亮,李鱼.通用计算电路的不可区分混淆自动化构造方法[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，

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

）的构造问题是多年来一直困扰密码学研究的一个难题.现有的基于多线性映射、函数加密、全同态加密等密码学原语的

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

构造均存在不同程度的安全性问题，且存在构造过程不易实现、电路扩展效率不高等缺陷.本文从电路的自动化搜索的全新角度审视

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

的设计问题，将电路设计映射到图神经网络构造问题中，基于图神经网络的自动演化技术，探索了一种可以实现限定性满足不可区分性和功能保持性的通用

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

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

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

）.该

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

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 (

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

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

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

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

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

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

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

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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Hybrid Quantum-Graph Neural Network for Multimodal Sentiment Analysis

CS-ROMF:Efficient Community Search Based on Graph Combinatorial Optimization

RWK-GNN: Fraud Detection for Imbalanced Graphs with Feature Enhancement and Subkernel Decomposition

Anomaly Detection with Dual-Channel Heterogeneous Graph Neural Network Based on Hypersphere Dual Learning

Related Author

ZHU Shuaishuai

HAN Yiliang

LI Xing-guang

CAI Yu-jian

CUI Wei

LI Jin-song

ZHANG Ying-yu

ZHANG An-ran

Related Institution

School of Electronic Information and Engineering, Changchun University of Science and Technology

Hong Kong Baptist University, Hongkong

Beijing Information Science and Technology University

School of Software, Beihang University

College of Computer Science, Chongqing University

⁰