标准PRF假设下基于立体几何变换的轻量级混淆电路协议  

Lightweight Garbled Circuit Protocol Based on Solid Geometry Transformation under Standard PRF Assumption

作　　者：谭振华[1] 宁婧宇 TAN Zhen-Hua;NING Jing-Yu(Software College,Northeastern University,Shenyang 110819)

机构地区：[1]东北大学软件学院,沈阳110819

出　　处：《计算机学报》2023年第10期2240-2257,共18页Chinese Journal of Computers

基　　金：国家重点研发计划基金资助项目(No.2019YFB1405803);中央高校基本科研业务费专项资金(N2217001);国家自然科学基金资助项目(No.61772125)资助.

摘　　要：混淆电路(Garbled Circuit,GC)是安全两方计算(Secure Two-Party Computation,S2PC)的重要基础协议.为保证安全性,GC协议需要调用加密算法对电路中的门信号进行加密混淆.当前,GC协议构造每个二元门(如与门)需调用4次加密算法,标准伪随机函数(Pseudorandom Function,PRF)假设下,每个二元门的混淆表至少包含2个密文.如何有效降低加密算法调用次数与混淆表规模,是GC协议提升性能的主要研究问题.本文在标准PRF假设下,提出了一种基于立体几何变换的轻量级混淆电路协议SGT-GC,根据每类二元门信号逻辑设计了专门的立体几何变换,并替代传统的加密算法实现混淆门的构造.其中,对于每个二元混淆与门(AND Gate),首先将其4种可能的输入组合(00,01,10,11)转换为三维空间中不共圆的4个点坐标P00、P01、P10、P11,经过逻辑值为FALSE的三个点(P00,P01,P10)构造圆,然后在经过圆心的圆平面法线上取任意点C,i并满足该点到P00、P01、P10的距离相等且不同于到逻辑值为TRUE的点P11的距离.则该随机点Ci即可作为二元与门混淆表中的交换信息,其通信成本变成1,且不再需要额外的加密算法调用.对于二元混淆异或门以及一元非门,本文也进行了专门的设计并给出了详细的协议过程与数学论证.本文所提出的SGT-GC协议中,每个混淆表中仅需1个共享交换信息,且不需调用任何额外加密算法,避免了多次调用复杂的加密算法所造成的计算成本及传输混淆表中多条密文所造成的通信成本.安全性证明表明,本文所提协议在半诚实模型下满足隐私性、不经意性和可认证性.Garbled Circuit(GC)plays a critical role in Secure Two-Party Computation(S2PC).Since Boolean circuits reveal the input information of participants,Yao proposed the first Garbled Circuit,which could protect the security and privacy during communication.After Yao's,how to optimize GC has attracted great attention in decades,from the perspectives of computation or communication.To ensure the security,GC protocols consistently encrypt the gates in the circuits by encryption algorithms.Each gate invokes the encryption algorithm 4 times.Under standard pseudorandom function(PRF)assumption,the garbled table of each AND gate consists of 2 ciphertexts.Despite the secure requirement is liberalized to non-standard assumption,the garbled table of each AND gate consists of 1.5 ciphertexts.Invoking encryption algorithms and transferring garbled tables leads to prohibitively high cost of computation and communication.In view of this,this paper proposes a lightweight garbled circuit based on solid geometry transformation under standard PRF assumption,called SGT-GC.Without invoking any encryption algorithms,SGT-GC satisfies the security requirements during the garbling process with special solid geometry transformations.Each wire has two options,namely TRUE and FALSE,thus each binary gate has four input options(00,01,10,11).Using distinct solid geometry transformations,four input options are converted into coordinates of four points in three dimensions(P00,P01,P10,P11),from which the Generator can calculate the coordinates of a specific point that is regarded as the shared information in garbled table.For each garbling AND gate in SGT-GC,the input options(00,01,10)output FALSE and(11)outputs TRUE.We select a random point Ci on the normal of the circle surface passing through the center of the circle which constructed by points P00,P01 and P10.Such a Ci has the same distance to points P00,P01 and P10,but has the different distance to P11.As a result,we use the random Ci as the only shared information between the Generator and the E

关 键 词：混淆电路 安全两方计算 立体几何变换 标准伪随机函数假设 安全协议 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]