传统的加密方案仅可以保证传输的数据对被动的窃听者是安全的，但如果窃听者在截获密文后对密文的发送者进行主动的胁迫，迫使其交代出加密时所用的本地随机数以及明文，那么传统方案将无法保证数据的安全。为了解决这一严重安全问题，Canetti等^[1]首次提出了可否认加密技术。可否认加密技术可以赋予加密者任意编造密文所对应明文的能力，使得加密者在受到逼问时可以向逼问者提供一段虚假的明文信息和随机码，可以在同样的加密算法下产生的密文与被截获密文相同。以此令攻击者无法正确区分真正的明文来防止明文的泄露。可否认加密与传统的加密方式的区别是，可以找到不同的明文和随机数加密得到相同的密文。而传统加密在一定意义上相当于对明文的承诺，难以找到不同的明文和随机数加密得到相同的密文，甚至不存在不同的明文和随机数加密得到相同密文。

可否认加密的应用场景十分广泛，比如在电子选举^[2]和电子拍卖等场景中。选民和拍卖者的信息是公开的，那么很有可能存在胁迫投票和交代竞标价格等行为。可否认加密可以杜绝上述行为的产生，其中，Cramer^[3]、Hirt^[4]等研究了可否认加密在电子选举中的应用。

Klonowski等^[5]提出一种基于Elgamal的接收方可否认公钥加密方案。但胁迫者通过胁迫接收方可以得到私钥s和假明文 ${m_{\rm f}}$ ，然后胁迫方会计算哈希值并通过计算得到明文信息，因此该方案有一定缺陷并不满足接收方可否认的定义。

Ibrahim^[6]介绍了一个基于Jacobi符号的发送方公钥可否认方案，但其存在问题如下：一是，它不能从有效明文空间中任意选取明文作为用于欺骗的明文；二是，其安全性是基于不可靠的二次剩余问题（quadratic residual problem，QRP）；三是，其解密过程非常慢，因为要重复计算公钥中的Jacobi符号直至计算出某个公钥位是非二次剩余的。Howlader等^[7]用二次剩余问题构造了一个发送方可否认加密方案，解决了上述问题1，但仍然没能很好地解决问题2和3。之后，Ibrahim^[8]又提出了一种方案，该方案基于中介公钥基础设施（mediated PKI，MPKI），需要一个可信第三方，在加密时需要重复使用不经意传输（oblivious transfer，OT）协议，故其存在加密效率较低的问题。Ibrahim^[6,8]提出的两个方案被认为是具有里程碑意义的，但是它们均不能够抵御量子计算机攻击。

在量子计算机相继攻破RSA、DSA和ECDSA密码后，2016年4月，美国国家标准局（National Institute of Science and Technology，NIST）提出了抗量子密码路线图，定义了密钥交换、公钥加密和数字签名的新标准，在该标准下有望通过格密码构建抗量子的密码体系。目前，还没有研究者能给出一种使用Shor算法攻击格密码的有效算法，主要问题是被经常用于Shor分解算法和相关量子算法的周期性查找技术，并不适用于格问题，因此将格密码作为抗量子密码提供了正确性依据。

目前，国内外很少有研究者提出比较完整的可否认加密方案，而可以抵御量子攻击的可否认加密方案更是少之又少，并且没有关于方案性能的具体分析。本文提出的方案是一个概率性的发送方否认公钥加密方案，对单一比特逐比特加密，通过困难问题LWE问题构造一个密文集合“模糊集”使敌手无法与之于均匀分布集合进行区分。而接收方可以通过私钥正确分辨两个集合，其安全性可规约到格上最短独立向量问题（shortest independent vector problem，SIVP）上。本文提出的方案优势在于可以抵御量子攻击，且不需要可信第三方等额外物理假设。且本文的性能较好，与文献[7]中方案相比加密效率提高了70%，密文膨胀率约减小了3倍。

由于本方案基于LWE问题需要大量的矩阵运算，存在的缺点是计算效率低，密钥较大，密文膨胀率较大，因此本方案不适用于加密较长的明文，而对于选举系统中选民投票的场景或者对密钥等短数据加密有着较好的应用前景。

1 预备知识 1.1 发送方可否认基本概念

可否认加密根据可以进行否认的对象分为发送方、接收方以及双向可否认加密方案。可否认加密还可分为完全否认方案和多分布式否认方案。其中，多分布式否认方案相对于全否认加密方案存在一个正常算法以及一个替代算法。由于替代算法的输出与正常算法相似，因此其看起来似乎是一直在使用规定的算法进行加密。由于多分布式否认方案需要同时构造两个加密算法，全否认加密方案的认可度比多分布式否认方案要高。本文提出的方案为发送方全否认加密方案。

发送方可否认加密使得发送方产生一个虚假的明文 ${m_{\rm{f}}}$ 和虚假的随机数 ${r_{\rm{f}}}$ ，使得加密后的密文 ${\rm{LW}}{{\rm{E}}_{p,\chi }}$ 看起来像是由正确的明文 $m$ 和本地的随机数 $r$ 加密得到的，使得 $Enc({m_{\rm{f}}},{r_{\rm{f}}}) = Enc(m,r)$ 。如果胁迫者强迫发送方提供明文，发送方可以有选择地提供正确的 $m$ 和 $r$ ，或提供虚假的消息 ${m_{\rm{f}}}$ 和 ${r_{\rm{f}}}$ 欺骗胁迫者，因此否认加密可以避免胁迫问题。虽然胁迫者无法辨别发送者提供的明文，但接收方可以通过私钥正确解密，上述行为被称作发送方否认。

1.2 发送方可否认基本构造

根据Canetti等^[1]中提出的可否认加密的概念，考虑发送方S在通信中传给接收方R消息，事先并没有任何信息的交流。那么致力于将消息可否认地传给S而用到的协议 $\Pi $ 应满足：1）接收方以可忽略的错误概率解密出明文；2）对于窃听者来说该协议是语义安全的；3）欺骗者应该有一个欺骗算法 $\phi $ 根据密文 $c$ 、随机数 $r$ 、明文 $m$ 产生用于欺骗的假随机数 ${r_{\rm{f}}}$ 。

正确性：接收者通过解密后得到的明文不同于发送者所加密明文的概率是可忽略的。

安全性：发送方的 $m$ 和 ${m_{\rm{f}}}$ 加密后得到的密文对于敌手而言是计算不可区分的：

$ En{c_\Pi }(m) \approx En{c_\Pi }({m_{\rm{f}}}) $

(1)

可否认性：对于发送方传输的消息 $m$ 、本地随机数 $r$ 、得到的密文 $En{c_\Pi }(m,r)$ 、窃听者可信的明文集合M，存在一个欺骗算法 $\phi $ 使得其可以产生 ${r_{\rm{f}}}$ ，即 ${r_{\rm{f}}} = $ $ \phi (m,r,{m_{\rm{f}}})$ 对于敌手而言：

$En{c_\Pi }(m,r) \approx En{c_\Pi }({m_{\rm{f}}},{r_{\rm{f}}})$

(2)

因此，胁迫的问题可以通过隐藏正确的明文 $m$ 、不诚实的交代虚假明文 ${m_{\rm{f}}}$ 以及随机数 ${r_{\rm{f}}}$ 来解决。

同时，Canetti等^[1]提出了“模糊集”的概念来构造可否认加密方案。假设发送者可以随机地从均匀分布或某些伪随机分布集合（模糊集）中随机的选取一个元素，具有私钥的接收者可以判断该元素是从均匀分布集合或是伪随机分布集合中选取。因此，发送方可以在加密0时发送伪随机元素，加密1时发送随机元素，当受到胁迫时发送方可以声称该元素是从另一个集合中选取的，而胁迫者无法分辨。“模糊集”的密度即模糊集占整个集合的比例应尽量低，否则，需要重复加密多次达到指定误码率。例如，在文献[7]方案中其模糊集的密度为1/2，导致需要重复加密20次才可使得误码率达到百万分之一。

1.3 LWE问题

LWE问题在文献[9]中被提出，对于安全参数 $n$ ，由 $n$ 的多项式生成的素数 $p$ ，考虑下面一组方程组：

$\left\{\!\!\!\! \begin{array}{l} \left\langle {{{s}},{\alpha _1}} \right\rangle { \approx _\chi }{{{b}}_1}(od p), \\ \left\langle {{{s}},{\alpha _2}} \right\rangle { \approx _\chi }{{{b}}_2}(od p), \\ \qquad\quad \vdots \\ \left\langle {{{s}},{\alpha _{\rm{n}}}} \right\rangle { \approx _\chi }{{{b}}_n}(od p) \\ \end{array} \right.$

(3)

式中， ${{{s}} \sim {\rm{U}}}_p^N$ ， ${\alpha _i}$ 相互独立地在模 $p$ 上均匀选取，其中在方程组的每一个方程中引入的噪声 $\chi $ 。对于方程组中的每一个方程 $i$ 有：

${{{b}}_i} = \left\langle {{{s}},{\alpha _1}} \right\rangle + {{{e}}_i}$

(4)

如何从方程组（3）求解向量 ${{s}}$ 就是 ${\rm{LW}}{{\rm{E}}_{p,\chi }}$ 搜索困难问题。1983年，Kanan^[10]提出解决 ${\rm{LW}}{{\rm{E}}_{p,\chi }}$ 问题的算法，其时间复杂度为 ${2^{o(n \cdot {\rm{lb}\;}{\rm{ }}n)}}$ ，而后攻击 ${\rm{LW}}{{\rm{E}}_{p,\chi }}$ 问题的方案被逐渐提出，例如，Bkw、Kannan sieve、Sis sieve、Dec、Dual算法等，这些方案提高了攻击效率。

在Regev^[9]的理论中，说明了对于整数 $n$ 、 $p$ 和 $\alpha = $ $ o(1/\sqrt n {\rm{lb }}\;{\rm{ }}n)$ ，应满足 $\alpha p > 2\sqrt n $ ,如果存在有效的算法解决 ${\rm{LW}}{{\rm{E}}_{p,\chi }}$ 问题，那么，也存在一个有效的量子算法以 $o(n/\alpha )$ 的时间复杂度解决近似最短向量问题的判定问题（GAPSVP）和最短独立向量问题（SIVP）的最坏情况。SVP问题^[11]和SIVP问题是格上主要的两个计算问题。在SVP和SIVP问题中输入的是一组格，目标是找出格上最短的非零向量，目前研究者们没有找到传统算法能在多项式时间内解决SVP和SIVP问题，有些研究者甚至推断没有量子算法在多项式时间内可以解决该问题，仅有的证据是没有已知的量子算法在解决格问题上比传统算法效果更好。目前这也是在量子计算领域最重要的开放问题，因此基于该推断研究者们认为解决 ${\rm{LW}}{{\rm{E}}_{p,\chi }}$ 问题是困难的。Regev^[9]还证明了考虑某连续分布 $\varphi $ 、 ${{\textit{Z}}_p}$ 上的离散分布 $\bar \varphi $ ，若有一个区分算法可以采用不可忽略的概率区分 ${{As}} + {{e}}({{e}} \leftarrow \bar \varphi )$ 和均匀分布 ${\rm U}$ ，那么也存在有效的算法能够解决 ${\rm{LW}}{{\rm{E}}_{p,\bar \varphi }}$ 搜索困难问题，对这两个分布进行区分的难度不亚于解决 ${\rm{LW}}{{\rm{E}}_{p,\bar \varphi }}$ 搜索困难问题的。

2 发送方可否认加密方案 2.1 可否认加密方案

作者在基于LWE问题的公钥加密方案^[9]的基础上进行了改进，根据文献[1]中提出的“模糊集”概念，构造两个不可区分的分布集合，实现了一种发送方可否认公钥加密方案。本方案中，接收方生成公私钥对 ${{pk}} = ({{A}},{{{b}}_p}),{{sk}} = {{s}}$ ，以及素数 ${{p}}$ ，发送方加密时对单比特逐个加密。根据LWE问题中存在的不可区分性质，在已知 ${{A}}$ 和 ${{s}}$ 的情况下，构建一个与均匀分布集合相比元素个数很小的密文“模糊集” ${{A}} \cdot {{s}} + {{e}}$ ，即比特0对应密文的集合。在解密比特0的密文分布（模糊集）时的误码率基本可以忽略。而在解密比特1的密文分布（均匀分布）时，解密结果有一定的概率分布在低密度的“模糊集”中导致误码，因此需要将该模糊集的密度尽量降低。

考虑敌手对发送方进行胁迫，发送方与接收方采用本可否认加密方案，依次进行密钥生成、加解密、验证密文过程的流程图如图1所示。

1）密钥生成

接收方选取安全参数n，随机生成一个 $10{n^2}$ 左右的素数 $p$ ，生成一个m（ $m = (1 + \varepsilon )(n + 1){\rm{lb\;}}p$ ）维整数向量作为噪声 ${{e}}$ ，其元素服从离散高斯分布，分布律为：

$\bar \varphi (i): = \int_{(i - 1/2)/p}^{(i + 1/2)/p} {\varphi (x){\rm{d}}x} $

(5)

式中， $\varphi (x)$ 是由连续高斯分布 ${\rm N}\left(0,\dfrac{{{\alpha ^2}}}{{2\text{π} }}\right)$ 从 $( - \infty ,\infty )$ 区间模压缩到区间 $\bigg[ - \dfrac{1}{2},\dfrac{1}{2}\bigg]$ 得到的概率分布，其表达式如下：

$\varphi (x): = \mathop {\lim }\limits_{M \to \infty } \sum\limits_{ - M}^M {\frac{1}{\alpha }} \cdot \exp \left( - \text{π}{\left(\frac{{x - M}}{\alpha }\right)^2}\right)$

(6)

式中， $\alpha (n) = \dfrac{1}{{\sqrt {2\text{π} } \sigma }} = o\left( {1/\sqrt n {{{\mathop{\rm lb}\nolimits} }^2}(n)} \right)$ ，通常根据精度要求选取正整数 ${{M}}$ 的大小。在保证参数 $\alpha {{p > 2}}\sqrt n $ 的同时，还要保证噪声 ${{e}}$ 的分布不能过于集中且具有一定随机性。通过实验得到不同安全参数 $n$ 下噪声 ${{e}}$ 的离散分布情况，因为 ${{e}}$ 为离散高斯采样，则其分布是正负对称的。表1给出 ${{e}}$ 取不同正数时的离散概率，由表1可知 ${{e}}$ 服从比较平稳的高斯分布。

随机生成一个 $n$ 维整数向量 ${{s}}$ 作为私钥，其元素均服从离散均匀分布 ${\rm U}( - p/2,p/2)$ 。

生成 $m \times ({{n}} + 1)$ 维公钥 ${{pk}} = ({{A}},{{{b}}_p})$ 。公钥pk由 ${{A}}$ 和 ${{{b}}_p}$ 两部分构成具体为，随机生成一个 $m \times n$ 的整数矩阵 ${{A}}$ ，其元素服从均匀分布 ${\rm U}( - p/2,p/2)$ ，以及计算生成的向量 ${{{b}}_p} = {{A}} \cdot {{s}} + {{e }}od p$ 。

算法1 　密钥生成 $Keygen({\rm{\;}})$

1. $ {{{e}}^m} \sim \chi _\eta ^k$ ；

2. $ {{{s}}^n},{{{A}}^{m \times n}} \sim {{\rm U}_p}$ ；

3. $ {{{b}}^m} \leftarrow {{A}} \cdot {{s}} + {{e}}$ ；

4. return $ {{pk}}: = [{{{A}}^{m \times n}},{{{b}}^m}],{{sk}}: = {{{s}}^n}$ 。

2）加密过程

首先，有明文比特流 $U = \{ {u_i}|i = 1,2, \cdots ,L\} $ ，为了降低解密时比特1解密成0情况的误码率，需要对单比特重复加密k次。

当 ${u_j} = 0$ 时，从 $m$ 维0–1均匀整数分布 ${{r}}$ 中随机取一个向量 ${{r}}_j^i$ ，得到密文向量 ${{c}}_j^i = {({ r}_j^i)^{\rm T}} \cdot {{pk}} od p, 1 \le j \le L, $ $1 \le i \le k$ 。此时，如果 ${u_j} = 0$ 则将k个向量 ${{r}}_j^i\left( {1 \le i \le k} \right)$ 依次保存到本地随机数文件R中；否则，不保存。当 ${u_j} = 1$ 时，此时密文的构造方式与Regev^[9]中的方案有所区别，重复k次，并从均匀分布 ${\rm U}( - p/2,p/2)$ 上选取一个 $n + 1$ 维的模 $p$ 向量作为密文 ${{{c}}_{{j}}}{\rm{ = }}{[}{{c}}_j^1{\rm{,}}{{c}}_j^2{\rm{,}} \cdots {\rm{,}}{{c}}_j^k{]}$ 。

算法2 　加密 $ Enc({{pk}} = [{{{A}}^{m \times n}},{{{b}}^m}]{\rm{ }},{\rm{ }}m)$

1. $ {{{r}}^{m + 1}} \sim {{\rm U}_2}$ ；

2. $ {\rm{if}}(m = 0) {\rm{ }}\;\;{{{c}}^{n + 1}_i}: = {{{r}}^{\rm{T}}} \cdot [{{A}},{{b}}]$

重复k次 return $ {{ c}} = [{{{c}}_1},{{{c}}_2}, \cdots ,{{{c}}_k}]$ ；

3. $ {\rm{ if}}(m = 1) {\rm{ }}\;\;{{{c}}^{n + 1}_i} \leftarrow {{\rm U}_p}$

重复k次 return $ {{c}} = [{{{c}}_1},{{{c}}_2}, \cdots ,{{{c}}_k}]$ 。

3）解密过程

接收方通过私钥对密文进行计算得到 ${{c}}_{n + 1}^i - $ $ \left\langle {{{c}}_{1 \sim n}^i \cdot {{s}}} \right\rangle $ ，其中， ${{c}}_{n + 1}^i$ 为密文向量的第 $n + 1$ 位， ${{c}}_{1 \sim n}^i$ 为密文向量的前 $n$ 位。若得到的结果 $|{{r}} \cdot {{e}}| < 6\sigma $ （ $\sigma $ 为变量 ${{r}} \cdot {{e}}$ 的标准差），则记单次解密结果 ${m'_i} = 0$ ；若结果 $|{{r}} \cdot {{e}}| \ge 6\sigma $ ，则记单次解密结果 ${m'_i} = 1$ 。对单比特加密 $k$ 次得到的密文 ${{c}}= [{{{c}}_1},{{{c}}_2}, \cdots ,{{{c}}_k}]$ 中的 ${{{c}}_i}\left( {1 \le {{i}} \le {{k}}} \right)$ 依次解密得到 $[{m'_1},{m'_2}, \cdots ,{m'_k}]$ 。若 ${m'_1} \vee {m'_2} \vee \cdots \vee {m'_k} = 0$ ，则最终的解密结果为0；若 ${m'_1} \vee {m'_2} \vee \cdots \vee {m'_k} = 1$ ，则最终的解密结果为1。本方案中接收方由于有私钥 ${{{s}}^n}$ ，可以正确计算 ${{c}}_{n + 1}^i - \left\langle {{{c}}_{1 \sim n}^i \cdot {{s}}} \right\rangle $ 得到 ${m'_i}$ 最终确定明文 $m$ ，而敌手并不能得到 ${m'_i}$ 进而判断 $m$ 是0或1。

算法3 　解密 $Dec({{sk}} = {{s}},{{c}})$

1. $ {m_i}' = {{c}}_{n + 1}^i - \left\langle {{{c}}_{1 \sim n}^i \cdot { s}} \right\rangle {\rm{ = }}\left| {{{r}} \cdot {{e}}} \right| < 6\sigma ? 0:1$ ；

2. ${\rm{if}}({m'_1} \vee {m'_2} \vee \cdots \vee {m'_k}) = 0{\rm{ }} \; \; {\rm{return}} \; m = 0$ ；

3. $ {\rm{if}}({m'_1} \vee {m'_2} \vee \cdots \vee {m'_k}) = 1 \;\; {\rm{ return}} \; m = 1$ 。

4）编码

若存在一个发送方的胁迫者，发送方可以不诚实地将密文 ${{c}}$ 对胁迫者进行欺骗。当发送方传输比特0时，可以将从密文分布中生成的密文 ${{c}}$ 不诚实地声称为从均匀分布中生成的，而胁迫者无法正确区分两个分布。当发送方加密比特1时，若发送方想将密文欺骗为0，那么敌手会要求发送方提供加密时所用到的本地随机数，而发送方却无法提供，此时无法实现从1至0的否认。

在以往提出的可否认加密方案中，有一部分方案不能做到将明文进行任意的抵赖，比如文献[7]中提出的方案。为了做到将明文可以向任何假明文进行否认，需要将2.1节中提出的单向可否认加密方案改进成既可以将0否认成1也可以将1否认成0的双向可否认加密方案，于是进行如下的明文编码改进：

发送方将发送的信息转化为长度为 $L$ 的明文比特流 $V = \{ {v_j}|j = 1,2, \cdots ,L\} $ ，并从明文空间中选取长度为 $L$ 的假明文比特流 $\widetilde V = \{ {\tilde v_j}|j = 1,2, \cdots ,L\} $ ，对 $V$ 和 $\widetilde V$ 进行异或运算得到长度为L的否认标志比特流 ${V^*} = \{ v_j^*|j = 1,2, \cdots ,L\} $ ，并统计不进行否认的明文比特位数所占比例 $x = P({v^*} = 0|{v^*})$ ，当编码为两比特时应小于1/2。对明文进行可否认编码处理后得到长度为 $2L$ 的明文编码 $U = \{ {u_j}|j = 1,2, \cdots ,2L\} $ 以及假明文编码 $\widetilde U = \{ {\tilde u_j}|j = 1,2, \cdots ,2L\} $ 。

具体的可否认编码方式为：1）对于 ${v_j}$ 和 $v_j^*$ 均为0的比特位，以 $\dfrac{1}{{2x}}$ 的概率编码为 ${u_{2j - 1}}{u_{2j}} = 00$ ，其余编码为 ${u_{2j - 1}}{u_{2j}} = 11$ ，为了抵抗统计攻击，保证01的数量占50%；2）对于 ${v_j}$ 和 $v_j^*$ 均为1的比特位，编码为 ${u_{2j - 1}}{u_{2j}} = $ $ 01$ ；3）对于 ${v_j}$ 为0， $v_j^*$ 为1的比特位，编码为 ${u_{2j - 1}}{u_{2j}} = 00$ ；4）对于 ${v_j}$ 为1， $v_j^*$ 为0的比特位，编码为 ${u_{2j - 1}}{u_{2j}} = 01$ ；5）综上得到明文编码 ${{U}}$ 。6）将明文编码 ${{U}}$ 中，对应 ${v_j} = 1$ 和 $v_j^* = 1$ 的编码替换为 ${u_{2j - 1}}{u_{2j}} = 11$ ，对应 ${v_j} = 0$ 和 $v_j^* = 1$ 的编码替换为 ${u_{2j - 1}}{u_{2j}} = 01$ ，其余不变，得到假明文编码 ${{{{\widetilde U}} }}$ 。

若接收方在解密后得到的两比特明文中有偶数个比特为0时，最终的解码结果为0；若解密后得到的明文中有奇数个比特1时，最终的解码结果为1。将单个明文比特编码为两明文比特的编码方式如图2所示。

2.2 实用性分析

对每一比特编码为两位，可以适用于不足一半的明文比特流需要否认的情况，若超过一半则 ${{\widetilde U}}$ 中的11比特会超过25%（完全诚实情况下11比特占25%），敌手通过统计11比特所占比例可以发觉欺骗的存在。在实际应用中，例如，使用ASCII码传输字母，若发生最坏情况则要对每一个字母都进行否认，考虑a～z的ASCII码为97～122，对应的比特串为01100001～01111010。那么继续考虑最坏的情况，任取两个字母的比特串表示中最多有4个对应比特位不相同，需要进行欺骗的比特位数少于总比特位数的一半。因此，对每一比特编码为两位，可以对英文字母以及简单的标点符号进行完全的抵赖，这对于发文档、邮件等常用情景是完全适用的，敌手也不会察觉存在欺骗。

若要进行欺骗的明文比特超过一半，比如传输数据或者图片的情况，也可将每比特编码为更多位数，例如，编码为3位可以满足75%的明文比特进行欺骗，编码为4位可以满足87.5%的明文比特进行欺骗，该比例随编码位数增长。编码方式也可以递推，如将两位编码扩展至3位编码的方式如图3所示。

图3中，3比特的明文编码方式与图2中两比特的明文编码方式类似。为了抵抗敌手进行统计攻击，需进行适当调整，使得001、111编码的数量各占1/4，110、101、000的数量各占1/32，011占13/32。

通过上述方式的改进完成了本方案的双向可否认功能，首先接收方设定安全参数并生成公私钥对，发送方获得公钥对明文进行编码。然后，对明文编码加密并生成保留本地随机数文件，当受到胁迫时向胁迫方交代假明文编码及随机数文件并通过验证。

3 理论分析

对方案的可否认性、安全性、正确性、密文的膨胀率以及算法复杂度进行讨论。

3.1 可否认性

针对在解密时是否需要进行否认，对诚实和不诚实两种情况分别进行如下说明：

1） 诚实的情况

在发送方对比特0进行加密时，即对明文编码00或者11进行加密；接收方解密后会得到00或者11，由此接收方会最终解密成0。在发送方对比特1进行加密时，即对明文编码01进行加密；接收方解密后会得到比特01，由此接收方会最终解密成1。

2） 不诚实的情况

在发送方对比特0进行加密并要进行欺骗时，即对明文编码00进行加密，接收方解密后会得到00，但发送方会欺骗敌手是对明文编码01进行加密，而敌手却无法区分，最终迫使敌手相信发送方发送的是比特1。在发送方对比特1进行加密并要进行欺骗时，即对明文编码00进行加密，但发送方会欺骗敌手是对明文编码11进行加密，而敌手却无法区分，最终迫使敌手相信发送方发送的是比特0。

3.2 安全性

在 ${\rm{LW}}{{\rm{E}}_{p,\chi }}$ 困难问题假设下，本文提出的方案是IND–CPA安全的。

使用基于Game的证明方法证明本方案的安全性，并用 ${\rm{Adv}}{_{{\rm{Game}}0}}[{\cal{A}}]$ 表示敌手在本方案中的优势。证明过程分为如下3个Game：

1） 对于Game0

Game0是标准的IND–CPA游戏，在敌手经过训练后，挑战者按照密钥生成过程生成公钥 ${{pk}}: = ({{A}},{{b}})$ 及私钥 ${{sk}}: = {{s}}$ 。敌手获得挑战者生成的公钥 ${{pk}}$ ，然后从明文空间中选取两个明文 ${{{m}}_0}$ 和 ${{{m}}_1}$ ，发送给挑战者，挑战者k随机选取 $b \in (0,1)$ ，并依照加密过程对 ${m_b}$ 进行加密，将加密结果 ${{{c}}_b}$ 发送给敌手，敌手对得到的密文 ${{{c}}_b}$ 进行猜测得到明文输出 $b$ ，如果 $b' = b$ 则敌手攻击成功，敌手 ${\cal{A}}$ 的优势记为 ${\rm{Adv}}{_{{\rm{CPA}}}}[{\cal{A}}] = \bigg|{\rm Pr}[b = b' \;{\rm{in}} \;{\rm{Game}}0] - \dfrac{1}{2}\bigg|\text{。}$

2） 对于Game1

Game1改变Game0的公钥 ${{b}}: = {{As}} + {{e}}$ 的生成过程，改成随机均匀选取 ${{b}}' \leftarrow {{\rm U}_q}$ ，敌手区分 ${{b}}'$ 是否等于 ${{As}} + {{e}}$ 与 ${\rm{LW}}{{\rm{E}}_{p,\chi }}$ 问题一样困难，所以Game1与Game0中敌手的优势差为：

$ |\Pr (b = b' \;{\rm{ in}} \;{\rm{Game}}1 - \Pr (b = b' \;{\rm{ in}}\;{\rm{ Game}}0)| \le {\rm{Adv}}{_{{\rm{LWE}}}}({{\cal A}}) \text{。} $

3） 对于Game 2

Game2改变Game 1的挑战密文的生成方式，使用均匀随机选取密文 ${{c}}'$ 的方式替代加密比特0时所用方式，敌手区分这两种密文与 ${\rm{LW}}{{\rm{E}}_{p,\chi }}$ 问题一样困难，所以Game2与Game1中敌手的优势差为：

$ |\Pr (b = b'\;{\rm{ in}}\;{\rm{ Game}}2) - \Pr (b = b'\;{\rm{ in}}\;{\rm{Game}}1)| \le {\rm{Adv}}{_{{\rm{LWE}}}}({{\cal A}}) \text{。} $

由于Game2挑战的密文与明文 $b$ 相互独立所以有： $\Pr (b = b' \;{\rm{ in}} \;{\rm Game2}) = \dfrac{1}{2}$ ；则有：

$ \begin{aligned}[b] {\rm{Adv}}{_{{\rm{CPA}}}}[{{\cal A}}] \!\!=& |\Pr (b = b'\;{\rm{ in}}\;{\rm{Game}}1) \!-\! \Pr (b = b'\;{\rm{ in}}\;{\rm{Game}}0)| + \\ &|\Pr (b = b'\;{\rm{ in}}\;{\mathop{\rm Game}\nolimits} 2) \!-\! \Pr (b = b'\;{\rm{ in}}\;{\rm{Game}}1)| \le \\ &2{\rm{Adv}}{_{{\rm{LWE}}}}({{\cal A}})\text{。} \end{aligned} $

在 ${\rm{LW}}{{\rm{E}}_{p,\chi }}$ 问题是困难问题的假设下， ${\rm{Adv}}{_{{\rm{LWE}}}}({\cal{A}})$ 可以忽略不计。

因此证明本方案是IND–CPA安全的。

3.3 正确性

通过构造“模糊集”，解密明文0时得到的结果 ${m'_i}{ = {{c}}}_{n + 1}^i - \left\langle {{{c}}_{1 \sim n}^i \cdot {{s}}} \right\rangle { ={{ r}}} \cdot {{e}}$ ，是m个独立同分布变量 $r \cdot e \sim $ ${\rm N}\bigg(0,{\bigg(\dfrac{1}{{\sqrt {2\text{π} } \alpha (n)}}\bigg)^2}\bigg)$ 之和。通过中心极限定理可知 ${{r}} \cdot {{e}}$ 近似服从正态分布，即 ${{r}} \cdot {{e}} \sim {\rm N}\bigg(0,m{\bigg(\dfrac{1}{{\sqrt {2\text{π} } \alpha (n)}}\bigg)^2}\bigg)$ 。然后，将门限值设为6倍标准差 $\dfrac{{6\sqrt m }}{{\sqrt {2\text{π} } \alpha (n)}}$ ，使得 ${{r}} \cdot {{e}}$ 分布在该门限值内的概率为 $6\sigma $ （即将0解密成0的概率），即约为 $1 - {10^{ - 9}}$ 。此外，可以得到“模糊集”占整个均匀分布的比例（即将1单次解密成0的概率 $P = \dfrac{1}{{0.5p/6\sigma }}$ ）。选取参数 ${{m}} = 1.1(n + 1){\rm{lb}} \;p,\alpha (n) = 1/(10\sqrt n {{\rm{lb}} ^2}(n))$ 对本方案进行实现，实现中使用2.1节中的编码方式对明文的每一个比特编码为两个比特，接收方的解密为：

$ {{m}} = ({m_{11}} \vee {m_{12}} \vee \cdots \vee {m_{1k}}) \oplus ({m_{21}} \vee {m_{22}} \vee \cdots \vee {m_{2k}})\text{。} $

通过实现得到在不同安全参数下门限值的取值和单次解密的误码率，如表2所示。

由表2可知，对单比特的单次解密误码率较高，与本节中的理论分析相符，需要多次进行重复加密降低误码率。由于对单比特0而言，将其错误解码成1的概率约有十亿分之一，因此可近似将其忽略。而将1错误解码成0的概率可以考虑为将明文编码01中最后一位1错误解码为0，其概率为 ${P^k}$ ， $k$ 为重复加密的次数。将0错误解码成1的概率可以考虑为将明文编码11中最后一位1错误的解码为0，其概率同样为 ${P^k}$ 。这意味着在加密比特1时，为了达到不同需求的误码率可以重复对每一位编码后的比特加密4～5次或者更多次。

考虑接收方对编码后的单个比特1对应的密文进行解密时的误码率约为1/30，用简单的重复加密会降低误码率。为了继续减少重复的加密次数以提高加密效率，采用信道编码的方式对密文添加冗余并进行自纠错，因此找到一种合理的编码方式可以进一步提高本方案的加密效率。

3.4 复杂度

由公钥 ${{pk}} = ({{A}}|{{{b}}_p})$ ，及3.3节中选取的参数可知公钥的长度为 $1.1{(n + 1)^2}{\rm{l}} {{\rm{b}}^2}(10{n^2})$ 。对于每一明文比特在编码后要进行8次重复加密，每次得到密文为 ${{{c}}^{{i}}} = {({{{r}}^i})^{\rm{T}}} \cdot$ $ {{pk }}od p$ ， $0 < i \le 8 $ ，可知密文膨胀率为 $8({{n}} + 1){\rm{lb}}(10{{{n}}^2)}$ ，因此本方案和以往提出的可否认加密方案一样，密钥长度及膨胀率较大。由于在对比特1加密时直接生成模p的向量，其加密时间相比于对比特0的加密时间可以忽略，可直接考虑对比特0加密的时间复杂度。

本方案在不同过程中分别需要对 ${{\textit{Z}}_p}$ 上的整数做乘法运算，在计算时间复杂度时将 ${{\textit{Z}}_p}$ 上两个整数之间的乘法运算计算量记为常数c。给出不同过程中的时间复杂度和空间复杂度，如表3所示。

从表3中可以看出，解密过程的时间复杂度远低于加密过程的时间复杂度，与加密过程相比密钥生成及解密过程的计算量基本可以忽略不计。

4 实验结果及分析 4.1 加解密效率

为了得到第2节中作者提出的可否认加密方案的加密效率，选用参数 $p = 10{n^2}$ ， ${{m}} = 1.1(n + 1){\rm{lb}}\; p,\alpha (n) = $ $ 1/(10\sqrt n {{\rm{lb}} ^2}(n))$ ，通过Mac2017（2.3 GHz Intel Core i5 内存8 GB）采用C++语言对引入编码方案后的可否认加密方案进行实现。对100 MB随机选取的比特流重复进行加解密实验，通过实验得到本方案在不同安全参数下加密及解密256比特所占用内存及加解密所需的平均时间，如表4所示。

通过表4可以发现，在不同安全参数下解密时间相比于加密时间基本可以忽略，且内存占用较小。

4.2 方案对比

文献[7]为基于二次剩余构造的单比特可否认加密方案，是对文献[6]方案的改进，且该方案的可行性得到学术界广泛认可，因此将文献[7]中的方案与本方案进行对比。在同等安全程度下，对比公钥长度、加解密效率和密文膨胀率等性能。

1） 解密效率对比

为了保证文献[7]中提出的可否认加密方案的安全性，目前普遍选取512位的私钥p和q。在攻击该方案时，需要对其基于的二次剩余困难问题中的大整数N进行分解。使用Bai等提出的普通数域筛选法（GNFS）进行分解，根据该分解算法的时间复杂度 $\exp [c \cdot {({\rm{lb }}\;n{\rm{)}}^{{\rm{1/3}}}}{\rm{(lb (lb }}\;n){\rm{)}}{{\rm{ }}^{2/3}}]$ （ $n$ 为 $p \cdot q$ 的位数）可知，此时该方案可以抵御 ${2^{75}}$ 次计算的攻击^[12]，针对目前计算机的算力是较为安全的。

对文献[7]中方案进行分析，该方案在加解密时需要重复计算雅各比符号，通过欧几里德算法计算雅各比符号的时间复杂度 $O({\rm{l}}{{\rm{b}}^2}(n))$ （ $n$ 为p和q的位数）。在保证误码率低于两百万分之一的条件下：该方案加密比特1时平均每比特明文要进行2次雅各比符号计算，加密比特0时的时间可以忽略，因此平均加密每个明文比特的明文计算次数为 $\dfrac{1}{2} \times 2 \times 1{\rm{ }}\;{024^2}$ 。该方案在解密0时需要重复计算21次，解密1时需要重复计算2次，得到平均解密每个明文比特的计算次数为 $\dfrac{1}{2} \times \left( {21 + 2} \right) \times {512^2}$ 。

对于作者提出的可否认加密方案，在bitbucket LWE安全程度测试中得到：使用dual算法^[13]进行攻击时，为了能够抵御 ${2^{75}}$ 次的计算机计算， $n$ 需要取为180。此时本方案平均每个明文比特的加密次数为 $\dfrac{1}{2} \times 8{\left( {n + 1} \right)^2}{\rm{lb }}\;p$ ，具体为 $4 \times {(180 + 1)^2}{\rm{lb }}\;324 \;{\rm{ }}000$ 。因此本方案的加解密效率是文献[7]中方案的1.7倍。

2） 密文膨胀率及误码率对比

特别地，当选取平衡安全性以及加密效率后安全参数 $n = 180$ ，对每一位明文比特编码重复加密4次时，单比特的误码率约为 $4.8 \times {10^{ - 7}}$ ；重复加密5次时，误码率约为 $1.25 \times {10^{ - 8}}$ 。而文献[7]方案中所使用的模糊集密度较大，达到 $4.8 \times {10^{ - 7}} $ 的误码率需要重复加密21次，使得密文膨胀率较高。

根据3.4节中给出的本方案的密文膨胀率为 $8({{n}} + 1){\rm{lb}}(10{{{n}}^2})$ ，可知本方案在 $n$ =180时密文膨胀率约为1∶33 000，本方案的误码率与密文膨胀率均与3.4节中的理论分析相符合。在同等安全程度下，由于文献[7]中方案需要通过私钥重复计算雅各比符号及进行多次异或操作，使得密文膨胀率大约高达1∶100 000。下面给出本方案和文献[7]方案抗 ${2^{75}}$ 次攻击时的性能对比，如表5所示。

通过表5可知：与文献[7]方案相比，本方案的缺点在于公钥长度较长，仅适用于加密较短的明文；但是，在加解密效率和密文膨胀率上有明显优势，加密效率提高了70%，密文膨胀率约减小了3倍。

5 结　论

基于模糊集的概念，提出了一种可以抵御量子攻击的发送方可否认公钥加密方案。通过LWE问题构造了一个低密度的模糊集，使得重复加密的次数大大降低，进而降低了密文膨胀率提高了加密效率。为了使原明文可以抵赖为任意的假明文，还提出了一种编码方案使得明文比特0和1之间可以相互进行否认。通过理论分析得到了安全性、正确性以及时空复杂度。通过实验得到了本方案的加密效率约为72 B/s，密文膨胀率约为1∶33 000，适用于对短密钥进行加密的应用场景。与文献[7]中方案进行对比，本方案虽然在公钥长度上有所缺陷，但在抗量子攻击、加解密效率、密文膨胀率上有明显优势。

后续研究工作如下：一是，可以对简单重复加密的方式进行改进，用信道编码的方式对密文进行长码的编码，实现解密出现误码时的自纠错以提高效率；二是，有望构造一个基于模容错学习问题（MLWE）的可否认加密方案，将加密效率大幅提升。