基于单密钥函数加密的具体高效可否认加密方案*

2022-05-09杨糠,张江

密码学报 2022年2期

杨糠, 张江

密码科学技术国家重点实验室, 北京 100878

1 引言

Canetti 等人[1]引入了可否认加密(deniable encryption, DE) 的概念, 使得即使发送者/接收者在加密通信之后, 仍然能产生“否认” 的(但与真实值不可区分的) 随机数/私钥, 打开密文为另一个不同的明文. 可否认加密方案可从非交互的概念自然推广到交互的概念(在交互的情况, 可否认加密也称为可否认交互通信). 可否认加密加强了传统的安全通信, 使得即使发送者/接收者在之后被强迫泄露明文、随机数或私钥, 仍然能够保证通信消息的机密性. 可否认加密的一个直接应用是抑制投票贿选, 其可否认性保证: 即使恶意实体贿赂了投票人, 也无法确认投票是否满足指定要求. 可否认加密满足非承诺性(non-committing)[2], 从而可应用到自适应的安全多方计算(secure multi-party computation, MPC) 协议中[3]. 此外, 可否认加密保证了在选择打开攻击(seletive opening attacks) 下的安全性[4,5], 也蕴含了不可强制安全多方计算(incoercible MPC) 的存在性[6,7].

Canetti 等人[1]提出了两类可否认性. 第一种是完全可否认性, 即发送者和接收者运行一套预先指定的密钥生成和加解密算法, 过后可否认密文为其他的明文. 第二种是双方案可否认性(也称为多分布可否认性), 允许有两套密钥生成和加解密算法, 其中一套为可否认算法, 另一套为正常算法, 使得在可否认算法下加密的一个明文能被否认为在正常算法下加密的另一个明文. 容易看到完全可否认性是比双方案可否认性更强的安全概念.

我们自然期望设计满足完全可否认性的DE 方案. 然而, 设计该类加密方案是一个长期的公开问题.直到2014 年, Sahai 和Waters[8]才解决该公开问题, 基于不可区分混淆(indistinguishability obfuscation, iO) 设计了发送者完全可否认的公钥可否认加密方案. Bendlin 等人[9]在2011 年给出了关于接收者完全可否认性的不可能结果: 不存在满足该类可否认性的可否认公钥加密方案, 即任何接收者完全可否认的方案要求交互通信. 然而, 设计接收者完全可否认的交互方案一直保持是公开问题, 直到2020 年. 具体地, Canetti 等人[10]给出了一个突破性的结果, 基于亚指数安全的iO 设计了双方完全可否认的可否认交互加密方案, 不仅允许发送者和接收者可以否认密文, 而且当否认的明文不同时保证无法区分谁在欺骗.尽管完全可否认DE 方案的公开问题已得到初步解决, 然而已知的构造都依赖于iO, 即仅从理论上给出了完全可否认方案的解决方法, 完全没有考虑其效率问题. 本文集中于设计具体高效的可否认加密方案, 从而考虑更弱的可否认性——双方案可否认性.

在1997 年, Canetti 等人[1]基于半透明集合(translucent sets) 设计了发送者可否认的双方案可否认公钥加密方案, 其中半透明集合能够通过陷门置换和Hard-core 谓词获得. 如果用RSA 陷门置换实例化该可否认加密方案, 那么对于128 比特安全等级, 该方案每加密1 个比特需要800 字节的通信和256次RSA 加密运算. 从而, 该可否认加密方案的效率仍然偏低. 在2011 年, O’Neill 等人[11]一般化该设计思想, 从双半透明集合(bitranslucent sets) 设计了双方可否认的双方案可否认公钥加密方案, 而且基于LWE 困难假设[12]提出了双半透明集合的实例. 他们的方案获得了更强的可否认性(即允许发送者和接收者都可以否认密文), 但他们方案的效率比Canetti 等人给出的方案更低. 此外, 双方案可否认的属性基加密方案[13]和函数加密方案[14]也被相继提出. 然而, 这些方案仅仅扩展了可否认加密方案的功能性,并没有改进该类加密方案的效率.

与发送者可否认的DE 方案比较, 接收者可否认的DE 方案可能更被期望获得, 也更难设计[15]. 注意发送者可否认性同样是有用的, 特别是当数据擦除在技术上或法律上不可行的时候. 根据Nielsen 在2002年给出的不可能结果[16], 接收者可否认DE 方案的私钥至少需要跟明文一样长. 为了解决该问题, 目前有两种方法. 第一种方法是Goldwasser 等人[15]提出的可否认编辑(deniable edit), 即限制否认后的明文为m′= Edit(m,e), 其中m为原始的明文和e为编辑描述. 从而, 私钥长度与编辑描述长度|e| 成线性关系, 独立于明文的长度|m|. 在许多的应用中, 我们只需要否认明文m中的部分内容, 而不是全部内容,使得可否认编辑已经足够满足这些应用的需求. 如果定义e=m ⊕m′和Edit(m,e) =m ⊕e=m′, 那么可否认编辑方案直接变为标准的可否认加密方案(尽管失去了效率优势). 因此, 可否认编辑可以看作是可否认加密的一般化. 第二种方法是预先计划的可否认加密(plan-ahead deniable encryption)[1,11], 即发送者/接收者在明文加密之前预先计划一定数量的否认明文, 过后只能将密文否认为这些预先计划的明文. 虽然预先计划可否认加密方案在否认性方面存在一定的限制, 但是该方法允许加密任意多项式长度的明文, 从而支持大型文件的加密. 尽管这两种方法从不同角度限制了否认的能力, 但是他们提供了设计具体高效可否认加密方案的有效途径.

可否认加密可分为公钥可否认加密(发送者仅知道公钥, 接收者生成公私钥) 和私钥可否认加密(发送者和接收者共享相同的密钥). 一般而言, 私钥可否认加密比公钥可否认加密更加高效. 然而, 上述大部分不可能结果不仅适用于公钥可否认加密, 也同样适用于私钥可否认加密, 使得私钥可否认加密并没有比公钥可否认加密更容易设计. 目前, 所有已知的可否认加密方案都是从理论上设计, 没有考虑其具体效率.本文以设计具体高效的可否认加密方案为主要目标, 致力于设计满足双方案可否认性的私钥可否认加密方案(除非特别说明, 下文提及的可否认性均为双方案可否认性).

1.1 本文贡献

本文首先提出了新的私钥可否认编辑方案, 满足选择明文攻击(CPA) 安全性和接收者可否认性, 大幅度降低了Goldwasser 等人[15]方案的密文长度、否认密钥长度(具体的效率比较见1.2 节). 特别地, 提出的私钥可否认编辑方案降低密文长度超过2|Cedit|κ+3ℓκ比特, 其中|Cedit| 是关于编辑函数Edit 布尔电路表示的AND 门数量、ℓ=|e| 表示编辑描述长度和κ是安全参数. 而且, 该方案将否认密钥长度从2(ℓ+κ)κ比特降低到仅仅κ比特, 达到了最优. 基于Canetti 等人给出的转换技术[1], 再结合上“一次一密” 中XOR 操作允许将对随机数的编辑传递到对明文的编辑, 本文也将提出的满足接收者可否认性的私钥可否认编辑方案转换为发送者可否认的私钥可否认编辑方案.

与Goldwasser 等人[15]给出的私钥可否认编辑方案类似, 本文提出的方案基于单密钥私钥函数加密(single-key secret-key functional encryption, SK2FE) 方案设计. 本文利用Free-XOR 技术[17]和半门乱码电路技术[18], 再结合上提出的伪随机密钥、标签、密文产生技术, 设计了新的SK2FE 方案, 满足特殊加密和解密性质(其中该性质是设计私钥可否认编辑方案的特殊安全需求). 与Goldwasser 等人[15]给出的构造相比, 本文提出的SK2FE 方案减少了一半以上的密文长度, 也将主密钥长度从O(nκ) 降低到O(κ) 比特, 同时给出了更加简单的特殊解密算法, 其中n表示一个输入的长度. 然后, 基于新的SK2FE方案, 本文设计了高效的私钥可否认编辑方案.

基于提出的私钥可否认编辑方案, 本文也设计了新的预先计划私钥接收者可否认加密方案, 支持预先计划t个否认的明文. 该方案适合于加密较长的明文, 当t=O(1) 能获得O(1) 密文率(密文长度/明文长度的比率), 比提出的可否认编辑方案有显著更短的密文. 特别地, 通过混合加密技术, 我们能用可否认编辑方案加密O(κ) 比特的密钥, 然后用私钥加密方案(即对称加密方案) 加密任意多项式长度的明文.

1.2 可否认加密方案效率与比较

表1 比较了本文的私钥可否认编辑方案与Goldwasser 等人[15]方案的效率, 其中两个方案都满足CPA 安全性和接收者可否认性. Goldwasser 等人主要从理论上设计私钥可否认编辑方案, 将接收者可否认编辑方案的存在性归约到单向函数的存在性. 我们应用点置换技术[19,20]等优化方法到Goldwasser 等人的构造中, 改进他们方案的计算效率, 然后再与他们的构造进行效率比较. 注意点置换技术的使用没有引入额外的困难假设, 保证了他们的私钥可否认编辑方案[15]仍然基于单向函数.

计算效率的比较仅考虑了否认模型下加密算法和解密算法的效率, 忽略了正常模式下相应算法的效率比较. 这是因为发送者和接收者主要在否认模式下通信, 很少在正常模式下通信. 对于无需否认的加密通信而言, 发送者和接收者可以利用标准的私钥加密方案进行通信.

在表1 中的符号说明如下:

·n为明文m的长度,ℓ=|e| 为编辑描述e的长度以及κ为安全参数.

· 布尔电路CEdit用于计算以下函数FEdit:{0,1}n+ℓ+κ×{0,1}ℓ+κ →{0,1}n:

·|CEdit| 表示布尔电路CEdit中AND 门的数量;|CSpecial| 表示电路CSpecial中AND 门和XOR 门的数量, 其中注意Goldwasser 等人[15]没有考虑Free-XOR 优化技术[17].

·tperm表示计算单个随机置换π:{0,1}κ →{0,1}κ的运行时间, 其中随机置换可用密钥固定的分组密码实现(比如: AES);tprf表示计算单个伪随机函数PRF:{0,1}κ×{0,1}κ →{0,1}κ的运行时间, 其中伪随机函数可用分组密码实现. 如果用密钥固定的AES 实例化随机置换以及用带密钥编排的AES 实例化伪随机函数, 那么根据Guo 等人[21]的实验结果,tprf≈2tperm.

从表1 可以看到, 本文私钥可否认编辑方案的密文长度比Goldwasser 等人方案[15]减少了超过2|CEdit|κ+3ℓκ比特. 本文的方案也减少了否认密钥长度2(ℓ+κ) 倍, 使得对于较长的编辑描述e, 能节省较多的存储空间. 当两个方案都转化为标准的私钥可否认加密方案时, 本文提出的方案将提供更多的通信和存储优势, 即减少密文长度2|CEdit|κ+3nκ比特和减少否认密钥长度2nκ比特. 对于私钥的长度,本文的私钥可否认编辑方案与Goldwasser 等人方案[15]相同, 均与编辑描述的长度成线性关系. 与否认密钥的长度比较, 私钥长度是更次要的效率度量. 这是因为发送者和接收者无需存储私钥, 在少数需要的时候用否认密钥计算得到私钥即可.

计算效率的比较假设用AES 实现随机置换或伪随机函数, 从而有tprf≈2tperm. 我们主要考虑否认模式下加密算法、解密算法和否认算法的计算效率比较. 当|CSpecial|＞2(n-ℓ) 时, 本文的私钥可否认编辑方案降低解密算法运行时间约(|CSpecial|-2n+2ℓ)tperm. 对于否认算法, 当|CSpecial|＞2(n+ℓ) 时, 本文的方案降低运行时间约为(|CSpecial|-2n-2ℓ)tperm. 对于加密算法的计算效率, 本文的私钥可否认编辑方案与Goldwasser 等人的方案效率相当. 在安全性方面, 本文的私钥可否认编辑方案需要基于循环相关强健Hash 函数(circular correlated robust hash function, circular CRHF) 假设[22], 比Goldwasser 等人方案基于的单向函数假设更强.1如果我们将Free-XOR 技术[17] 和半门乱码电路技术[18] 应用于优化Goldwasser 等人[15] 的可否认编辑方案, 那么Goldwasser 等人方案的安全性将依赖于循环CRHF 假设, 与本文的方案相同. 即便如此, 本文提出的方案仍然显著减少了密文的长度, 仍然减少否认密钥长度2(ℓ+κ) 倍.

2 预备知识

2.1 符号

本文用κ表示(计算) 安全参数. 对于n ∈N, 符号[n] 和[0,n] 分别表示集合{1,2,··· ,n}和{0,1,··· ,n}. 对于两个字符串a,b,a‖b表示它们的级联. 用|x| 表示字符串x的长度. 对于字符串x ∈{0,1}*,xi表示x的第i个比特;以及lsb(x)表示x的最低比特. 符号x ←S表示从有限集合S中均匀随机采样x;x ←D表示根据分布D采样x. 缩写PPT 表示概率多项式时间(probabilistic polynomial time). 本文用negl(·) 表示一个未指定的可忽略函数, 即对于任意的常数c ≥0, negl(κ) =o(κ-c). 对于(随机) 算法A,y ←A(x) 表示关于输入x运行算法A和获得输出y. 用符号y ←A(x;r) 指定算法A所使用的随机数r. 为了方便表示, 用{xw}w∈I表示(xw1,xw2,··· ,xwn), 其中wi ∈I对于i ∈[n] 和n是集合I的大小.

对于布尔电路C, 我们可以对电路的每条线进行编号, 使得每条线都有唯一标识的索引(假设从1 开始编号). 电路C由一系列门组成, 每个门有(α,β,γ,T) 形式, 其中α,β是门输入线索引,γ是门输出线索引和T ∈{⊕,∧}是门的类型. 本文用I表示电路输入线索引的集合,O表示电路输出线索引的集合以及W表示AND 门输出线索引的集合. 当显示考虑两个输入x,y时, 本文用I1和I2分别表示x和y对应的电路输入线索引集合, 满足I=I1∪I2.

2.2 单密钥私钥函数加密

下面回顾Goldwasser 等人[15]给出的单密钥私钥函数加密(SK2FE) 定义. 特别地, SK2FE 仅保证了弱的安全概念: (1) 敌手至多获得单个私钥; (2) 敌手必须在获得挑战密文之前选择私钥.

定义1 (SK2FE) 针对函数f:{0,1}n1×{0,1}n2→{0,1}n3(其中n1,n2,n3是安全参数κ的函数), 单密钥私钥函数加密方案FE=(Setup,Gen,Enc,Dec) 由以下多项式时间算法组成:

· msk←Setup(1κ): 产生一个主私钥msk.

· sky ←Gen(msk,y): 输入主私钥msk 和y ∈{0,1}n2, 产生一个函数私钥sky.

·c ←Enc(msk,x): 输入主私钥msk 和x ∈{0,1}n1, 输出密文c.

·f(x,y)←Dec(sky,c): 输入函数私钥sky和密文c, 输出消息f(x,y).

正确性. 对于每个安全参数κ, 消息x ∈{0,1}n1和y ∈{0,1}n2:

单密钥安全性. 定义在PPT 敌手A和挑战者之间由比特b ∈{0,1}参数化的单密钥私钥函数加密安全性实验FEGamebA(κ) 如下:

(1) 选取msk←Setup(1κ) 和令O(·)=Enc(msk,·) 为加密预言机(oracle).

(3) 敌手AO(·)(sky) 询问加密预言机, 然后输出一个比特b′, 被作为该实验的输出.

我们称一个单密钥私钥函数加密方案FE=(Setup,Gen,Enc,Dec,SEnc,SDec) 具有特殊加密功能, 如果对于任意PPT 敌手A以下成立:

定义3 我们称单密钥私钥函数加密方案FE = (Setup,Gen,Enc,Dec,SEnc,SDec) 具有特殊解密功能, 如果对于每个安全参数κ和消息x ∈{0,1}n1:

2.3 伪随机函数和私钥加密方案

下面回顾伪随机函数的标准定义以及私钥加密方案(也称为对称加密方案) 的CPA 安全性. 此外, 我们也要求私钥加密方案满足一次伪随机性, 即要求挑战密文与密文空间中的随机值不可区分.

定义4 (伪随机函数) 令PRF :{0,1}κ×{0,1}κ →{0,1}κ是有效的密钥函数. 我们称PRF 是一个伪随机函数, 如果对于任意PPT 区分器A, 满足以下成立:

其中sk←{0,1}κ被均匀随机选取和fκ是从{0,1}κ映射到{0,1}κ的函数集合中均匀随机选取.

定义5 (私钥加密方案) 一个私钥加密方案SE=(Gen,Enc,Dec) 由以下多项式时间算法组成:

· sk←Gen(1κ): 产生一个私钥sk.

·c ←Enc(sk,m): 输入私钥sk 和明文m ∈{0,1}n, 输出密文c.

3 高效的单密钥私钥函数加密方案

本节首先给出乱码电路(garbled circuits) 的定义并描述相应的半门构造, 然后提出新的单密钥私钥函数加密方案, 最后证明该方案的安全性.

3.1 乱码电路方案及其半门构造

下面回顾Bellare 等人[23]给出的乱码电路定义. 为了便于描述本文提出的SK2FE 构造, 本文扩展他们的定义, 使得显示考虑两个不同的输入x和y. 本文给出的定义保证输入x的机密性, 即使允许敌手决定输入y对应的编码(也称为标签). 该扩展的定义使得我们能在不依赖于随机预言机(random oracle,RO) 的假设下设计高效的单密钥私钥函数加密方案.

定义6 (乱码电路方案) 对于任意布尔电路C:{0,1}n1×{0,1}n2→{0,1}n3, 乱码电路方案GC =(Garble,Encode,Eval,Decode) 定义如下:

· (ˆC,e,d)←Garble(1κ,C): 输入布尔电路C, 输出乱码电路ˆC和解码信息d.

· (X,Y)←Encode(e,x,y): 输入编码信息e以及x ∈{0,1}n1、y ∈{0,1}n2, 输出x对应的编码X以及y对应的编码Y.

·Z ←Eval(ˆC,(X,Y)): 输入乱码电路ˆC和电路输入线编码(X,Y), 输出电路输出线的编码Z.

·z ←Decode(d,Z): 输入解码信息d和电路输出线编码Z, 输出z ∈{0,1}n3.

正确性. 对于每个安全参数κ ∈N、布尔电路C:{0,1}n1×{0,1}n2→{0,1}n3以及输入x ∈{0,1}n1,y ∈{0,1}n2, 以下成立:

图1 半门乱码电路方案Figure 1 Half-gates garbling scheme

从经典的乱码电路半门构造, 我们容易保证方案1 的正确性. 根据文献[18] 给出的安全证明, 我们能在循环相关强健性假设[21,22]下保证方案1 满足不可区分安全性. 注意输入x和y的编码是独立的,从而即使敌手能选择y的编码Y, 但是也不能区分X0与X1. 最近, Rosulek 和Roy[24]突破了半门构造的下界, 提出了通信更低的乱码电路方案, 使得每个AND 门仅需1.5κ+5 比特通信(其中半门构造需要每个AND 门2κ比特通信), 当要求比半门构造50% 更多的CRHF 函数计算. 我们也能扩展Rosulek 和Roy的乱码电路构造从单个输入到两个不同的输入, 然后应用到本文的单密钥私钥函数加密方案(见3.2 节)中, 以获得更短的密文长度. 本文留具体的构造细节作为未来的研究工作.

3.2 单密钥私钥函数加密构造

3.3 安全性证明

正常解密算法根据比特yw(w ∈I2) 的取值恢复标签集合Y, 再结合密文中的X执行乱码电路运算,最后用解码信息d解码得到函数输出f(x,y). 从而, 根据正常加解密算法的描述, 正常解密算法的正确性容易获得. 对于特殊解密算法, 该算法执行与正常加密算法相同的运算得到L0w(w ∈I1), 然后与X中的标签Lxww比对得到输入x的每个比特. 因此, 根据正常加密算法和特殊解密算法的描述, 特殊解密算法的正确性容易保证. 下面, 本文证明私钥函数加密方案FE 的单密钥安全性和特殊加密安全性.

定理1 如果GC 是满足不可区分性的乱码电路方案以及PRF 是安全的伪随机函数, 那么如图2 所示的私钥函数加密方案FE 满足单密钥安全性和特殊加密安全性. 特别地, 以下关系成立:

图2 单密钥私钥函数加密构造Figure 2 Construction of single-key secret-key functional-encryption

证明: 本文首先证明方案FE 满足单密钥安全性. 该证明通过一系列游戏G0,G1,··· ,G4执行, 其中用Pr[Gi] 表示敌手在Gi中输出1 的概率. 本文在图3 中描述了这些游戏, 其中方框标出的内容表示该游戏相较于上一个游戏所做的改变. 本文将证明任意两个连续的游戏是不可区分的.

图3 关于我们私钥函数加密方案的单密钥安全性的系列游戏Figure 3 Sequence of games for single-key security of proposed secret-key functional-encryption scheme

游戏G1: 该游戏与G0相同, 除了如果一旦发现O(·)=FE.Enc(msk,·) 产生的所有密文和挑战密文c*中存在相同的随机数r, 那么游戏直接中止.

根据以上证明, 我们容易证明私钥函数加密方案FE 满足特殊加密安全性. 特别地, 重用游戏G1到G5,我们能将加密预言机从O(·)=Enc(msk,·) 逐步跳转到O(·)=Enc(sky,·). 从而, 容易获得以下的界:

以上的安全界使得本文完成该证明.

4 高效的私钥可否认编辑方案

基于提出的单密钥私钥函数加密方案, 本节描述高效的私钥可否认编辑方案, 满足CPA 安全性和接收者可否认性. 此外, 本文也转化该接收者可否认编辑方案为发送者可否认编辑方案, 但需要额外一轮的交互. 在此之前, 本文首先回顾接收者私钥可否认编辑方案的定义.

4.1 私钥可否认编辑定义

Goldwasser 等人[15]给出了满足双方案接收者可否认性的编辑方案定义. 本文扩展他们的定义从支持否认私钥到更强的否认密钥生成随机数如下:

定义7 (私钥可否认编辑) 令消息长度n和编辑描述长度ℓ均为安全参数κ的多项式函数. 令Edit:{0,1}n×{0,1}ℓ →{0,1}n为多项式时间的编辑函数. 一个私钥可否认编辑方案DE = (Gen,Enc,Dec,DenGen,DenEnc,DenDec,Deny) 由以下多项式时间算法组成:

· (Gen,Enc,Dec) 满足定义5 中描述的私钥加密方案定义.

· dk←DenGen(1κ): 否认密钥生成算法产生一个否认密钥dk.

·c ←DenEnc(dk,m): 否认加密算法输入否认密钥dk 和明文m ∈{0,1}n, 输出可否认密文c.

·m ←DenDec(dk,c): 否认解密算法输入密钥dk 和密文c, 输出明文m.

如果定义编辑描述e=m ⊕m′和Edit(m,e)=m ⊕e=m′, 那么可否认编辑方案直接是标准的可否认加密方案. 在此情况下,ℓ=n成立. 从而, 可否认编辑可以看作是可否认加密的一般化概念.

4.2 具体构造

基于提出的单密钥私钥函数加密方案FE = (Setup,Gen,Enc,Dec,SEnc,SDec), 本文设计了高效的接收者可否认编辑方案DE. 该方案基本与Goldwasser 等人[15]给出的方案相同, 除了以下3 点不同:

· 本文的方案基于提出的更高效单密钥私钥函数加密方案(见3.2 节) 设计, 使得该方案比Goldwasser 等人给出的私钥可否认编辑方案更加有效.

· 本文的方案支持更强的随机数否认(代替私钥否认), 并简化了正常模式下密钥生成算法.

· 与Goldwasser 等人方案相同,加密算法仍然加密(m,k),其中m ∈{0,1}n为明文和k ∈{0,1}κ+ℓ为随机数. 然而, 对于否认模式下的解密算法, 本文的方案只用FE 的特殊解密算法SDec 解密密文恢复明文m(而不是(m,k)). 该简单的优化不能提升Goldwasser 等人方案的效率, 但是能够减少本文方案的解密算法计算时间(ℓ+κ)tprf.

为了能否认随机数(而不是私钥), 本文要求SK2FE 方案FE 满足以下性质:

· 不失一般性, 函数密钥sky ←FE.Gen(msk,y) 总是分解为sky=(y,sk′y).

· 令Ky为y ∈{0,1}n2所对应的密钥空间. 存在PPT 采样算法Sample 能从Ky中均匀随机选取sk′y. 为了描述简单, 本文也用sk′y ←Ky表示从密钥空间Ky中均匀随机选取sk′y.

· 存在逆采样算法IGen满足: 对于任意的y ∈{0,1}n2和sky ←FE.Gen(msk,y),r ←IGen(sk′y) 使得sk′y=Sample(r) 且r与均匀的随机数计算不可区分, 其中sky=(y,sk′y).

第3 节给出的SK2FE 方案满足以上性质. 具体地, 密钥空间Ky={0,1}n2κ; Sample 随机选取sk′i,yi ←

其中m ∈{0,1}n和k ∈{0,1}κ+ℓ.

给定关于函数FEdit具有特殊加解密功能的单密钥私钥函数加密方案FE, 本文获得以下高效的私钥可否认编辑方案.

方案3 (私钥可否认编辑) 令消息长度n和编辑描述长度ℓ均为安全参数κ的函数. 对于任意多项式时间的编辑函数Edit :{0,1}n×{0,1}ℓ →{0,1}n, 本文能构造一个私钥可否认编辑方案DE =(Gen,Enc,Dec,DenGen,DenEnc,DenDec,Deny), 如图4 所示.

图4 私钥可否认编辑加密方案构造Figure 4 Construction of proposed secret-key deniable edit encryption scheme

对于否认模式下的算法, 本文的私钥可否认编辑方案能获得完美的正确性, 基于底层SK2FE 方案FE的完美正确性. 对于正常模式下的算法, 本文的方案获得统计正确性, 即正确性以概率1-1/2κ成立. 特别地, 因为y,k ∈{0,1}κ+ℓ都是均匀随机的字符串, 所以事件∃es.t.y ⊕k= (0κ,e) 发生的概率至多为1/2κ. 如果该事件没有发生, 那么解密算法将正确恢复明文m, 基于SK2FE 方案FE 的完美正确性.

定理2 如果FE 是关于函数FEdit的满足特殊加解密性质的单密钥私钥函数加密方案(即满足定义1),那么如图4 所示的私钥可否认编辑方案DE 满足选择明文安全性和接收者编辑可否认性. 特别地, 以下关系成立:

为了否认t个密文c= (c1,c2,··· ,ct)(其中ci是(mi,ki) 的FE 密文), 本文能首先产生关于向量y的FE 私钥sky(其中yi=ki ⊕(0κ,ei)), 然后用算法IGen计算得到密钥生成的随机数rc,e.

4.3 发送者可否认编辑方案

本节将4.2 节描述的接收者可否认编辑方案DE 转化为发送者可否认编辑方案DE′, 其中转化后的方案如图5 所示. 当方案DE 是非交互的, 转化后的方案DE′是交互的.

图5 发送者可否认编辑方案Figure 5 Sender-deniable edit scheme

本文主要基于Canetti 等人[1]给出的接收者可否认加密方案与发送者可否认加密方案之间的转换方法, 也观察到“一次一密” 中XOR 操作允许将对随机数的编辑转换到对明文的编辑. 具体地, 如图5 所示的发送者可否认编辑方案DE′设计思想如下:

· 发送者能用DE.DenGen 和DE.Gen 生成否认私钥dk 和正常私钥sk, 并与接收者共享这些私钥.然后, 接收者用加密算法加密一个随机数s并发送相应的密文c1给发送者; 发送者能用对应的解密算法解密c1获得s. 发送者能通过“一次一密” 的方法用s加密真正的明文m得到密文c2. 在收到密文c2以后, 接收者能用s解密密文c2获得明文m.

· 因为明文m和随机数s处于对称关系, 所以能通过否认s来实现对明文m的否认. 具体地, 令s′=Edit(s,e), 那么c2⊕s′=(m ⊕s)⊕s′=Edit(m,e). 这是因为通过编辑函数Edit 对随机数s任意比特的翻转, 都将记录在s′中, 使得s ⊕s′在相应翻转位置比特为1, 进而翻转m相应位置的比特, 从而实现对m的编辑. 更具体来说, 在可否认模式下, 发送者能用算法DE.Deny(dk,c1,e)计算否认的随机数rc,e, 使得Edit(s,e) = DE.Dec(skc,e,c1), 其中skc,e ←DE.Gen(1κ;rc,e). 进一步有c2⊕Edit(s,e)=m ⊕s ⊕Edit(s,e)=Edit(m,e) 成立.

因为“一次一密” 是信息论安全的, 所以如图5 所示的发送者可否认编辑方案的安全性完全依赖于底层接收者可否认编辑方案的安全性.

5 预先计划的可否认加密方案

本节基于第4 节提出的私钥可否认编辑方案设计预先计划的可否认加密方案. 本文仅描述满足接收者可否认性的预先计划可否认加密方案, 其中满足发送者可否认性的方案能利用Canetti 等人[1]给出的转换方法获得(见第4.3 节). 本文主要借鉴了O’Neill 等人[11]提出的方法, 根据私钥可否认加密的特点优化了该方法, 使得否认密文无需存储加密所用的随机数. 优化后的方法也很好地适配了底层所用的私钥可否认编辑方案. 在给出具体构造之前, 本文首先给出预先计划私钥可否认加密方案的定义.

5.1 预先计划私钥可否认加密的定义

以下满足接收者可否认性的预先计划私钥加密方案的定义是通过修改O’Neill 等人[11]给出的满足双可否认性的预先计划公钥加密方案的定义获得. 本文给出的定义也扩展了O’Neill 等人给出的定义, 从预先计划1 个否认明文到预先计划t个否认明文, 其中t ∈N,t ≥1.

定义9 (预先计划的私钥可否认加密) 令明文长度n和预先计划否认明文的数量t均为安全参数κ的多项式函数. 对于预先计划t个否认明文的私钥可否认加密方案PADE = (Gen,Enc,Dec,DenGen,DenEnc,DenDec,Deny) 由以下多项式时间算法组成:

· (Gen,Enc,Dec) 满足定义5 中描述的私钥加密方案定义.

· dk←DenGen(1κ): 否认密钥生成算法产生一个否认密钥dk.

· ct←DenEnc(dk,m,{mi}i∈[t]): 否认加密算法输入否认密钥dk、真实的明文m ∈{0,1}n和t个预先计划的否认明文m1,m2,··· ,mt ∈{0,1}n, 输出可否认的密文ct.

·m ←DenDec(dk,ct): 否认解密算法输入密钥dk 和密文ct, 输出明文m.

·rct,q ←Deny(dk,ct,q): 否认算法输入否认密钥dk、密文ct 和否认明文的索引q ∈[t], 输出随机数rct,q满足: skct,q ←Gen(1κ;rct,q) 和mq=Dec(skct,q,ct).

正确性. 对于每个安全参数κ ∈N、真实明文m ∈{0,1}n和否认明文m1,m2,··· ,mt ∈{0,1}n, 以下成立:

选择明文安全性. 私钥加密方案(Gen,Enc,Dec) 和(DenGen,DenEnc,DenDec) 分别满足定义5 中给出的选择明文攻击(CPA) 安全性. 令PADEnorm= (Gen,Enc,Dec) 和PADEdeny= (DenGen,DenEnc,

5.2 预先计划的私钥可否认加密构造

本节给出预先计划私钥可否认加密方案的具体构造如下.

方案4 (预先计划私钥可否认加密) 令Edit′为以下编辑函数:

给定关于以上编辑函数Edit′的私钥接收者可否认编辑方案DE = (Gen,Enc,Dec,DenGen,DenEnc,DenDec,Deny) 和私钥加密方案SE = (Gen,Enc,Dec), 本文设计的预先计划接收者可否认加密方案PADE = (Gen,Enc,Dec,DenGen,DenEnc,DenDec,Deny) 如图6 所示. 方案PADE 主要采用混合加密的思想, 用私钥可否认编辑方案DE 加密随机的密钥, 然后用这些密钥和私钥加密方案SE 加密明文. 加密算法中的随机值p用于将真实的密文c0插入在随机的位置, 使得敌手无法判断哪个密文加密了真实的明文, 从而支持了对密文的否认. 通过底层可否认编辑方案和私钥加密方案的正确性, 该预先计划可否认加密方案的正确性是直接的, 其中解密算法总是用K0解密对应的密文c′p.

在图6 所示的预先计划可否认加密方案中, PADE.DenEnc 算法选取了一个随机数k ∈{0,1}κ并将其加密. 直观上看, 这似乎是不必要的. 然而, 为了在私钥场景下达到可证明安全性, 本文需要用随机数k区分挑战密文ct 和其他密文. 具体而言, 敌手获得随机数rct,q后, 可执行密钥生成算法PADE.Gen(1κ,rct,q) 获得私钥skct,q. 根据编辑描述e= (k,p)⊕(0κ,q) 和编辑函数Edit′的定义, 容易看到PADE.Dec(skct,q,ct)=mq. 对于任意的其他密文ct′, PADE.Dec(skct,q,ct′) 计算得到真实的明文m, 除非密文ct 和ct′用的随机数k相同, 其发生的概率至多为1/2κ. 在这种情况下, 敌手即使获得密钥生成的随机数以后, 也不能区分在正常模式和否认模式下加密预言机的不同加密方式.

其中qo表示敌手A询问加密预言机的数量.

两个私钥加密方案PADEnorm= (Gen,Enc,Dec) 和PADEdeny= (DenGen,DenEnc,DenDec) 的CPA安全性可以直接由底层可否认编辑方案DEnorm和DEdeny的CPA 安全性以及私钥加密方案SE 的CPA安全性保证. 在安全证明上主要的不同是: PADEdeny需要利用混合论证(hybrid argument) 方法一步一步将密文c0,c1,··· ,ct中的明文替换为另一个明文; 而PADEnorm并不需要混合论证, 由于c1,c2,··· ,ct是随机的密文. 方案PADE 的预先计划接收者可否认性可以直接由底层可否认编辑方案DE 的接收者编辑可否认性和私钥加密方案SE 的一次伪随机性保证, 其中基于SE 的一次伪随机性利用混合论证方法将除mq之外其他明文对应的密文替换为均匀随机的密文. 具体而言, 以上定理的证明描述如下:

基于以上游戏之间的界, 敌手A针对PADEdeny选择明文安全性的优势被界定如下:

通信与存储效率分析. 本文用第4 节描述的私钥可否认编辑方案实例化方案DE. 对于私钥加密方案SE, 本文用伪随机函数PRF:{0,1}κ×{0,1}κ →{0,1}n实现. 特别地,

在本文的预先计划私钥可否认加密方案中密钥K0,K1,··· ,Kt都是独立均匀随机的且仅使用一次. 从而, 一次性加密t+ 1 个n比特长的明文仅需(t+ 1)n比特的密文. 该函数PRF 容易从伪随机置换PRF′:{0,1}κ×{0,1}κ →{0,1}κ, 即PRF(K,r) = PRF′(K,r‖1)‖···‖PRF′(K,r‖ℓ), 其中r ∈[0,t] 和ℓ=「n/.

预先计划私钥可否认加密方案PADE 的否认密钥长度和私钥长度分别为|dk| =κ比特和|sk| =(logt+κ)κ比特. 下面分析方案PADE 的密文长度. 令以下函数FEdit′为编辑函数Edit′对应的函数: