一种公钥可否认加密方法及系统

摘要

本发明属于公钥加密技术领域，公开了一种公钥可否认加密方法及系统，包括：建立解密可控的公钥加密方案PKE‑CD方案，用于生成可解密和不可解密的密文，将可解密的密文否认成不可解密的密文；从函数族中随机选取一个函数f，用于将随机字符串映射成其某个比特1的位置；输入公钥，真实和伪造的消息以及随机数，调用函数f和PKE‑CD中的加密算法生成密文；输入私钥和密文，调用PKE‑CD中的解密算法，输出解密结果，调用函数f，输出真实传输的消息；当发送方受到胁迫时，输入公钥，真实的消息，加密的随机数和伪造的消息，调用函数f和PKE‑CD中的伪造算法，输出伪造的随机数，将其和伪造的消息一起发送给胁迫方。本发明支持一次多比特消息的加密，实现了δ(n)的可否认性。

权利要求

1.一种公钥可否认加密方法，其特征在于，所述公钥可否认加密方法包括：建立一个解密可控的公钥加密方案PKE‑CD方案；

在函数族 中随机选取一个函数f；

输入公钥PK，真实传输的消息m∈M，伪造的消息m′∈M和随机数 发送方调用函数f和PKE‑CD方案中的Encrypt算法，输出密文c；

输入私钥SK和密文c，接收方调用PKE‑CD方案中的Decrypt算法，输出解密结果，调用函数f，输出真实传输消息m；

当发送方受到胁迫时，输入公钥PK，真实传输的消息m，随机数 和伪造的消息m′，调用函数f和PKE‑CD方案中的Fake算法，输出伪造的随机数所述公钥可否认加密方法的PKE‑CD方案包括以下四个算法：λ

KeyGen(1)是一个密钥生成算法，输入安全参数λ，输出公私密钥对(pk,sk)；

Encrypt(pk,m,d,r)是一个加密算法，输入公钥pk，消息m∈M，标签d∈{0,1}和随机数r∈Ωd，输出密文c；

Decrypt(sk,c)是一个确定的解密算法，输入私钥sk和密文c，如果d＝1输出消息m，否则输出⊥；

Fake(pk,m,r,m′)是一个伪造算法，输入公钥pk，真实传输的消息m，随机数r∈Ω1和伪造的消息m′∈M，输出r″←Fake(pk,m,r,m′)，其中r″属于Ω0且满足Encrypt(pk,m′,0,r″)＝Encrypt(pk,m,1,r)；

所述公钥可否认加密方法的函数族

n

对于任意的字符串e＝(en,en‑1,...,e1)∈{0,1}，定义函数族n

选取一个随机 定义Xn＝{e|e∈{0,1} },Yn(f)＝{e′|e′＝(en,...,ef(e)+1,0,n n

ef(e)‑1,...,e1)∈{0,1} ,e←Xn\{0}}；

分布 和 是δ(n)‑接近的，δ(n)是一个无穷小量；

所述公钥可否认加密方法的 输入公钥PK，真实传输的消息m∈M，伪造的消息m′∈M和随机数 算法Enc运行如下：随机选取e＝(en,en‑1,...,e1)∈Xn，计算k＝f(e)；

令e″＝(en,en‑1,...,ek+1,0,ek‑1,...,e1)，计算k″＝f(e″)；

当i＝k，i＝k″时，令mk←m，mk″←m′，随机选取rk,rk″∈Ω1，生成ck←Encrypt(pk,mk,1,rk)和ck″←Encrypt(pk,mk″,1,rk″)；当1≤i≤n，i≠k，i≠k″时，随机选取mi∈M， 生成ci←Encrypt(pk,mi,ei,ri)；最终输出c＝(cn,cn‑1,...,c1)；

所述公钥可否认加密方法的Dec(SK,c)：输入私钥SK和密文c，算法Dec运行如下：将密文c解析为cn,cn‑1,...,c1，运行算法Decrypt解密每一个子密文ci，其中1≤i≤n；

如果ci是可解密的密文，输出mi并将其位置i标记为1，否则输出⊥并将位置i标记为0；

从上一步的结论中接收方获得e＝(en,en‑1,...,e1)，计算k＝f(e)，获得真实传输的消息m＝mk；

所述公钥可否认加密方法的 输入公钥PK，真实传输的消息m，随机数 和伪造的消息m′，Fake算法运行如下：从随机数 中获得e，计算k＝f(e)；

令e″＝(en,en‑1,...,ek+1,0,ek‑1,...,e1)，计算k″＝f(e″)；

随机选取m″k∈M，生成r″k←Fake(pk,m,rk,m″k)；

当1≤i≤n，i≠k时，令m″i←mi，r″i←ri，输出 其中 中包含e″，{m″i|1≤i≤n,i≠k″}，{r″i|1≤i≤n}。

2.一种计算机设备，其特征在于，所述计算机设备包括存储器和处理器，所述存储器存储有计算机程序，所述计算机程序被所述处理器执行时，使得所述处理器执行权利要求1所述公钥可否认加密方法的步骤。

3.一种计算机可读存储介质，存储有计算机程序，所述计算机程序被处理器执行时，使得所述处理器执行权利要求1所述公钥可否认加密方法的步骤。

4.一种实施权利要求1所述公钥可否认加密方法的公钥可否认加密系统，其特征在于，所述公钥可否认加密系统包括：

PKE‑CD加密模块，用于生成可解密或不可解密的密文；

PKE‑CD解密模块，用于解密密文，对可解密密文输出其对应的加密消息，对不可解密的密文输出⊥；

PKE‑CD伪造模块，用于将可解密的密文否认成一个不可解密的密文；

函数f计算模块，用于将随机字符串映射成其某个比特1的位置；

可否认加密模块，输入公钥、真实和伪造的消息以及随机数，调用函数f计算模块和PKE‑CD加密模块，输出密文；

可否认解密模块，输入私钥和密文，调用PKE‑CD解密模块，输出解密结果，调用函数f计算模块，输出真实传输的消息；

可否认伪造模块，输入公钥，真实传输的消息，加密时用的随机数和伪造的消息，调用函数f计算模块和PKE‑CD伪造模块，输出伪造的随机数。

5.一种通信数据隐私保护终端，其特征在于，所述通信数据隐私保护终端搭载权利要求4所述的公钥可否认加密系统。

说明书

一种公钥可否认加密方法及系统

技术领域

[0001] 本发明属于公钥加密技术领域，尤其涉及一种公钥可否认加密方法及系统。

背景技术

[0002] 目前，在被动窃听敌手存在的场景中，加密技术可以保护通信数据的隐私。然而，在某些场景中，可能会存在胁迫问题，例如，假设Eve经常使用公钥加密方案传输一些机密
消息，如果Eve不幸被捕，此时，Eve可能会受到威胁，要求其揭露被截获密文所对应的明文
以及加密明文消息时使用的随机数。在这种情况发生时，有没有办法可以让Eve在不泄露真
实传输消息的情况下遵守胁迫方的要求呢？1997年，Canetti等人提出了可否认加密技术，
为上述问题提供了一个可行的解决方法。粗略地说，可否认加密允许发送方(或接收方或双
方)通过伪造一个假的随机数(可能是加密时或密钥生成时所需的一些参数)不可察觉地将
传输的密文打开成另一个消息。从上述描述可以看出，可否认加密具有一种有趣的特性，称
为可否认性。可否认加密在一些场景中具有广泛的应用，如用于设计不可胁迫(或无收据)
的选举方案、拍卖方案和密钥托管等，还可以用于构造通用的不可胁迫的多方计算协议和
自适应安全多方协议。

[0003] 在过去的二十年中，已经有一些关于可否认加密的工作。Canetti等人提出可否认加密概念的同时也描述了两种可否认加密的模型。一种称为完全可否认模型，在这个模型
中，通信双方始终运行指定的算法，且当受到胁迫时，可以对其传输的消息进行否认。另一
种是一个较弱的模型，称为多分布可否认模型，在这个模型中，通信双方运行备用的密钥生
成算法和加密算法，事后，双方令人信服地声称他们使用指定的算法传输了不同的消息。
Canetti等人在最初的工作中也给出了在不同模型中的可否认加密方案，其中完全可否认
模型中的方案称为party方案，然而方案要实现高的可否认性密文扩展严重。Klonowski等
人提高了Canetti等人多分布模型中可否认加密方案的可否认性，此外，他们还基于
ElGamal加密给出了一个接收方接可否认加密方案，但此方案需要双方预先共享秘密信息。
Ibrahim在多分布的可否认模型中基于二次剩余假设提出了单比特和多比特的发送方可否
认加密方案。对于单比特加密的方案，可以看作是Canetti等人方案的具体实现。而对于多
比特加密的方案而言，仅在加密几比特时是有效的，并且其伪造的消息可能没有意义。在之
后的工作中，他基于Mediated RSA和不经意传输(OT)协议提出了一个接收方可否认加密方
案。但由于Mediated PKI的局限性和OT协议的复杂性，使得方案在实用性和效率上是不切
实际的。2011年，O’Neill等人在多分布的可否认模型中设计了第一个非交互的双方可否认
加密，实现了可忽略的可否认性。Bendlin等人表明在完全可否认的模型中任何非交互的公
钥接收方可否认(或双方否认)加密方案的可否认性不会比多项式的可否认性更好。Dü
rmuth等人在完全可否认的模型中提出了一种发送方可否认的加密方案，具有可忽略的可
否认性，但该方案已被证明是不安全的。2014年，Sahai等人在完全可否认的模型中基于不
可分区分混淆(iO)提出第一个具有可忽略的可否认性的发送方可否认加密方案。2018年，
Canetti等人也利用iO在完全可否认的模型中构造了一个具有可忽略的可否认性的交互式
双方可否认加密方案。但是，目前iO还没有一个高效实现方法，这意味着以上两个完全可否
的加密方案仅具有理论意义。目前，一些已知的多分布可否认模型中的方案可以在实践中
实施，但是它们中的备用算法可能会导致一些问题：如误用、怀疑和协商等。因此，为了获得
更安全的保证，应使用完全可否认加密方案。但据我们所知，在完全可否认的模型中设计一
个实用的公钥可否认加密方案仍然是一个有趣的挑战。

[0004] 通过上述分析，现有技术存在的问题及缺陷为：在多分布的可否认模型中的一些方案可以在实践中实施，但模型中存在备用的加密算法和密钥生成算法可能会导致误用、
怀疑和协商等问题。所以为了获得更安全的保证，应使用完全可否认模型中的方案，因为该
模型中的方案总是运行指定的算法。然而，目前在完全可否认的模型中方案不具有实用性，
具体来说，基于iO的构造，由于iO的复杂低效使得方案不能被实施；基于半透明集的构造，
实现高的可否认性密文扩展严重。

[0005] 解决以上问题及缺陷的难度为：在完全可否认的模型中设计实用的公钥可否认加密，难度在于实现强可否认性的同时降低密文长度。

[0006] 解决以上问题及缺陷的意义为：可否认加密算法旨在在胁迫者存在的场景中保护传输数据的隐私，设计具有强可否认性低通信开销的方案，利用可否认加密在实践中实施。

发明内容

[0007] 针对现有技术存在的问题，本发明在完全可否认的模型中提供了一种公钥可否认加密方法及系统。

[0008] 本发明是这样实现的，一种公钥可否认加密方法，所述公钥可否认加密方法包括：

[0009] 第一步，建立一个解密可控的公钥加密方案PKE‑CD方案；

[0010] 第二步，在函数族 中选取随机函数f；

[0011] 第三步，输入公钥PK，真实传输的消息m∈M，伪造的消息m′∈M和随机数 发送方调用函数f和PKE‑CD方案中的Encrypt算法，输出密文c；

[0012] 第四步，输入私钥SK和密文c，接收方调用PKE‑CD方案中的Decrypt算法，输出解密结果，调用函数f，输出真实传输消息m；

[0013] 第五步，当发送方受到胁迫时，输入公钥PK，真实传输的消息m，随机数 和伪造的消息m′，调用函数f和PKE‑CD方案中的Fake算法，输出伪造的随机数

[0014] 进一步，所述公钥可否认加密方法中的PKE‑CD方案包括以下四个算法：

[0015] KeyGen(1λ)是一个密钥生成算法，输入安全参数λ，输出公私密钥对(pk,sk)。

[0016] Encrypt(pk,m,d,r)是一个加密算法，输入公钥pk，消息m∈M，标签d∈{0,1}和随机数r∈Ωd，输出密文c。

[0017] Decrypt(sk,c)是一个确定的解密算法，输入私钥sk和密文c，如果d＝1输出消息m，否则输出⊥。

[0018] Fake(pk,m,r,m′)是一个伪造算法，输入公钥pk，真实传输的消息m，随机数r∈Ω1和伪造的消息m′∈M，输出r″←Fake(pk,m,r,m′)，其中r″属于Ω0且满足Encrypt(pk,m′,0,
r″)＝Encrypt(pk,m,1,r)

[0019] 进一步，所述公钥可否认加密方法的函数族

[0020] 对于任意的字符串e＝(en,en‑1,...,e1)∈{0,1}n，定义函数族

[0021] 进一步，所述公钥可否认加密方法的 输入公钥PK，真实传输的消息m∈M，伪造的消息m′∈M和随机数 算法Enc运行如下：

[0022] 随机选取e＝(en,en‑1,...,e1)∈Xn，计算k＝f(e)；

[0023] 令e″＝(en,en‑1,...,ek+1,0,ek‑1,...,e1)，计算k″＝f(e″)；

[0024] 当i＝k，i＝k″时，令mk←m，mk″←m′，随机选取rk,rk″∈Ω1，生成ck←Encrypt(pk,mk,1,rk)和ck″←Encrypt(pk,mk″,1,rk″)；当1≤i≤n，i≠k，i≠k″时，随机选取mi∈M，
生成ci←Encrypt(pk,mi,ei,ri)；最终输出c＝(cn,cn‑1,...,c1)。

[0025] 进一步，所述公钥可否认加密方法的Dec(SK,c)：输入私钥SK和密文c，算法Dec运行如下：

[0026] 将密文c解析为cn,cn‑1,...,c1，运行算法Decrypt解密每一个子密文ci，其中1≤i≤n。如果ci是可解密的密文，输出mi并将其位置i标记为1，否则输出⊥并将位置i标记为0。

[0027] 从上一步的结论中接收方获得e＝(en,en‑1,...,e1)，计算k＝f(e)，获得真实传输的消息m＝mk。

[0028] 进一步，所述公钥可否认加密方法的 输入公钥PK，真实传输的消息m，随机数 和伪造的消息m′，Fake算法运行如下：

[0029] 从随机数 中获得e，计算k＝f(e)；

[0030] 令e″＝(en,en‑1,...,ek+1,0,ek‑1,...,e1)，计算k″＝f(e″)；

[0031] 随机选取m″k∈M，生成r″k←Fake(pk,m,rk,m′k′)；

[0032] 当1≤i≤n，i≠k时，令m″i←mi，r″i←ri，输出 其中 中包含e″，{m″i|1≤i≤n,i≠k″}，{r″i|1≤i≤n}。

[0033] 本发明的另一目的在于提供一种计算机设备，所述计算机设备包括存储器和处理器，所述存储器存储有计算机程序，所述计算机程序被所述处理器执行时，使得所述处理器
执行如下步骤：

[0034] 第一步，建立一个解密可控的公钥加密方案PKE‑CD方案；

[0035] 第二步，在函数族 中选取随机函数f；

[0036] 第三步，输入公钥PK，真实传输的消息m∈M，伪造的消息m′∈M和随机数 发送方调用函数f和PKE‑CD方案中的Encrypt算法，输出密文c；

[0037] 第四步，输入私钥SK和密文c，接收方调用PKE‑CD方案中的Decrypt算法，输出解密结果，调用函数f，输出真实传输消息m；

[0038] 第五步，当发送方受到胁迫时，输入公钥PK，真实传输的消息m，随机数 和伪造的消息m′，调用函数f和PKE‑CD方案中的Fake算法，输出伪造的随机数

[0039] 本发明的另一目的在于提供一种计算机可读存储介质，存储有计算机程序，所述计算机程序被处理器执行时，使得所述处理器执行如下步骤：

[0040] 建立一个解密可控的公钥加密方案PKE‑CD方案；

[0041] 在函数族 中选取随机函数f；

[0042] 输入公钥PK，真实传输的消息m∈M，伪造的消息m′∈M和随机数 发送方调用函数f和PKE‑CD方案中的Encrypt算法，输出密文c；

[0043] 输入私钥SK和密文c，接收方调用PKE‑CD方案中的Decrypt算法，输出解密结果，调用函数f，输出真实传输消息m；

[0044] 当发送方受到胁迫时，输入公钥PK，真实传输的消息m，随机数 和伪造的消息m′，调用函数f和PKE‑CD方案中的Fake算法，输出伪造的随机数

[0045] 本发明的另一目的在于提供一种实施所述公钥可否认加密方法的公钥可否认加密系统，所述公钥可否认加密系统包括：

[0046] PKE‑CD加密模块，用于生成可解密或不可解密的密文；

[0047] PKE‑CD解密模块，用于解密密文，对可解密密文输出其对应的加密消息，对不可解密的密文输出⊥；

[0048] PKE‑CD伪造模块，用于将可解密的密文否认成一个不可解密的密文；

[0049] 函数f计算模块，用于将随机字符串映射成其某个比特1的位置；

[0050] 可否认加密模块，输入公钥、真实和伪造的消息以及随机数，调用函数f计算模块和PKE‑CD加密模块，输出密文；

[0051] 可否认解密模块，输入私钥和密文，调用PKE‑CD解密模块，输出解密结果，调用函数f计算模块，输出真实传输的消息；

[0052] 可否认伪造模块，输入公钥，真实传输的消息和加密时用的随机数，以及伪造的消息，调用函数f计算模块和PKE‑CD伪造模块，输出伪造的随机数。

[0053] 本发明的另一目的在于提供一种通信数据隐私保护终端，所述通信数据隐私保护终端搭载所述的公钥可否认加密系统。

[0054] 结合上述的所有技术方案，本发明所具备的优点及积极效果为：本发明首先提出了一个解密可控的公钥加密方案PKE‑CD方案，该方案可以生成可解密和不可解密两种密
文，同时支持将可解密的密文否认成不可解密的密文。其次定义了一个函数族，集合中的函
数可以将一个随机字符串映射成字符串中某个比特1的位置。接着采用上述的方案和函数，
在完全可否认的模型中构造了一个公钥发送方可否认加密方案，该方案支持一次对多比特
消息进行加密，实现了δ(n)的可否认性，此外，与party方案对比，具有更强的可否认性，且
加密相同长度的消息时需要更少的通信开销。

附图说明

[0055] 为了更清楚地说明本申请实施例的技术方案，下面将对本申请实施例中所需要使用的附图做简单的介绍，显而易见地，下面所描述的附图仅仅是本申请的一些实施例，对于
本领域普通技术人员来讲，在不付出创造性劳动的前提下还可以根据这些附图获得其他的
附图。

[0056] 图1是本发明实施例提供的公钥可否认加密方法流程图。

[0057] 图2是本发明实施例提供的公钥可否认加密系统的结构示意图；

[0058] 图中：1、PKE‑CD加密模块；2、PKE‑CD解密模块；3、PKE‑CD伪造模块；4、函数f计算模块；5、可否认加密模块；6、可否认解密模块；7、可否认伪造模块。

[0059] 图3是本发明实施例提供的公钥可否认加密方案与party方案的效率对比表格。

具体实施方式

[0060] 为了使本发明的目的、技术方案及优点更加清楚明白，以下结合实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于
限定本发明。

[0061] 针对现有技术存在的问题，本发明提供了一种公钥可否认加密方法及系统，下面结合附图对本发明作详细的描述。

[0062] 如图1所示，本发明提供的公钥可否认加密方法包括以下步骤：

[0063] S101：建立一个解密可控的公钥加密方案PKE‑CD方案；

[0064] S102：在函数族 中选取随机函数f；

[0065] S103：输入公钥PK，真实传输的消息m∈M，伪造的消息m′∈M和随机数 发送方调用函数f和PKE‑CD方案中的Encrypt算法，输出密文c；

[0066] S104：输入私钥SK和密文c，接收方调用PKE‑CD方案中的Decrypt算法，输出解密结果，调用函数f，输出真实传输消息m；

[0067] S105：当发送方受到胁迫时，输入公钥PK，真实传输的消息m，随机数 和伪造的消息m′，调用函数f和PKE‑CD方案中的Fake算法，输出伪造的随机数

[0068] 本发明提供的公钥可否认加密方业内的普通技术人员还可以采用其他的步骤实施，图1的本发明提供的公钥可否认加密方法仅仅是一个具体实施例而已。

[0069] 如图2所示，本发明提供的公钥可否认加密系统包括：

[0070] PKE‑CD加密模块1，用于生成可解密或不可解密的密文；

[0071] PKE‑CD解密模块2，用于解密密文，对可解密密文输出其对应的加密消息，对不可解密的密文输出⊥；

[0072] PKE‑CD伪造模块3，用于将可解密的密文否认成一个不可解密的密文；

[0073] 函数f计算模块4，用于将随机字符串映射成其某个比特1的位置；

[0074] 可否认加密模块5，输入公钥、真实和伪造的消息以及随机数，调用函数f计算模块4和PKE‑CD加密模块1，输出密文；

[0075] 可否认解密模块，输入私钥和密文，调用PKE‑CD解密模块2，输出解密结果，调用函数f计算模块4，输出真实传输的消息；

[0076] 可否认伪造模块，输入公钥，真实传输的消息，加密时用的随机数和伪造的消息，调用函数f计算模块4和PKE‑CD伪造模块3，输出伪造的随机数。

[0077] 下面结合附图对本发明的技术方案作进一步的描述。

[0078] 本发明支持一次可以对多比特消息进行加密，同时支持δ(n)的可否认性。首先提出了一个解密可控的公钥加密方案PKE‑CD方案，该方案可以生成可解密和不可解密两种密
文，同时支持将可解密的密文否认成不可解密的密文。其次定义了一个函数族，集合中的函
数f可以将一个随机字符串映射成字符串中某个比特1的位置。采用上述提到的方案和函数
f，在完全可否认的模型中构造了一个公钥发送方可否认加密方案，加密时，发送方输入公
钥，真实和伪造的消息以及随机数，调用函数f和PKE‑CD中的加密算法生成密文；解密时，接
收方输入私钥和密文，调用PKE‑CD中的解密算法，输出解密结果，接着调用函数f，输出真实
传输消息的位置，进而输出真实传输的消息；当发送方受到胁迫时，发送方输入公钥，真实
传输的消息，加密时用的随机数和伪造的消息，调用函数f和PKE‑CD方案中的伪造算法，输
出伪造的随机数，发送方揭露伪造的消息和伪造的随机数给胁迫方，胁迫方根据揭露的信
息将伪造的消息识别成真实传输的消息，从而实现了真实传输消息的隐私保护。本发明与
party方案相比，具有更强的可否认性，且加密相同长度的消息需要更少的通信开销。

[0079] 1、预备知识，介绍了一些符号、密码学假设，回顾了公钥δ(n)‑发送方可否认加密方案及其安全性要求。

[0080] 1.1符号n

[0081] {0,1} 表示所有n长的字符串构成的集合，PPT表示概率多项式时间， 表示x
群， 表示群 的阶为N， 表示群 是群 的子群。为了简便，分别用g·h和g
xmodφ(N)
表示群 中的乘法运算g·hmodN和指数运算g 。x←y表示将y值赋值给x，x←X表示从
集合X中随机选取一个元素x，y←A(x)表示输入x，算法A输出y。

[0082] 在描述公钥δ(n)‑发送方可否认加密之前，首先回顾下δ(n)‑接近的概念。

[0083] 定义1：(δ(n)‑接近的)，令 和 是两个概率分布集合，令本发明称分布X和Y是δ(n)‑接近的，如果对于任一多项式时间的区分器D和
所有足够大的n有|Pr(D(Xn)＝1)‑Pr(D(Yn)＝1)|<δ(n)。

[0084] 如果δ(n)是可忽略的，本发明称分布X和Y是计算上不可区分的。

[0085] 1.2公钥δ(n)‑发送方可否认加密

[0086] Canetti等人给出了δ(n)‑发送方可否认加密的一般定义如下。

[0087] 定义2：(公钥δ(n)‑发送方可否认加密)，一个公钥δ(n)‑发送方可否认加密是一个4元组的多项式时间算法(Gen,Enc,Dec,Fake)，描述如下：

[0088] Gen是一个密钥生成算法，输入安全参数n，输出公私密钥对(pk,sk)。

[0089] Enc是一个加密算法，输入公钥pk，真实传输的消息m∈M和随机数r，输出密文c。

[0090] Dec是一个解密算法，输入私钥sk和密文c，输出消息m。

[0091] Fake是一个有效的伪造算法，输入公钥pk，真实传输的消息m∈M，随机数r和伪造的消息m′∈M，输出r″←Fake(pk,m,r,m′)，r″满足Enc(pk,m′,r″)＝Enc(pk,m,r)。

[0092] 一个公钥δ(n)‑发送方可否认加密需要满足下列的性质。

[0093] 正确性：接收方的输出不同于发送方的输入的概率是可忽略的。

[0094] 安全性：对于任意的m0,m1∈M，传输m0和传输m1的通讯是计算上不可区分的。

[0095] 可否认性：对于任意的m,m′∈M，随机数r,r′，令c←Enc(pk,m,r)，r″←Fake(pk,m,r,m′)，对于仅有公钥pk的PPT区分器而言，随机变量(m′,r″,c)和(m′,r′,Enc(pk,m′,r′))
是δ(n)‑接近的。

[0096] 注意当发送方在加密的同时选择了伪造的消息m′，我们称这种方案为提前计划的可否认加密方案。

[0097] 1.3困难假设

[0098] 本发明描述了两个困难假设：子群成员问题假设和一比特翻转分布假设。

[0099] 定义3：(子群成员问题假设)，令 是一个有限阿贝尔群， 是其非平凡的子群，给定一个随机元素 判断x是否属于子群 的问题称为子群成员问题。定义一个打破子
群成员问题的PPT敌手 的优势如下：

[0100]

[0101] 其中·表示公开参数。子群成员问题假设表明对于任意的敌手 是可忽略的。

[0102] 定义4：(一比特翻转分布假设)，对于任意的字符串e＝(en,en‑1,...,e1)∈{0,1}n，定义一个函数族 选取一个随机 定义Xn＝
n n n
{e|e∈{0,1}},Yn(f)＝{e′|e′＝(en,...,ef(e)+1,0,ef(e)‑1,...,e1)∈{0,1} ,e←Xn\{0}}；
分布 和 是δ(n)‑接近的，这里的δ(n)是一个无穷小量。

[0103] 这个假设表明，当n足够大时，在一个随机的n长字符串中，仅随机的将某位比特1修改成0不会影响其随机性。

[0104] 在这里本发明给出上述函数f的一种实现方法。首先，令x是一个n长的字符串，将x中比特的位置从右开始标记为1,2,...,n，用Γ(x,i)来表示x中从右边数第i个1的位置，例
如，Γ(11001,2)＝4，表示11001中第2个1的位置为4。然后，随机选取一个伪随机函数
定义f(x)＝Γ(x,G(x)mod‖x‖)，其中‖x‖是字符串x的汉明权重。易
验证f(x)是PPT可计算的。

[0105] 2、解密可控的公钥加密

[0106] 本发明提出了解密可控的公钥加密(PKE‑CD)，其中密文能否解密取决于发送方的决定。此外，本发明还阐述了该加密的安全性需求，并给出了一个具体的方案。

[0107] 2.1形式化定义

[0108] 定义5：(PKE‑CD)，解密可控的公钥加密方案Π＝(KeyGen,Encrypt,Decrypt,Fake)是一个4元组的多项式时间算法，定义如下：

[0109] KeyGen(1λ)是一个密钥生成算法，输入安全参数λ，输出公私密钥对(pk,sk)。

[0110] Encrypt(pk,m,d,r)是一个加密算法，输入公钥pk，消息m∈M，标签d∈{0,1}和随机数r∈Ωd，输出密文c。

[0111] Decrypt(sk,c)是一个确定的解密算法，输入私钥sk和密文c，如果d＝1输出消息m，否则输出⊥。

[0112] Fake(pk,m,r,m′)是一个伪造算法，输入公钥pk，真实传输的消息m，随机数r∈Ω1和伪造的消息m′∈M，输出r″←Fake(pk,m,r,m′)，其中r″属于Ω0且满足Encrypt(pk,m′,0,
r″)＝Encrypt(pk,m,1,r)。

[0113] 2.2安全性需求

[0114] PKE‑CD必须满足三个安全需求：正确性、语义安全和半可否认性。现在给出形式化的定义。

[0115] 定义6：(正确性)，如果对于可解密的密文来说，接收方的输出与发送方的输入不同的概率是可忽略的，且不可解密的密文被解密的概率是可忽略的，本发明称PKE‑CD方案
是正确的。

[0116] 语义安全游戏，本发明将语义安全游戏描述为敌手和挑战者之间的多阶段游戏：

[0117] Setup，挑战者运行算法(pk,sk)←KeyGen(1λ)，将公钥pk发送给敌手

[0118] Challenge， 输出两个不同的消息m0,m1∈M，收到由随机数r∈Ω1生成的挑战密文c←Encrypt(pk,mb,1,r)。

[0119] Guess， 输出猜测b′∈{0,1}。

[0120] 定义敌手 在这场游戏中的优势为：

[0121]

[0122] 定义7：(语义安全)，在窃听者存在的情况下，如果对所有的PPT敌手 函数是可忽略的，本发明称PKE‑CD方案是语义安全的。

[0123] 半可否认性游戏，本发明将半可否认性游戏描述为敌手和挑战者之间的多阶段游戏：
λ

[0124] Setup，挑战者运行算法(pk,sk)←KeyGen(1)，将公钥pk发送给敌手

[0125] Challenge， 输出两个不同的消息m,m′∈M，挑战者抛硬币b∈{0,1}。如果b＝0，随机选取r′∈Ω0，生成c′←Encrypt(pk,m′,0,r′)，返回(m′,r′,c′)给敌手 如果b＝1，
随机选取r∈Ω1，生成c←Encrypt(pk,m,1,r)，r″←Fake(pk,m,r,m′)，返回(m′,r″,c)给敌
手

[0126] Guess，根据分布X＝{(m′,r′,Encrypt(pk,m′,0,r′))|r′∈Ω0}和分布Y＝{(m′,r″,Encrypt(pk,m,1,r))|r∈Ω1,r″←Fake(pk,m,r,m′)}， 输出猜测b′∈{0,1}。

[0127] 定义敌手 在这场游戏中的优势为：

[0128]

[0129] 定义8：(半可否认性)，如果对所有的PPT敌手 函数 是可忽略的，本发明称PKE‑CD方案是半可否认的。

[0130] 如果上述两个分布X和Y是ε(λ)‑接近的，那么本发明称PKE‑CD方案是ε(λ)‑半可否认的。

[0131] 2.3一个具体的PKE‑CD方案

[0132] 本发明基于子群成员问题假设给出了一个具体的PKE‑CD方案。

[0133] KeyGen(1λ)：输入安全参数λ，随机选择两个等长的不同奇素数p和q满足P＝2N+1也是一个素数，其中N＝pq，令 是一个N阶的乘法群，选取群 的一个随机生成元g，
q
计算h＝g ，定义 易知 是 的一个p阶子群，算法KeyGen输出公钥
和私钥sk＝(p,q)；

[0134] Encrypt(pk,m,d,R)：输入公钥pk，消息m∈M＝{0,1,2,...,T}(集合M是一个整数m
集)，标签d∈{0,1}和随机数R，生成密文c＝gR；

[0135] 1.可解密的：R＝hr，其中

[0136] 2.不可解密的：R是 中的随机元素；

[0137] Decrypt(sk,c)：输入私钥sk和密文c，计算g′＝gp，c′＝cp；

[0138] 1.可解密的：给定c′＝cp＝(gmhr)p＝gpmgqrp＝(gp)m＝g′m，计算c′关于g′的离散对数，因为0≤m≤T，所以在O(T)时间内可以用穷举搜索方法找到m或者在 时间内用
Pollard’s lambda方法找到m；
p m p m p

[0139] 2.不可解密的：给定c′＝c ＝(g R) ＝g′R ，其中R是 中的随机元素,所以接收方从c′中得不到任何信息，返回⊥；

[0140] Fake(pk,m,r,m′)：输入公钥pk，真实传输的消息m，随机数r∈Ω1和伪造的消息m r m′ m′
m′，输出伪造的随机数R″＝gh/g ∈Ω0，之后，发送方可以声称c是由c＝g R″构造的不可
解密的密文。

[0141]

[0142]

[0143] 3、新的公钥发送方可否认加密方案

[0144] 本发明基于PKE‑CD方案和一比特翻转分布假设提出了一种公钥发送方可否认加密方案，然后给出了一个具体的实例。

[0145] 3.1方案

[0146] 令Π＝(KeyGen,Encrypt,Decrypt,Fake)表示一个PKE‑CD方案，M表示方案Π中的消息空间，给定在一比特翻转分布假设中定义的集合 Xn，Yn(f)。

[0147] Gen(1n)：输入安全参数n，运行算法KeyGen(1λ)生成(pk,sk)，随机选择 输出公钥PK＝(pk,f,n)和私钥SK＝sk。

[0148] 输入公钥PK，真实传输的消息m∈M，伪造的消息m′∈M和随机数 算法Enc运行如下：

[0149] 随机选取e＝(en,en‑1,...,e1)∈Xn，计算k＝f(e)；

[0150] 令e″＝(en,en‑1,...,ek+1,0,ek‑1,...,e1)，计算k″＝f(e″)；

[0151] 当i＝k，i＝k″时，令mk←m，mk″←m′，随机选取rk,rk″∈Ω1，生成ck←Encrypt(pk,mk,1,rk)和ck″←Encrypt(pk,mk″,1,rk″)，当1≤i≤n，i≠k，i≠k″时，随机选取mi∈M，
生成ci←Encrypt(pk,mi,ei,ri)；最终输出c＝(cn,cn‑1,...,c1)。

[0152] Dec(SK,c)：输入私钥SK和密文c，算法Dec运行如下：

[0153] 将密文c解析为cn,cn‑1,...,c1，运行算法Decrypt解密每一个子密文ci，其中1≤i≤n。如果ci是可解密的密文，输出mi并将其位置i标记为1，否则输出⊥并将位置i标记为0。

[0154] 从上一步的结论中接收方获得e＝(en,en‑1,...,e1)，计算k＝f(e)，获得真实传输的消息m＝mk。

[0155] 输入公钥PK，真实传输的消息m，随机数 和伪造的消息m′，Fake算法运行如下：

[0156] 从随机数 中获得e，计算k＝f(e)；

[0157] 令e″＝(en,en‑1,...,ek+1,0,ek‑1,...,e1)，计算k″＝f(e″)；

[0158] 随机选取m″k∈M，生成r″k←Fake(pk,m,rk,m′k′)；

[0159] 当1≤i≤n，i≠k时，令m″i←mi，r″i←ri，输出 其中 中包含e″，{m″i|1≤i≤n,i≠k″}，{r″i|1≤i≤n}。

[0160] 注意随机数 包含e，{mi|1≤i≤n,i≠k}，{ri|1≤i≤n}，其中伪造消息m′＝mk″已经包含于 中，所以本发明的方案是提前类型的可否认加密方案。

[0161]

[0162]

[0163]

[0164] 3.2一个实例

[0165] 基于2.3中描述的具体的PKE‑CD方案给出了本发明发送方可否认加密的一个具体实例。

[0166] Gen(1n)：输入安全参数n＝10，运行算法KeyGen(1λ)生成随机选择 输出公钥PK＝(pk,f,n＝10)和私钥SK＝sk，其中f的执行算法参见1.3。
注意，将n设置为10，在实际应用中太小，但此处仅通过给出一个简单的例子来描述本发明
的方案。此外，本发明假设f(1010110110)＝Γ(1010110110,3)＝5，f(1010100110)＝Γ
(1010100110,4)＝8。

[0167] 输入公钥PK，真实传输的消息m∈M，伪造的消息m′∈M和随机数 算法Enc运行如下：

[0168] 随机选取e＝(e10,e9,...,e1)∈X10，例如e＝(1010110110)，计算f(1010110110)＝5。

[0169] 令e″＝(1010100110)，计算f(1010100110)＝8。

[0170] 当i＝5，i＝8时，令m5←m，m8←m′，随机选取 生成 和当1≤i≤10，i≠5，i≠8时，随机选取mi∈M，
生成密文如下：

[0171]

[0172]

[0173] 最终输出c＝(c10,c9,...,c1)。注意加密阶段的随机数 包含(1010110110)，m10,...,m6,m4,...,m1，r10,R9,r8,R7,r6,r5,R4,r3,r2,R1。

[0174] Dec(SK,c)：输入私钥SK和密文c，算法Dec运行如下：

[0175] 将密文c解析为c10,c9,...,c1，运行算法Decrypt解密每一个子密文ci，其中1≤i≤10。输出(m10,1)，(⊥,0)，(m8,1)，(⊥,0)，(m6,1)，(m5,1)，(⊥,0)，(m3,1)，(m2,1)，(⊥,0)。

[0176] 从上一步的结论中接收方获得e＝(1010110110)，计算f(1010110110)＝5，获得真实传输的消息m＝m5。

[0177] 输入公钥PK，真实传输的消息m＝m5，随机数 和伪造的消息m′＝m8，Fake算法运行如下：

[0178] 从随机数 中获得e，计算f(1010110110)＝5。

[0179] 令e″＝(1010100110)，计算f(1010100110)＝8。

[0180] 随机选取m″5∈M，生成

[0181] 输出 其中 中包含(1010100110)，m10,m9,m7...,m6,m″5,m4,...,m1，r10,R9,r8,R7,r6, R4,r3,r2,R1。

[0182] 上述方案中存在两种打开加密的方式，如下：

[0183] 诚实打开加密：发送方输出

[0184] (m10,r10)，(m9,R9)，(m8,r8)，(m7,R7)，(m6,r6)，

[0185] (m5,r5)，(m4,R4)，(m3,r3)，(m2,r2)，(m1,R1)，

[0186] 声称传输的消息是m＝m5。

[0187] 不诚实打开加密：发送方输出：

[0188] (m10,r10)，(m9,R9)，(m8,r8)，(m7,R7)，(m6,r6)，

[0189] (m″5,R″5)，(m4,R4)，(m3,r3)，(m2,r2)，(m1,R1)，

[0190] 声称传输的消息是m′＝m8。注意m″5是从集合M随机选取的一个合理消息，

[0191] 当发送方受到胁迫时，他将不诚实的打开加密。

[0192] 下面结合效率分析对本发明的技术效果作详细的描述。

[0193] 本发明给出了新的公钥发送方可否认加密方案的效率分析。在已知的完全可否认加密方案中，Dürmuth等人的方案被证明是不安全，分别于2014年和2018年Sahai等人和
Canetti等人基于不可区分混淆提出的方案仅仅是理论上的构造。从安全性和可实施性的
角度出发，本发明仅与party方案进行了比较。首先本发明假设|m|表示多比特的消息(一般
来说，|m|可以取到40)，假设PKE‑CD方案中的密文长度和party方案中 ‑element(或 ‑
element)中元素的长度是一样的，用τ表示(例如，τ＝2048)。此外，本发明建议n的取值至少
应大于500。表格1给出了两个方案的详细比较。

[0194] 表1效率比较

[0195]方案 消息长度 密文长度 可否认性
party方案 1比特 nτ 4/n
本发明的方案 |m|比特 nτ δ(n)

[0196] 与party方案相比，本发明提出的方案具有更高的效率和更强的可否性。具体来说，本发明的方案一次可以加密|m|比特消息，实现了δ(n)的可否认性，这里δ(n)远小于1/
n，当两个方案同时加密|m|长的消息时，本发明将密文长度降低到nτ长。此外，从PKE‑CD方
案的实现中采样一个随机元素的速度比从party方案的半透明集更快。但是，本发明注意到
party方案是一个通用的构造，它可以使用任意的半透明集。在这个意义上，如果party方案
使用PKE‑CD方案作为半透明集，则两个方案的计算开销是可以比较的。本发明也注意到
party方案不是一个提前类型的可否认加密，但party方案一次仅可以加密一比特的消息，
因此，一旦加密消息固定，那么其伪造的消息也就被固定了，所以从这个意义上来讲，两个
方案都是提前类型的可否认加密，所以上述的比较是合理的。

[0197] 应当注意，本发明的实施方式可以通过硬件、软件或者软件和硬件的结合来实现。硬件部分可以利用专用逻辑来实现；软件部分可以存储在存储器中，由适当的指令执行系
统，例如微处理器或者专用设计硬件来执行。本领域的普通技术人员可以理解上述的设备
和方法可以使用计算机可执行指令和/或包含在处理器控制代码中来实现，例如在诸如磁
盘、CD或DVD‑ROM的载体介质、诸如只读存储器(固件)的可编程的存储器或者诸如光学或电
子信号载体的数据载体上提供了这样的代码。本发明的设备及其模块可以由诸如超大规模
集成电路或门阵列、诸如逻辑芯片、晶体管等的半导体、或者诸如现场可编程门阵列、可编
程逻辑设备等的可编程硬件设备的硬件电路实现，也可以用由各种类型的处理器执行的软
件实现，也可以由上述硬件电路和软件的结合例如固件来实现。

[0198] 以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，凡在本发明的精神和原则之内所
作的任何修改、等同替换和改进等，都应涵盖在本发明的保护范围之内。