混淆电路与不可区分混淆*

张 正, 张方国

1.中山大学数据科学与计算机学院, 广州510006

2.广东省信息安全技术重点实验室, 广州510006

1 引言

随着对称密码和公钥密码的不断发展, 仅仅对消息的加密已经不能满足人类社会的安全需求.云计算、协同计算等新型计算模型的出现, 也使得对函数或电路的加密变得越来越重要.在交给代理商进行计算之前, 用户希望不仅仅对输入加密, 对函数本身也进行加密, 从而达到保护函数 “内部信息” 的目的.例如若医院将疾病的诊断外包, 那么不仅病人的信息涉及隐私, 疾病的诊断方法也是医院需要保护的信息.因此,对于函数或电路的加密成为一个新的研究热点, 许多相关的密码学方案也被提出.其中, 包括混淆、函数加密(functional encryption)、混淆电路(又称混乱电路, 加密电路等)、随机编码(randomized encoding)等等.其中, 有两个相近的概念——混淆和混淆电路.

混淆是由程序混淆[1]发展而来.学者们最初为了保护代码安全而提出混淆的概念.也就是说, 混淆的目的是在保持程序功能的前提下, 使得程序内容 “不可读”.电路混淆或者说函数混淆起始于 Hada 的研究[2].Hada 提出的混淆要求混淆后的程序相当于一个黑盒预言机, 除非函数是可学习的, 否则这种混淆的构造是不存在的.在 2001 年, Barak 等人[3]第一次提出了电路混淆的形式化定义, 并给出了可证明的安全定义——虚拟黑盒安全(virtual black box).这种安全定义除了电路输出其他信息都不泄露.但是,Barak 等人在文章中表示, 虚拟黑盒混淆不具有通用构造方案, 即存在一类函数无法达到虚拟黑盒混淆安全.同篇文章中提出了一种弱化的混淆方案, 称为不可区分混淆(indistinguishability obfuscation).不可区分混淆是指两个规模相同、功能相同的电路在混淆后不可区分, 而且保留其功能性.Garg 在2016 年[4]提出第一个利用多线性映射构造通用不可区分混淆的方案.之后, Bitansky 等人[5]和Ananth 等人[6]又分别使用公钥和私钥函数加密构造不可区分混淆.Lin 等人[7–10]在此基础上, 利用低维的多线性映射(最低完成维度为3 的) 构造函数加密从而完成不可区分混淆的构造.但是现有文章中构造的多线性映射方案均存在不同程度的安全性问题, 以及效率低下的缺点, 利用安全的密码原语构造高效的通用不可区分混淆方案依然是很多学者的研究重点.

混淆电路最初是由 Yao 在 1986 年[11]为解决安全两方计算而提出的一种电路加密技巧.之后, 由Goldreich 等人[12]将此方案中两个参与者扩展为多个.但是, 混淆电路一直是以协议中一种处理技巧进行描述, 没有独立的定义和证明.直到 2008 年, Lindell 等人[13]在对 Yao 的方案进行安全证明中第一次提出了混淆电路方案, 将混淆电路提取成一个独立的方案.之后, 2012 年, Bellare 等人[14]给出混淆电路具体的形式化定义, 以及隐私性、健忘性、可靠性等安全定义.此项工作奠定了混淆电路做为一项独立的密码方案的基础.Hemenway 等人[15]在 2016 年提出自适应安全的混淆电路方案.但是, 这些混淆电路的方案均有一个缺点——不可重用.可重用的混淆电路是否存在这个问题困扰了学者三十多年, 直到2013年, Goldwasser 等人[16]利用全同态加密以及基于属性的加密方案构造了第一个可重用的混淆电路方案.之后, Wang 等人[17]又对此进行改进, 舍弃原方案的安全性等级, 利用随机线性码构造的混淆电路替换Goldwasser 方案中的全同态加密.然而这些可重用混淆电路方案都不高效, 是否存在更高效的可重用的混淆电路依然是人们关注的问题.除此之外, 可重用混淆电路是否可以构造混淆也是一个待探索的问题.

从表面来看, 不可区分混淆和混淆电路存在很多相似的地方.比如说, 在功能上两者都是对电路进行“加密” 以保护电路安全性为目的, 都要求 “加密” 后的电路保留其功能性.而在安全定义上, 不可区分混淆的不可区分性和混淆电路基于不可区分安全相似: 均要求功能相同、规模相同的电路在“加密” 后不可区分.

但是, 从已有的构造方案来看, 混淆电路仅仅需要对称加密方案和伪随机函数即可完成构造, 而不可区分混淆需要用到多线性映射这种效率不高且安全性不稳定的工具.根据已有的实现方案对比, 不可区分混淆的方案在对于规模不超过100 的电路进行混淆需要的时间在小时级别[18–20], 而混淆电路抵抗半诚实的敌手可以达到每个门的平均加密时间为 10 微秒[21], 抵抗恶意的敌手可以达到每个门的平均加密时间为50 毫秒[22].也就是说, 现有的构造方案, 混淆电路的效率远远高于不可区分混淆.

这两者之间的效率差距如此之大, 使得我们开始思考不可区分混淆和混淆电路的区别到底在哪里？是否能够利用现有的混淆电路去构造不可区分混淆？如果不能, 屏障又在哪里？本文即是以这几个问题为出发点, 对不可区分混淆和混淆电路进行研究.通过对定义、安全要求、应用场景的分析, 得到两者之间的区别与联系.并试图通过相互构造, 为进一步的研究提供思路.

本文主要综述基于混淆电路和混淆两个密码体制, 探索两个密码体制之间的区别与联系.本文分为两部分.第 2–4 节为第一部分, 首先介绍布尔电路, 接下来讲混淆电路和混淆的语义定义、安全定义、构造方案、应用等; 第 5–6 节为第二部分, 主要讲混淆电路与混淆的区别与联系.首先探索混淆电路与混淆的区别, 从设计初衷、定义、安全要求、构造难度等方面分析, 接下来探索混淆电路和混淆的相互构造并分析难点所在, 为接下来的研究提供新思路.

2 布尔电路简介

计算模型一般分为两类, 一致性模型 (uniform models) 和非一致性模型 (non-uniform models).一致性模型包括单带图灵机(single-tape turing machines)、多带图灵机(multi-tape turing machines) 等,而非一致性模型包括布尔电路(boolean circuits)、接受建议的机器(machines that take advice).其中布尔电路是最为人们熟知的非一致性模型.布尔电路通过一些逻辑门操作完成函数的计算功能, 因此混淆和混淆电路对布尔电路的“加密” 即隐藏电路的门操作种类甚至电路逻辑图.本节将对布尔电路这一计算模型进行简单的介绍, 包括电路的定义与性质、函数与电路之间的转换、通用电路等.

2.1 电路的定义与性质

布尔电路作为一种非一致性模型, 能够为不同输入规模的同一个函数设计不同的电路.而一个具体的布尔电路是一个有向无环图, 其利用标准布尔操作与(∧)、或(∨)、非 (¬) 作用到输入的二进制串上产生输出结果.而对于与和或操作, 要求点的入度为2, 对于非操作要求点的入度为1.其具体定义如下:

定义 1(布尔电路[23]) 对任意n∈N, 一个n输入单输出的布尔电路是具有n个源顶点和m个汇顶点的有向图.其中:

• 源顶点也称输入顶点, 指的是入度为0 的顶点.汇顶点也称输出顶点, 指的是出度为0 的顶点.

• 每个非源顶点称为一个逻辑门, 并用逻辑操作∧(与)、∨(或)、¬(非) 中的一个操作进行标记.

• 顶点的扇入度指的是进入该顶点的边的条数.标记为∧和∨的顶点的扇入度等于2, 而标记为¬的顶点的扇入度等于1.

• 布尔电路C的规模 (或大小) 是C中顶点的个数, 记为 |C|.

• 如果C是一个布尔线路而x∈{0,1}n是它的一个输入, 则将C在x上的输出记为C(x),C(x)可以自然的定义如下.形式上, 我们为C中每个顶点v定义输出值val(v): 如果v是第i个源顶点, 则定义 val(v) =xi; 否则, val(v) 递归的定义为将顶点v上的逻辑操作作用于v的所有入边关联的顶点的输出值上得到的结果.C(x) 是C的输出顶点的值.

在实际构造过程中, 由于非门可以和与门、或门进行合并.例如电路¬x1∧x2可以看作一个门电路g(x1,x2)=¬x1∧x2.如果将电路中的非门均进行此修改, 那么布尔电路中所有逻辑门将被看作一个二元函数g: {0,1}×{0,1} →{0,1}.统一的结构便于设计加密方案, 因此若不做特殊说明, 文章中出现的逻辑门不再局限于与门、或门, 而是看作一个二元函数.由于输出长度为m的电路可以拆分为m个子电路.因此, 在构造方案中一般考虑输出长度为1 的电路.

布尔电路一旦选定, 有向无环图的结构也被确定下来.常见的可以使用一个六元组f=(n,m,q,A,B,G) 表示一个布尔电路[14].其中n⩾ 2 表示输入长度,m⩾ 1 表示输出长度,q⩾ 1 表示门的个数.输入顶点有n个, 每个门对应一个顶点, 则图中顶点共有n+q个.将输出均用门顶点表示, 因此有向无环图中共有r=n+q条线, 令输入 (顶点) 标记为 Inputs = {1,··· ,n}, 线 (边) 标记为 Wires = {1,··· ,n+q}, 输出 (边) 标记为 OutputWires = {n+q−m+1,··· ,n+q}, 门 (顶点) 标记为 Gates = {n+1,··· ,n+q}.A、B、G均为函数.A: Gate → WiresOutputWires 输出每个门的第一条输入线标号.B: Gate → WiresOutputWires 输出每个门的第二条输入线标号.G:Gates×{0,1}2→{0,1} 表示门计算, 即表示门的种类.

布尔电路的规模是指其逻辑门的个数, 记作|C|.另外一个衡量布尔电路计算规模的参数是深度.布尔电路的深度是指从输入顶点到输出顶点最长一条路的长度, 记作 depth(C).电路规模衡量一个电路的大小, 电路深度衡量的是一次计算需要的时间.

2.2 电路与函数

作为非一致性模型, 单个电路很难衡量一个问题的复杂度.因此, 将不同输入长度的电路放入一个集合中, 以集合为单位即可描述一个任意输入长度的问题.将不同输入长度的电路放入一个集合中, 这样的形式称为电路簇.电路簇的形式化定义如下:

定义 2(电路簇[24]) 设T:N →N 是一个函数,T(n) 规模的电路簇是一系列布尔电路 {Cn}n∈N, 其中Cn有n个输入位和一个输出位, 并且其规模 |Cn|T(n) 对任意n成立.

将同一问题的不同输入规模的电路放入集合也可构造一个电路簇, 这样的电路簇 {Cn}n∈N可以计算一个函数f: {0,1}∗→{0,1}∗.若函数f输入x, 从电路簇中选取电路C|x|用来计算C|x|(x).因此, 利用电路簇的规模复杂度可以度量函数的复杂度.电路簇的规模复杂度定义为函数s:N →N, 其中s(n) 是电路Cn的规模.函数f的电路复杂度 (circuit complexity), 记作sf, 是指能计算f的最小规模电路簇的规模复杂度.其形式化定义如下:

定义 3(电路复杂度[24]) 函数f: {0,1}∗→ {0,1}∗的电路复杂度定义为函数sf: N → N, 其中sf(n) 表示将f限定为n比特输入串时, 能计算f的最小电路.

根据电路深度和电路规模, 可以将电路簇分为不同的 NCd类.最常用的为 NC0和 NC1两类, 即深度为常数规模和对数规模的电路.Barrington[25]提出任意一个深度为d的电路都可以转化为一系列大小为5×5、数量为4d的矩阵相乘形式的矩阵分支程序.这种方法称为Barrington 定理.根据此定理, NC1级别的电路可以转化为多项式规模的矩阵分支程序, 将电路的“加密” 转化为对矩阵的“加密”.

定义 4(NC 类[24]) 对于任意d, 如果存在判定问题L的电路簇{Cn} 使得Cn的规模为poly(n) 且深度为O(logdn), 则称L属于 NCd类.

电路簇使得布尔电路对于输入规模的限制放开, 成为了联系一致性模型和非一致性模型的纽带.如果给定n, 可以在 poly(n) 时间内构造出电路Cn, 那么此多项式规模的电路簇 {Cn}n∈N被称为是一致的.一个函数可以由一致的多项式规模电路簇计算, 那么它可以由多项式时间算法计算.这个算法首先构造出一个电路, 然后对给定输入计算电路的输出.因此, 多项式规模电路簇可以求解的判定问题属于P/poly.

2.3 通用电路

将不同输入规模的电路放入集合中称为电路簇, 那么将相同规模的电路整合为一个电路称为通用电路.一个通用电路可以计算规模相同的任意一个电路, 通过增加对电路的描述作为输入使得通用电路的输出为不同电路的计算结果.通用电路与通用图灵机相似, 将函数转化为数据作为程序的输入.因此, 通用电路的深度问题与图灵机的时空转换问题相关[26].

若将一个函数的表述加到电路的输入中, 使得电路的输出结果等于函数的计算结果, 这样的电路称为通用电路 (universal circuits).通用电路可以计算规模相同的任意一个电路.即对任意一个通用电路UC(x,p), 输入任意一个规模为n的电路C的描述p以及此电路的输入x, 得到UC(x,p)=C(x).

valiant 在 1976 年[26]提出了一种有效的通用电路构造方案.有效的是指通用电路的规模和深度是多项式级别扩展的.而valiant 的方案对电路规模为k的电路构造的通用电路规模为O(klogk), 深度为O(k).Cook 等人在 1 985 年[27]提出了深度是线性的、规模为的通用电路构造方案.之后又不断有学者提出优化的构造方案[28–31].通用电路可以有效的隐藏计算电路的拓扑结构, 因此在很多密码方案中均有应用.

3 混淆电路

混淆电路对于安全多方计算的意义重大, 而 Yao 构造安全多方计算常用的混淆电路一直被看作一种构造方法.直到 2012 年, 混淆电路才作为一个独立的密码方案出现, 随之给出其语义定义、安全定义等.本节将对混淆电路做出详细地介绍.首先3.1 节整理对混淆电路的语义定义, 以及选择性安全、适应性安全、基于模拟安全、基于不可区分安全等不同安全级别的安全定义.此外简单介绍一些混淆电路的性质或扩展.接下来在3.2 节说明经典的Yao 构造混淆电路方案以及一些优化方案.最后将简述混淆电路的不同应用场景.

3.1 语义定义及安全定义

混淆电路起源于Yao 在1982 年和1986 年[11,32]提出的关于安全两方计算协议的构造之中.在文章中, Yao 构造一个安全两方计算协议来解决著名的大富翁问题, 即有两个大富翁Alice 和Bob, 他们想要在不泄露自己具体财富值的情况下得知谁更富有.这个问题相当于对一个比较两输入大小的电路进行加密, 使得每个人都可以得到最终结果并且无法获取他人的输入.随后在 1987 年, Glodreich 等人[12]具体描述了基于Yao 的方法构造安全两方计算协议.而Beaver 等人[33]则在1990 年首次提出混淆电路的定义.在1999 年, Naor 等人[34]利用伪随机函数构造混淆电路并应用到隐私保护的拍卖过程中.

2008 年, Lindell 等人[13]在证明 Yao 的两方安全计算协议中, 利用形式化的语言描述了混淆电路的构造过程.2012 年, Bellare 等人[14]首次给出严谨的形式化定义和安全性定义.Bellare 等人提出的形式化定义中, 一个混淆电路方案由五个子函数组成GC = (Gb,En,Ev,De,ev), 分别用做混淆电路、加密输入、计算输出、解密输出以及函数计算.除了混淆电路函数Gb 和加密输入函数 En 外, 计算函数Ev 和解密函数De 经常看作一个函数使用, 而ev 函数是原始函数在未加密状态下的计算过程.因此, 学者们普遍使用的混淆电路的定义是简化后的三元组函数G=(Gb,En,Ev).

定义 5(混淆电路) 一个混淆电路方案可以看作一个三元组算法G= (Gb,En,Ev), 每个算法的功能如下:

• Gb(1λ,C) →(F,k).此算法用来对电路C进行加密.输入函数C和安全参数k, 输出 (F,k) 表示加密后的电路F以及一个密钥k.

• En(k,x)→X.此算法用来加密输入.输入函数C的输入x以及加密密钥k, 加密得到输入的密文X.

• Ev(F,X) →Y.此算法用来在密文状态下计算电路C.输入加密后的函数F以及加密后的输入X, 得到输出Y=f(x).

此定义要求满足正确性, 即对于任意电路C和输入x, 都有

混淆电路的安全定义分为四种: 基于模拟的选择性安全, 基于不可区分的选择性安全, 基于模拟的自适应安全和基于不可区分的自适应安全[15].基于模拟和基于不可区分是指在敌手区分加密函数的能力,而选择性安全和自适应安全则是要求敌手是否可以根据加密后电路选取输入.四种安全定义分别对应一个游戏SimSel, IndSel, SimAda, IndAda 如图1 所示.四种安全的成立要求在对应游戏中, 敌手区分的能力优势可忽略, 即

除此之外, 混淆电路还有一些其他相关的性质特点.

图1 SimSel, IndSel, SimAda, IndAda 游戏过程Figure 1 Game of SimSel, IndSel, SimAda and IndAda

首先是关于函数f的辅助函数——侧信息函数.加密的过程中, 虽然电路和输入在符合安全定义情况下都得到了不同程度的保护, 但是不可避免地还是会产生一些关于明文的额外信息的泄露.我们称这种关于明文的额外信息为侧信息[14].侧信息函数Φ(f) 就是用来表示对函数f的侧信息泄露.常用的侧信息函数有三种, 分别为 Φsize, Φtopo, Φcirc.其中 Φsize表示泄露函数f的电路大小, 包括输入输出长度、门的个数等信息.Φtopo表示泄露函数f的电路拓扑图, 相当于敌手可获取到将输入和输出以及所有门看作图的顶点, 电路的连接线看作图的边所构成的有向无环图.Φcirc则表示泄露函数f的整个电路图, 即仅仅保护输入而电路是公开的.侧信息函数有利于将加密后所隐藏的信息和泄露的信息形式化的表示, 从而更加清晰地表现了加密函数功能性和信息隐藏的能力.一般来说, 对于侧信息为Φtopo的混淆电路方案可借助于通用电路转化为侧信息为Φsize的混淆电路方案.

由于传统的基于Yao 的加密函数方案都有一个通病, 即混淆电路的一次性.若多次使用不同的输入计算混淆电路, 那么隐藏的电路信息和输入信息将被泄露.因此, 有学者提出可重用混淆电路[16], 即对加密后的电路F, 可以使用多个不同的输入计算 En(k,x) →X, 且不泄露电路和输入的信息.此外, 如果加密输入X的每个比特仅与输入x的一个比特相关, 那么我们称此混淆电路是投射的[35].

3.2 常见构造方法

2008 年, Lindell 等人[13]在证明 Yao 的安全两方计算协议中, 描述了混淆电路的构造过程.完整的构造是从加密一个门开始到加密整个电路.假设g是布尔电路C的一个门, 那么g可以表示为一个函数g:{0,1}×{0,1}→{0,1}.其中两个输入线标记为ω1,ω2, 输出线标记为ω3.随机生成六个密钥分别表示三条线的输入为 0 和 1 两种情况.接下来, 门g将会利用一个对称加密方案E产生四个密文c0,0,c0,1,c1,0,c1,1.具体构造方法如图2 所示.

图2 Yao 的混淆电路构造方案Figure 2 Construction of garbled circuits from Yao

将四个密文进行一个随机置换即得到门g的加密表c0,c1,c2,c3.在计算门g的时候, 利用对应的密钥解密c0,c1,c2,c3, 如果某个解密结果不是⊥, 那么得到的结果即为有了对一个门的加密方案之后, 对整个电路进行类似的加密方法, 即可得到整个加密方案.在Bellare 等人给出混淆电路的形式化定义后, 对于此种构造方法可利用双密钥加密方案加密, 即可实现基于安全的密码原语构造混淆电路的工作.这些构造均为选择性安全的.2016 年, Hemenway 等人[15]提出了基于模拟自适应安全的混淆电路, 通过对输入密钥进行对称加密, 完成了由选择性安全到自适应安全的转化.Jafargholi 等人[36]在此基础上构造了基于不可区分的自适应安全混淆电路.

四个密文若按照真值表的顺序公布可能会泄露信息.为了安全着想, 需要将四个密文c0,c1,c2,c3进行随机置换.Beaver 等人[33]提出一种Point-and-permute 技术来优化这一过程.在每条线的密文中都设置一个随机的置换比特.的置换比特相反且没有对应关系, 即中置换比特与b无关.而对于四个密文则可以用两个密钥的置换比特进行标记, 这样既不泄露信息而且在解密时仅需解密对应置换比特的密文.这样的话, 对称加密方案也可替换为一个简单的一次性加密方案其中H是一个带种子的伪随机函数.Naor 等人[34]在此基础上提出若适当的选择可以使得置换比特对应的第一个密文变为全为零的字符串, 这样只需传输三个密文即可.

除此之外,Kolesnikov 和Schneider 在2008 年[37]提出了Free-XOR 技术.Free-XOR 技术是选定一个共同的秘密值∆∈{0,1}λ,此秘密值全局唯一.对于每条线的标签的选择需满足即这种构造方式的优点是对于异或门计算的简化.若电路中存在异或门g= (ω1,ω2,ω3),那么无需再进行加密计算仅需直接计算即可.因此, 混淆电路仅需对非异或门仅需对称加密即可, 实现了效率上的提高.这项技术还被Ball 等人[38]应用在算术电路中, 使得在 Zm上加法和数乘的计算优化.类似于Free-XOR 技术, 首先选择一个公共秘密值将每条线的标签设为其中是 Zm上的向量.因此, 对于加法计算满足对于数乘计算满足使得在算术电路中加法门和数乘门的计算简化.

而 Zahur 等人在 2015 年的 EUROCRYPT 会议上提出了一种名为半门的设计思路[39], 此方法在Free-XOR 的基础上减少了与门的密文数量.假设电路中存在一个与门ω3=ω1∧ω2, 且利用 Free-XOR技术给出每条线的标签为若按照原来的方案需要至少3 个密文的传输, 而半门的处理可以使密文数量减少到2 个.具体方法如下: 在加密过程中, 生成者随机选择一个比特r, 那么有ω3=ω31⊕ω32=(ω1∧r)⊕(ω1∧(r⊕ω2)).首先来看ω31=ω1∧r, 生成者已知r的取值, 可生成密文接下来考虑ω32=ω1∧(r⊕ ω2), 生成者可以公布r⊕ ω2的标签给对方 (并不泄露和b之间的关系).此时计算方可得到对应的r⊕ω2的值, 因此生成者产生两个密文当r⊕ω2为 0 时, 计算方可根据第一个密文得到当r⊕ω2为1 时, 计算方可根据第二个密文得到再与实际输入的进行异或操作即可得到由于此方案基于Free-XOR, 因此使用四个密文计算ω31和ω32再进行异或操作也可完成对与门ω3=ω1∧ω2的加密, 再利用 Naor 等人的方法[34]对每对密文中第一个密文转化为全零, 那么最终只需要传输两个密文即可计算一个与门.此方法大大提高了与门的加密速度和计算速度.

3.3 应用

混淆电路从 1986 年发展至今, 依然有大量学者为之努力和探索, 可见混淆电路强大的实用性和对密码学的重要性.2006 年, Malkhi 等人[21]根据 Yao 的方案构造了一个安全两方计算系统——Fairplay.作者对系统进行了测试, 64 比特输入的大富翁游戏需要 254 个门计算, 一次计算需要大约 4 s 时间.从Fairplay 中看到混淆电路的计算时间较短, 效率较高, 可应用在很多现实场景中.此小节将对混淆电路的应用进行综述.混淆电路起源于安全两方计算, 之后被推广到安全多方计算中去.除了在安全计算中的应用, 混淆电路还在一次性编程(one-time program)[40]、可验证计算、同态计算、函数加密甚至不可区分混淆的构造中均有应用.

安全两方计算安全两方计算分为两种——SFE (secure function evaluation) 和PFE (private function evaluation).SFE 是指Alice 和Bob 两个人均知道函数的功能, 而各自持有一部分输入, 要求在计算过程中不泄露自己持有的输入.PFE 是指Alice 和Bob 一方持有函数, 一方持有输入, 要求在计算过程中不泄露自己持有的输入或函数.由于通用函数的存在, 使得SFE 协议中构造一个通用电路UC 是两方均知道的, 再将持有函数的一方的函数描述作为通用电路的输入进行计算.因此, 对于PFE 的计算可以归结到SFE 的计算上.最早的SFE 方案是Yao 在1986 年提出的[11], 利用混淆电路和不经意传输(oblivious transfer)[41]完成交互轮数为4 且敌手是诚实但好奇的安全两方计算要求.不经意传输是指A 有一对消息想要传递给B 其中一个, 但是 B 不希望A 知道他获取的是哪一个, 而 A 希望B 仅获取一个消息.不经意传输和混淆电路构成现有安全两方计算的两大基础工具.SFE 通过混淆电路实现对计算过程的保密而通过不经意传输保证输入的隐私性.Goldwasser 等人[12]利用零知识证明系统将Yao 的方案扩展为可抵抗恶意的敌手.但是这种转化是低效率的, 因此学者们[38,42–44]对利用混淆电路构造更高效的抵抗恶意敌手安全两方计算进行探索.还有学者为了追求高效, 定义相对弱的安全两方计算协议[35,45,46].除此之外, Wang 等人[47,48]提出了带认证的混淆电路方案用以构造高效的抵抗恶意敌手的安全两方计算方案.

其他应用安全多方计算是安全两方计算的扩展,因此混淆电路在安全多方计算中也有广泛的应用[49].如: Patra 等人[50]构造的安全三方计算, 以及一系列利用混淆电路作为基础工具构造的安全多方计算方案[44,51–53].Gennaro 等人[54]将混淆电路应用在可验证计算中, 而 Gentry 等人[55]则利用混淆电路进行同态计算.而在公钥加密方案中的 KDM 安全[56,57]上, 混淆电路也能助一臂之力.除了在理论密码学中的应用之外, 混淆电路在现实生活中也有非常广泛的应用.首先混淆电路可以用在安全文本处理[58]中,其次在隐私保护拍卖[34]和隐私信用调查[59]中也使用到混淆电路.特别地, 混淆电路还可以用在隐私医疗诊断[60,61]中, 保护病人的隐私.

混淆电路由于其结构简单、快速高效的特点, 不仅在密码学理论中有广泛应用, 还能在现实社会中有效保护个人隐私.混淆电路的强大功能性和广泛的应用场景引起了学者们的关注, 越来越多的学者为了构造更加高效、更加安全、功能更加强大的混淆电路而开展研究工作.

4 混淆

混淆作为一个强大的密码学工具, 其安全有效的构造一直困扰着密码界.在通用虚拟黑盒混淆被证明不存在之后, 学者们致力于通用不可区分混淆的构造.但是, 目前通用不可区分混淆的构造依然面临着巨大问题.本节将对混淆进行详细的介绍.首先4.1 节将概述包括虚拟黑盒混淆和不可区分混淆在内混淆的语义定义和安全定义.此外还定义一些其他的混淆概念, 包括非一致输入混淆、简洁的混淆等.4.2 节简述现有的不可区分混淆的通用构造方案, 主要分为用多线性映射直接构造和用函数加密构造两种方法.最后,介绍混淆的应用.

4.1 语义定义及安全定义

混淆, 即将任意一个电路在保持其功能的前提下进行“加密”, 使得混淆后的电路 “不可读”, 达到保护电路内部信息的目的.也就是说, 混淆相当于将程序或者函数放入一个盒子中, 人们可以 “使用” 这个盒子, 但是不能“打开” 盒子.2001 年, Barak 等人[3]首次给出了具有虚拟黑盒安全混淆的形式化定义.虚拟黑盒混淆除了功能性和多项式规模扩展的要求之外, 还要求除了输出其他信息都不泄露.也就是说, 调用混淆后的程序和使用预言机的效果相同.这是一个基于断言的安全性极强的定义.

定义6(电路混淆) 一个概率多项式时间算法O可以看做是一个电路混淆, 需要满足以下三个条件:

• (功能性) 对任意一个电路C,O(C) 表示的电路与电路C的功能相同.

• (多项式效率) 对任意一个电路C, 存在多项式P且满足|O(C)|P(|C|).

• (“虚拟黑盒” 特性) 对任意一个概率多项式时间敌手A, 存在一个概率多项式时间模拟器S和一个可忽略函数α, 使得对任意一个电路C满足

但是, 在Barak[3]和 Goldwasser 的文章中都有指出, 存在一类函数无法达到虚拟黑盒混淆.也就是说, 不存在通用的虚拟黑盒混淆方案.为了构造通用的混淆方案, 学者们试图对虚拟黑盒混淆的安全要求放宽, 使得通用构造也保持具有实际意义的安全性.2007 年, Hohenberger 等人[62]提出了一个平均情况虚拟黑盒混淆的定义.而 Döttling 等人在 2011 年[63]提出使用可信硬件中存储全同态加密算法的解密密钥来构造基于硬件的程序混淆.但是, 不基于硬件假设的情况下, 直到2013 年才提出第一个通用混淆的方法.

Garg 等人[4]在2013 年提出了一个弱化的安全性定义——不可区分混淆, 并且给出了第一个通用不可区分混淆的构造方案.不可区分混淆相较虚拟黑盒混淆, 仅要求对两个功能相同, 规模相同的电路在混淆后不可区分.不可区分混淆虽然比虚拟黑盒混淆安全性较弱, 但是具有通用构造.通用不可区分混淆的出现, 使得密码界许多待解决的问题出现了新的解决方案.因此, 不可区分混淆的强大引得学者们频频回顾.

定义 7(不可区分混淆) 一个一致的概率多项式算法iO被称为一个对电路簇{Cλ} 的不可区分混淆,需要满足以下两个条件:

• 对任意安全参数λ∈N, 任意电路C∈Cλ以及任意输入x, 有

• 对任意概率多项式区分器D, 存在一个可忽略函数α, 满足要求: 对任意安全参数λ∈N, 任意电路对C0,C1∈Cλ, 且满足C0(x)=C1(x), 那么有

在构造混淆的过程中, 也构造了一些具有特殊性质的混淆.非一致输入混淆 (differing-inputs obfuscation)[64]是不可区分混淆的一种变形, 此定义不再要求两个电路功能相同, 允许两个电路存在相同输入且输出不同, 但是找到这个输入的概率可忽略.非延展混淆 (non-malleable obfuscation)[65]是指从一个函数混淆结果不可以得到关于另一个相关函数的混淆.简洁的(succinct) 混淆[66]是指混淆后的电路规模与原电路规模无关, 仅与输入长度、安全参数等相关.

除了对电路的混淆, 有学者对于其他计算模型的混淆也展开了研究, 包括对图灵机的混淆, 对 RAM的混淆等等.对于图灵机的混淆, 由于 Pippenger 等人[67]证明任意一个图灵机都可转化为一个电路, 因此对图灵机的混淆将归结到对电路的混淆.但是 Pippenger 等人的转换方法使得电路规模不仅与图灵机的规模相关, 还与图灵机的计算时间和内存占用相关, 近期的文章[68–70]着重于研究构造混淆电路规模仅与图灵机规模相关的方案, 构造常数级乘法界定的图灵机混淆方案, 即混淆后的电路规模仅与原始电路规模线性相关.

4.2 常见构造方法

现有的对于任意P/poly 电路的通用不可区分混淆的构造方法主要分为两种.一种是由Garg 等人[3]在2013 年提出的, 使用多线性映射和分支程序对NC1电路完成不可区分混淆, 再利用自举技术构造对任意多项式级别电路的混淆.另一种方法是Bitansky 等人[5]和Ananth 等人[6]分别提出的利用公钥的和私钥的函数加密构造对任意多项式级别电路的通用不可区分混淆.

第一种构造方法如图3 所示,第一步利用多线性映射等基础工具构造对NC1电路的不可区分混淆.首先, Barrington[25]提出任意一个深度为d的电路都可以转化为一系列大小为5×5、数量为 4d的矩阵相乘形式的矩阵分支程序.这种方法称为Barrington 定理.使用此方法将NC1电路转化成矩阵相乘的形式, 并对矩阵进行填充随机数和 Kilian 的随机矩阵相乘[71]的方法, 实现分支程序随机化.为了抵抗部分输入攻击, 再进行乘法绑定(multiply bunding).最后, 为了抵抗其他非线性攻击手段, 利用多线性映射或者由多线性映射构造的分级编码程序就行编码, 即完成了对任意NC1电路的不可区分混淆方案.

得到NC1电路的不可区分混淆方案后, 再利用自举技术构造对任意多项式级别电路的不可区分混淆.自举技术如图4 所示, 利用对全同态加密技术的解密算法进行 NC1级别的混淆从而完成对任意多项式电路的混淆.具体来说, 首先利用全同态加密构造两对公私钥, 并分别对任意多项式规模电路C进行加密,得到(g1,PK1,g2,PK2).再构造一个NC1级别的电路PSK2,g1,g2.此电路的功能为: 输入密文与非交互式承诺不可区分证明.如果对此承诺验证通过, 则用 SK1解密密文, 否则终止.对此电路进行 NC1级别的混淆得到最终的对任意多项式规模电路C的不可区分混淆:

图3 Garg 提出的通用混淆构造方案Figure 3 Construction of iO from Garg

图4 P/poly 电路混淆过程Figure 4 Construction of P/poly circuits’ obfuscation

另一种方法则是利用简洁的或者紧致的函数加密方案完成对任意多项式电路的通用不可区分混淆的构造.简洁的是指函数加密中加密电路的大小是poly(n,λ), 即关于输入电路的规模n和安全参数λ的多项式规模扩展.Bitansky 和 Vaikuntanathan[5]利用对称加密方案和简洁的公钥函数加密方案按混淆电路的输入比特数递归定义了对任意多项式规模电路的不可区分混淆构造.对输入长度为i的电路Ci, 首先利用两次对称加密方案加密电路Ci得到CT0和CT1, 并构造新函数:

通过将输入xi的最后一位拆分为0 和1 两种情况完成递归定义需要接下来混淆的输入长度为i−1 比特的函数.这种构造方法是递归定义的, 因此要求函数加密是简洁的.

而 Ananth 和 Jain[6]则是利用紧致的公钥函数加密方案构造对任意多项式电路的不可区分混淆方案.紧致的(compact) 是指函数加密的加密函数的运行时间必须是关于安全参数和输入长度多项式时间.第一步利用归纳的思想由c元输入的函数加密方案 (FEc) 构造c+1 元输入的函数加密方案 (FEc+1).利用一个紧致的公钥函数加密 FE 的 KeyGen 函数加密c+1 元函数f, 生成 FEc+1.skf.并构造电路G如图5 所示.若 FEc+1.Enc 函数接收到输入为 (msk,x,1) 时, 利用 FEc.KeyGen 函数加密电路G得到 FEc.skG; 若 FEc+1.Enc 函数接收到输入为 (msk,x,i) 且 2ic+1 时, 利用c元函数加密的FEc.Enc 函数加密 (x,x,1,τ,i) 即可.由此可构造任意元输入的函数加密方案, 再通过 Goldwasser 等人[72]的方法构造不可区分混淆.首先通过以输入比特长度为单位递归构造多输入函数加密方案.多输入的函数加密方案如果满足输入为n+1 元, 那么对输入为n比特的电路C混淆, 只需构造通用电路U(x1,··· ,xn,C)=C(x1,··· ,xn) 并将x1,··· ,xn和C当作多输入函数加密的n+1 元输入进行加密.

由于紧致的和简洁的函数加密方案的构造都需要用到多线性映射.其他不可区分混淆的构造方案也均需要多线性映射的帮助.因此目前通用不可区分混淆的构造依然离不开多线性映射.而多线性映射在 2003 年由 Boneh 和 Silverberg 提出[73].之后相继提出的多线性映射方案 GGH13[74]、CLT13[75]、GGH15[76]等, 不仅效率不高, 安全性还受到了不同程度的攻击[77–81].因此是否存在安全高效的多线性映射方案还不得而知[82,83].除此之外, 利用Garg 等人的方法需要的多线性映射维度为多项式级别的, 降低多线性映射维度也成为学者优化不可区分混淆构造的一个方向.2015 年, Zimmerman 提出对算术电路直接进行混淆[66], 从而避免了分支程序带来的多线性映射维度的增加, 使得多线性映射的操作数量从深度d指数级别降为多项式级别.2017 年, Lin 等人[7–10]将不可区分混淆的构造需要的多线性映射维度从多项式降到常数阶, 之后通过构造特别的伪随机生成器使得多线性映射维度降低到3.寻找高效安全的三线性映射去构造不可区分混淆称为新的问题.三线性映射甚至多线性映射的发展也直接影响到不可区分混淆的发展.因此, 越来越多的学者试图跨越从三线性映射到双线性映射的鸿沟或者抛弃之前的构造方法,利用已有的安全的密码原语, 寻求更有效可行的构造方案.

图5 电路G 的具体内容Figure 5 Details of circuit G

4.3 应用

混淆之所以受到如此广泛的关注和研究, 是因为混淆其强大的功能性.混淆不仅仅是实现了保护函数“内容” 的目的, 还解决了许多困扰密码学界多年的问题.本节将对不可区分混淆在密码学中的应用进行介绍, 包括对于函数加密方案, 多方密钥协商方案, 自线性对方案等的构造.

对通用电路构造安全的函数加密方案一直是一个未解决困难问题, 大多数的构造仅能实现内积加密函数这样简单电路的函数加密方案.但是, Garg 在提出第一个通用不可区分混淆方案的文章中就提出了利用不可区分混淆构造对于任意多项式规模电路的函数加密方案.由于函数加密要求对函数输入的保护, 此方案需要构造一个特殊函数Pf,sk1,CRS(e1,e2,π)=f(x) 用以解密加密后的输入并进行计算.此函数将计算函数f, 一个公钥加密方案的私钥 sk1以及零知识证明的参数 CRS 作为固定参数, 输入使用公钥 pk1加密输入x的密文e1和公钥pk2加密输入x的密文e2以及一个零知识证明π, 此证明表明e1和e2是合法构造的.当函数P得到输入后, 先验证证明π是否有效, 若有效则使用私钥sk1解密e1得到输入x,最后计算f(x).将函数P混淆后的程序作为函数加密函数KeyGen(msk,f) 的输出skf, 而函数加密函数 Enc(mpk,x) 则使用公钥加密x得到e1和e2并构造其零知识证明π作为输出c= (e1,e2,π).这样就保证了函数加密需要的对输入加密的安全要求.因此, 使用不可区分混淆可以构造选择性不可区分安全的函数加密方案.

非交互无需可信第三方的多方密钥协商方案也是密码学的一个难题.2014 年Boneh 等人[84]提出了使用混淆构造无需可信第三方非交互的多方密钥协商方案, 并且此方案每个成员公布的信息大小与总成员数量无关.同样地, 此构造也依赖于构造一个特殊的函数PE.此函数内置一个伪随机函数PRF, 在输入成员集合S, 成员i公布的信息 pki(一个签名方案的公钥) 以及一个签名σ之后, 首先验证签名正确性,若验证通过, 那么输出PRF(S,{pkj}) 作为协商的密钥.每个成员i除了要生成自己的签名私钥ski和公布的签名公钥 pki之外, 还需要公布对函数PE的混淆程序iO(PE).在计算协商密钥时, 成员j使用自己的私钥skj对S进行签名σi, 选取同一个iO(PE) (一般选择最小号成员生成的混淆程序) 计算得到协商密钥.这样就完成了无需可信第三方的多方密钥协商方案的构造.

此外, Boneh 在此文章中还利用类似的技术实现了支持分布式初始化的广播加密方案, 以及抗勾结的叛徒追踪系统等方案的构造.2014 年, Sahai 等人[85]利用混淆构造了可否认加密方案(deniable encryption).同年, Garg 等人[86]利用不可区分混淆构造两轮的安全多方计算模型.从这些应用可以看出, 不可区分混淆在解决一些问题的关键在于构造一个定制的函数, 将需要隐藏的信息作为函数的固定参数或者利用函数判定某些性质, 再完成计算.将此定制的函数进行混淆, 达到隐藏信息和打包的作用.

除了以上提到的应用方法之外, 2016 年, Yamakawa 等人[87]利用不可区分混淆构造自线性对, 从而构造安全的多线性映射.与其他应用不同的是, 自线性对的构造利用的是不可区分混淆中两个功能相同、规模相同的函数在混淆后不可区分的关系.利用Blum 整数N构造一个群在未知整数N分解的情况下无法求取群的阶从而无法有效计算映射函数e(gx,gy) →gcxy.因此构造一对功能相同的函数τy和其中τy←e(·,y) 而由于order 未知因此可以保护y不被泄露, 而τy则在order 未知的情况下可有效构造.借助于不可区分混淆使得不可区分, 方案即可使用iO(τy) 既保证y的安全又能够有效构造.借助于不可区分混淆, Yamakawa 等人解决了自线性对的构造问题.

可以看出, 不可区分混淆在密码学中应用广泛.借助于其不可区分性以及对函数整体的打包和保护,不可区分混淆解决了很多密码学中困扰许久的问题.

5 混淆电路与混淆的关系

从前两节的介绍中可以看到, 不可区分混淆和混淆电路在安全定义上有很多相似之处.除此之外, 两者在密码学领域都占有重要地位, 具有强大的功能, 为其他密码方案的构造提供了有效的工具.但是, 从构造中我们也发现, 两种方案的构造方式天差地别, 并且效率也相差甚远.因此, 我们在本节着重分析两个密码工具的区别与联系, 探究其中的差距到底在哪里.在 5.1 节, 我们分析传统Yao 方式的混淆电路与通用混淆即不可区分混淆的关系.接下来, 我们将在5.2 节探索可重用混淆电路与不可区分混淆的相互构造.

5.1 混淆电路与混淆的区别

在之前的介绍中, 不可区分混淆和混淆电路有着很多相似之处, 在构造的过程中, 都需要对函数进行“加密”, 使得敌手无法从加密后的函数中获取自己想要的信息.而在安全性定义上, 不可区分混淆的不可区分性和加密函数基于不可区分的安全性(包括选择性和自适应的), 都是要求对两个功能相同、规模相同的函数任意选取一个进行混淆或加密, 再让敌手进行猜测区分.不可区分混淆和混淆电路从表面上看似乎可以看作一个密码工具, 但是在现实的研究中又具有很大的差别.到底不可区分混淆和混淆电路的区别在哪里呢？

接下来我们将从设计初衷、定义、安全要求、构造难度四个方面进行对比.目的是分析不可区分混淆和传统混淆电路的根本区别, 为将来的密码研究探索新思路.

设计初衷从设计初衷上来说, 混淆最初是由程序混淆、代码混淆发展而来, 混淆电路则是从安全多方计算所衍生出的一个密码方案.混淆最初的目的是保护程序和代码内容的安全.经过近十年的演变, 不可区分混淆的主要作用也是保护电路或者函数的内部信息不被泄露.对比混淆电路, 他最初的目的是保护输入信息, 由于输入信息加密而衍生的需要在加密条件下进行电路计算.在混淆电路的三十年发展中, 其主要作用是为了保护每一位参与者的输入安全, 使参与者之间的输入互不可知.因此, 可以明显看出不可区分混淆必须加密和保护的是电路本身的安全和隐私, 而混淆电路必须加密和保护的是输入信息的安全.

定义从定义上, 不可区分混淆只有两个函数 Obf 和 Eval, 分别用来混淆程序和计算输出.而混淆电路则由三个函数组成Gb、En、Ev, 分别拥有加密电路、加密输入、计算输出的功能.函数中加密电路函数Gb 可以看作和不可区分混淆的混淆函数Obf 相似, 计算函数Ev 和不可区分混淆的计算函数Eval 相似.剩下的函数是用来加密输入.也就是说, 从定义上看到, 加密函数比不可区分函数在加密电路和保证加密电路的功能之外, 还增加了对输入的加密.

安全要求从安全要求上, 由于传统的 Yao 的构造是选择性安全的构造, 因此我们将不可区分混淆和混淆电路基于不可区分选择性安全都统一为图6 所示的游戏进行比较.不可区分混淆的不可区分性要求在此游戏后, 敌手猜测成功的优势是一个可忽略函数, 混淆电路的基于不可区分的隐私性同样的要求在此游戏后, 敌手猜测成功的优势是一个可忽略函数.

对比两个游戏的过程, 在电路的选择、计算、交互上是相同的.两个游戏均是由敌手先选择两个功能相同、规模相同的电路C0和C1, 并将这两个电路一起发送给挑战者.挑战者在收到两个电路之后, 先随机生成一个比特b∈{0,1}, 并对对应的电路Cb进行操作(不可区分混淆运行混淆函数 Obf, 混淆电路运行加密函数Gb), 在加密或者混淆完成后将结果返回给敌手.敌手收到之后可以进行电路的计算(不可区分混淆运行计算函数 Eval, 加密函数运行计算函数Ev), 并猜测挑战者选取的比特b.如果敌手不能以超过的概率猜测正确, 则说明此方案是安全的.

图6 不可区分混淆和加密电路的安全定义Figure 6 Security definition of iO and garbled circuits

但是可以看到在两个游戏中对电路输入的操作是不同的.不可区分混淆的输入是在挑战者返回混淆后的程序之后, 由敌手任意次选择输入并带入电路进行计算.而 Yao 的混淆电路的输入则是要求敌手必须在发送两个电路C0和C1之前选择好并发送给挑战者, 由挑战者统一进行加密返回给敌手.在此方面上, 混淆更接近适应性安全的混淆电路.此外, 敌手只能使用发送给挑战者的输入对加密后的电路进行计算, 不能再选择新的输入.也就是说, 不可区分混淆完成的混淆程序在敌手任意多次选择输入并计算之后,仍然无法区分.混淆电路加密后的电路则是限制在一次输入计算过程中不可区.如果对加密后的电路进行多次不同输入的计算, 我们可以通过局部输入攻击(partial evaluation attacks)[4]进行区分.

构造难度从构造难度上, 不可区分混淆需要多线性映射或者分级编码系统构造, 混淆电路需要双密钥密码进行构造.2017 年, Halevi 等人[18]实现了基于 GGH15 多线性映射的不可区分混淆方案.在文章中, 分支函数长度为20 时, 混淆时间已经超过四万秒.虽然在之后Lin 等人[7–10]的工作使得不可区分混淆方案可以基于三线性映射构造, 但是一方面还没有相关实现展示其具体效率, 另一方面没有突破多线性映射的禁锢.由于多线性映射至今无法确定是否存在安全的构造, 现有的构造都收到不同程度的攻击并且效率极低, 因此不可区分混淆的实现效率也很低.而在 2004 年 Dahlia 等人[88]基于 Yao 的混淆电路实现的安全多方计算平台Fairplay 上, 64 比特输入、电路规模为256 的大富翁游戏仅需要4 秒时间.在使用Free-XOR、半门、row-reduction 的操作后, 混淆电路的效率进一步得到提升.可以看到混淆电路比起不可区分混淆来看更加高效.

综上所述, 我们可以看到不可区分混淆和混淆电路两个概念还是存在相当大的区别.不可区分混淆构造要求更高, 效率较低, 但是对电路的安全性保护更加全面.混淆电路的构造要求低, 效率较高, 对输入也有不可区分混淆没有的加密机制, 但是对电路本身的安全性保护较低, 在实际使用过程中受限, 混淆电路不可重复使用.

5.2 混淆电路与混淆的联系

本节将探讨混淆电路与混淆之间的联系, 试图通过混淆构造可重用混淆电路, 并探索构造混淆所需的混淆电路的安全等级.需要说明的是, 我们期望构造的混淆电路和混淆均为通用构造, 特殊函数的构造暂不考虑.因此, 我们探索的是混淆电路与通用混淆即不可区分混淆之间的关系.通过相互构造, 期望发现其相互关系, 为混淆电路和混淆的发展提供思路.

由5.1 节的讨论可知混淆电路与混淆最大的障碍在于可重用性, 也就是说对于同一个混淆电路, 可以实现多组不同输入的计算并保证其安全性.Goldwasser 等人[16]给出第一个可重用混淆电路的构造.可重用混淆电路是在原有的混淆电路方案中加入可重用, 即在加密函数En 中, 要求可以选择不同的输入进行加密.同时在使用同一个加密后的电路F时不泄露电路和输入信息.其形式化定义如下:

定义 8(可重用混淆电路) 一个混淆电路方案uGC=(uGC.Gb,uGC.En,uGC.Ev) 被称为可重用混淆电路, 那么:

• uGC.Gb(1λ,C)→(F,sk).此算法用于对输入的电路C, 在安全参数λ下加密得到加密后的电路F以及一个密钥sk.

• uGC.En(sk,x) →X.此算法利用密钥 sk 将电路C的一个输入x进行加密, 得到X.对于同一个C加密后得到F和sk, 可以利用 sk 构造多组输入x的加密输入X, 称为可重用的.

• uGC.Ev(F,X) →Y.此算法对加密后的电路F以及输入X进行计算, 得到Y, 且Y的值等于C(x).

Goldwasser 等人[16]使用全同态加密和基于属性的加密方案构造了可重用混淆电路.文章中使用的基于属性的加密方案 ABE = (ABE.Setup,ABE.KeyGen,ABE.Enc,ABE.Dec) 与一般的 ABE 方案不同.普通的 ABE 方案, 在解密过程断言为真则解密, 断言为假则停机.而 Goldwasser 所使用的 ABE是加密两个消息m0和m1, 若断言为真则解密m1, 反之则解密m0.使用这种 ABE 方案和 Yao 的混淆电路方案 GC 结合, 即可解密 Yao 输入密钥对的其中一个.而断言则是使用全同态加密方案 FHE =(FHE.KeyGen,FHE.Enc,FHE.Eval,FHE.Dec) 的计算函数判定.为保证函数安全性, 额外选取一个对称加密方案Sym=(Sym.KeyGen,Sym.Enc,Sym.Dec) 将函数加密即可.具体构造方法如算法1 所示.

若我们希望找到通用混淆和可重用混淆电路的关系, 就需要对现有的可重用混淆电路进行改造.首先,目前存在的通用混淆方案为不可区分混淆方案.不可区分混淆在两个功能相同规模相同的电路对C0,C1满足:因此, 我们需要定义基于不可区分安全性的可重用混淆电路.可重用混淆电路的基于不可区分的自适应安全定义在一个游戏uAdaInd.游戏过程为: 敌手任意的选择一对规模相同、功能相同的电路C0,C1, 将此电路对发送给挑战者.挑战者随机选取b∈{0,1},计算 uGC.Gb(1λ,Cb) →(Fb,sk), 得到后将Fb发送给敌手.敌手根据Fb, 任意的循环以下步骤: 选择一个输入x, 询问挑战者, 挑战者计算 uGC.En(sk,x) →X并返回X给敌手, 计算 uGC.Ev(Fb,X) →Y.最后敌手猜测则称此混淆电路方案满足基于不可区分的自适应安全.

有了可重用混淆电路的定义和构造, 我们尝试使用不可区分混淆构造满足可重用性的混淆电路方案.假设存在一个不可区分混淆iO= (iO.obf,iO.Eval), 以及一个对称加密方案 Sym =(Sym.KeyGen,Sym.Enc,Sym.Dec), 构造一个可重用混淆电路方案uGC:

• uGC.Gb(1λ,C): 计算 sk←Sym.KeyGen(1λ).构造电路Csk,C(X).电路Csk,C(X) 首先计算x←Sym.Dec(sk,X),然后计算并返回C(x).将电路Csk,C(X)混淆得到Γ←iO.obf(1λ,Csk,C).返回 (Γ,sk).

• uGC.En(sk,x): 计算X←Sym.Enc(sk,x).返回X.

• uGC.Ev(Γ,X): 计算Y←iO.Eval(Γ,X).返回Y.

如此构造的可重用混淆电路方案是满足基于不可区分性的自适应性安全的.即可构造由基于不可区分性自适应安全的可重用混淆电路到不可区分混淆的规约.对任意一个不可区分混淆的挑战者, 敌手首先选择两个功能相同、规模相同的电路C0和C1, 计算 sk←Sym.KeyGen(1λ).接下来, 利用电路C0,C1以及sk 构造两个新的功能相同且规模相同的电路Csk,C0(X),Csk,C1(X).敌手将Csk,C0(X),Csk,C1(X)作为挑战电路对发送给不可区分混淆的挑战者得到一个回答iO(Csk,Cb(X)).此回答也是对于基于不可区分性的自适应安全的可重用混淆电路方案的挑战密文.若对此密文可区分那么对不可区分混淆的密文也可区分, 即此可重用混淆电路方案是满足基于不可区分性的自适应性安全的.

接下来, 我们将探索使用混淆电路构造不可区分混淆的方法.从 3.1 节可以看到, 传统的混淆电路是选择性安全的, 且是 “一次性” 的.因此, 学者们构造了可重用的混淆电路.那么, 可重用混淆电路与不可区分混淆又是否相等呢？

首先回顾一下Goldwasser 等人[16]提出的可重用混淆电路的安全定义.可重用混淆电路的安全定义是基于模拟的, 称为可重用的输入和电路隐私性(input and circuit privacy with reusability).其具体定义如下.

定义 9(可重用的输入和电路隐私性) 令uGC 是电路簇{Cn}n∈N的可重用混淆电路方案.对于一对概率多项式时间算法A= (A1,A2) 以及一个概率多项式时间模拟器S= (S1,S2) 来说, 考虑图7 的两个游戏:

图7 可重用输入和电路隐私性游戏Figure 7 Game of input and circuit privacy with reusability

其中O(·,C)[[stateS]]是一个运行S2的预言机, 输入x,C(x), 1|x|以及S的状态, 返回S2的输出结果.如果在这两个游戏中,两个分布是计算不可区分的, 那么称此可重用混淆电路方案满足可重用的输入和电路隐私性.

从安全定义来看, 可重用混淆电路的安全性是基于模拟的自适应安全.类比混淆来说, 相当于虚拟黑盒混淆的安全定义.但是由于其加密函数 En 是使用私钥sk 进行计算的, 和不需要限制使用明文进行计算的混淆不同.而Goldwasser 等人的文章中[17]有这样一段话: “加密输入需要私钥是必须的.如果可以公开加密, 那么敌手的能力将和传统的混淆相同.而这种混淆已经被证明不存在通用构造.” 这段话从侧面印证了如果在此安全定义下构造不需要私钥的可重用混淆电路方案, 就相当于完成了通用虚拟黑盒混淆的构造.

由于基于模拟的自适应安全也可满足此定义下的基于不可区分的自适应安全, 所以现有的基于模拟的自适应安全的可重用混淆电路均满足基于不可区分的自适应安全.但是, 是否存在不需要私钥的可重用混淆电路方案暂时是一个未解之谜.即敌手在获取到Fb后可自行计算函数, 无需再向挑战者获取输入x的加密密文X.

假设存在不需要私钥的可重用混淆电路方案, 那么构造不可区分混淆将是简单的.假设存在一个满足基于不可区分自适应性安全的不需要私钥的混淆电路方案uGC.构造一个不可区分混淆方案如下:

•iO.obf(1λ,C): 计算 uGC.Gb(1λ,C)→ (F,pk), 返回O=(F,pk).

•iO.Eval(x,O): 分离O=(F,pk), 计算 uGC.En(pk,x)→X, uGC.Ev(F,X)→Y, 返回Y.

综上可知, 利用不可区分混淆构造基于不可区分的自适应安全的可重用混淆电路方案是简单的, 而利用基于不可区分的自适应安全的可重用混淆电路方案构造不可区分混淆则是未知的.通过探索可知, 构造不可区分混淆相当于构造一个不需要私钥的基于不可区分自适应性安全的混淆电路方案.因此, 利用混淆电路方案构造混淆也许是一个新的发展方向.

6 总结

混淆电路与混淆作为对函数本身的保护是密码研究领域两个非常重要的工具.混淆电路在安全多方计算、同态计算、可验证计算等方面均有应用, 而混淆也在可否认加密、广播加密、自线性映射等方面均有应用.他们不仅在密码学理论研究中起到重要作用, 在现实生活中也有广泛的应用空间.由于混淆电路和混淆均是对电路的保护, 将来可能应用到人类社会的创作、发明、作品等技术保护.但是, 混淆电路和混淆都还存在很多问题值得被探索和研究.

首先, 混淆电路特别是可重用混淆电路方案的有效实现暂时缺失.可重用混淆电路相较于不可重用的方案来说大大提高了构造的复杂度, 在现实应用过程中也降低了构造速率.但是现有的相关可重用混淆电路的研究依然很少, 仅仅停留在理论分析上.目前可重用混淆电路在摆脱了同态加密的重负后, 使用的方案仅基于 LWE、随机线性码以及对称加密方案.但是安全性也大大降低.可重用混淆电路的效率以及安全参数的选择依然是一个待探索的领域.此外, 是否存在更加有效的可重用混淆电路的构造方案或优化方案也是一个待探索的方向.又或者, 是否存在效率接近不可重用的混淆电路而重用次数有限次的混淆电路方案？关于可重用混淆电路, 依然等待着学者们的探索与发现.

其次, 混淆的有效构造依然困扰着密码界.传统的基于多线性映射的混淆由于多线性映射的不安全性导致构造的混淆方案不安全, 是否存在安全有效的多线性映射方案依然是迷.而现有的GGH13、CTL13以及 GGH15 均被攻破, 构造多线性映射的问题停滞不前.对于使用较为成熟的双线性对方案构造混淆,近两年成为学者们努力的目标, 现有的研究显示有完成的可能性.但是这种构造方式的效率和参数也将成为下一个关心的问题, 以及这些构造是否存在可攻击的漏洞也未可知.对于不可区分混淆的构造和实现依然值得深入研究.

最后, 关于混淆电路和混淆之间的关系, 通过本文的探索, 问题纠结在于是否存在不需要私钥的基于不可区分的自适应性安全可重用混淆电路方案.是否可以通过现有的基于模拟的可重用混淆电路方案进行修改, 得到基于不可区分的方案并解放私钥.又或者对现有的可重用混淆电路作为基础, 结合密码学其他工具解放私钥是否可以完成混淆的构造？而这种构造方式相较于现有的混淆构造是否能够提高效率？此外, 关于可重用混淆电路的构造, 可否利用对具体函数的虚拟黑盒混淆进行构造.由于现有的对具体函数的混淆效率相较通用混淆较高, 因此尝试使用对具体函数的混淆来构造可重用混淆电路或许可行.

虽然混淆电路和混淆还有很长的路要走, 但是这两个密码方案已经显示其强大的功能.相信经过无数学者的努力和奋斗, 终有一天我们会突破这些难题, 让混淆电路和混淆为人类社会安全添砖加瓦.