DOI: 10.12677/CSA.2023.1310193, PDF, HTML, XML,  被引量   
作者: 李明祥：河北金融学院金融研究所，河北 保定
关键词: 全同态加密；无证书；LWE问题；LWR问题；随机预言机模型；Fully Homomorphic Encryption； Certificateless； LWE Problem； LWR Problem； Random Oracle Model

文章引用：李明祥. 基于LWR问题的无证书全同态加密方案[J]. 计算机科学与应用, 2023, 13(10): 1948-1964. https://doi.org/10.12677/CSA.2023.1310193

1. 引言

全同态加密(Fully Homomorphic Encryption, FHE)是一种具有特殊性质的公钥加密体制。它能在不解密的情形下对密文数据进行任意计算，即 $\text{Dec}\left(f\left(\text{Enc}\left({\mu }_1\right),\cdots ,\text{Enc}\left({\mu }_{\mathcal{l}}\right)\right)\right)=f\left({\mu }_1,\cdots ,{\mu }_{\mathcal{l}}\right)$ ，其中f为任意函数。2009年Gentry [1] 基于理想格提出了第一个全同态加密方案。Genry开拓性的工作迅速掀起了全同态加密研究的浪潮。2013年Gentry、Sahai和Waters [2] 提出了一种构造全同态加密方案的新技术，他们称之为近似特征向量技术。Gentry、Sahai和Waters [2] 利用近似特征向量技术，基于带误差学习(Learning with Errors, LWE)问题 [3] 构造了一个层次型全同态加密(leveledFHE)方案。在层次型全同态加密方案中，方案的参数取决于方案所能计算的电路深度。利用Gentry [1] 提出的自举技术可以把层次型全同态加密方案转换为全同态加密方案。本文的工作专注于层次型全同态加密方案，故在下文的叙述中经常省去“层次型”一词。

无证书加密(Certificateless Encryption, CLE) [4] 是一种新型公钥加密体制。它消除了基于身份的加密(Identity-Based Encryption, IBE) [5] 固有的密钥托管问题，同时，它也避免了传统公钥加密系统中的公钥证书管理问题。无证书全同态加密(Certificateless Fully Homomorphic Encryption, CLFHE)结合了全同态加密和无证书加密两者的优势，它引起了人们的研究兴趣。2017年Chen等人 [6] 利用近似特征向量技术，基于LWE问题提出了一个无证书全同态加密方案，并在随机预言机模型下证明了它满足IND-CPA安全性。最近，Li [7] 利用近似特征向量技术，基于LWE问题又提出了一个在随机预言模型下可证明安全的无证书全同态加密方案和一个在标准模型下可证明安全的无证书全同态加密方案。

带舍入学习(Learning with Rounding, LWR)问题 [8] 是LWE问题 [3] 的变形。LWE问题需要进行高斯噪声抽样。高斯噪声抽样的计算开销非常大，严重制约了基于LWE问题的全同态加密方案的计算性能。LWR问题不需要进行高斯噪声抽样。近几年来，人们基于LWR问题构造了几个全同态加密方案 [9] [10] 。与Gentry、Sahai和Waters [2] 提出的基于LWE问题的全同态加密方案相比，这些全同态加密方案 [9] [10] 由于舍弃了计算代价高昂的高斯噪声抽样其计算效率有了很大提高。截至目前，人们尚未提出基于LWR问题的无证书全同态加密方案。

鉴于无证书全同态加密的研究现状，本文致力于基于LWR问题的无证书全同态加密方案的设计与分析。首先，利用Gentry、Sahai和Waters [2] 提出的近似特征向量技术，基于LWR问题设计了一个无证书全同态加密方案。其次，在随机预言机模型下证明了所设计的方案满足INDr-CPA安全性。INDr-CPA比IND-CPA的安全性更强，它包括IND-CPA安全性和接收方匿名性。最后，本文具体给出了所设计的方案的系统参数设置。相比于现有的基于LWE问题的无证书全同态加密方案 [6] [7] ，本文所设计的方案省掉了耗时的高斯噪声抽样，其计算效率更高。

2. 预备知识

2.1. 符号约定

下面介绍本文的符号约定，如表1所示。

2.2. 格

下面简单介绍一下格理论，详细内容可参阅 [11] 。

定义1 设 $B=\left\{b_1,\cdots ,b_m\right\}\subset {ℝ}^n$ 是一组线性无关向量，格 $\Lambda$ 定义为

$\Lambda =\left\{x\in {ℝ}^n:\exists c\in {\mathbb{Z}}^m,x=Bc={\displaystyle {\sum }_{i=1}^m{c}_i{b}_i}\right\}$ ,

其中 $B$ 称为 $\Lambda$ 的一组基。这里，n为 $\Lambda$ 的维数，m为 $\Lambda$ 的秩，且 $m\le n$ 。在 $m=n$ 时， $\Lambda$ 称为满秩格。

定义2 对正整数q、矩阵 $A\in {\mathbb{Z}}_q^{n\times m}$ 和向量 $u\in {\mathbb{Z}}_q^n$ ，定义m维满秩整数格：

${\Lambda }^{\perp }\left(A\right)=\left\{e\in {\mathbb{Z}}^m:Ae=0\mathrm{mod}q\right\}$

${\Lambda }_u^{\perp }\left(A\right)=\left\{e\in {\mathbb{Z}}^m\text{:}Ae=u\mathrm{mod}q\right\}$ .

可以看出，如果 $t\in {\Lambda }_u^{\perp }\left(A\right)$ ，则 ${\Lambda }_u^{\perp }\left(A\right)={\Lambda }^{\perp }\left(A\right)+t$ 。即 ${\Lambda }_u^{\perp }\left(A\right)$ 是 ${\Lambda }^{\perp }\left(A\right)$ 的陪集。

定义3 对任意的向量 $c\in {ℝ}^n$ 和实数 $\sigma >0$ ， ${ℝ}^n$ 上高斯函数定义为

$\forall x\in {ℝ}^n$ , ${\rho }_{\sigma ,c}\left(x\right)=\exp \left(-\pi {\Vert x-c\Vert }^2/{\sigma }^2\right)$ ,

它以 $c$ 为中心，以 $\sigma$ 为参数。

对任意的向量 $c\in {ℝ}^n$ 、实数 $\sigma >0$ 以及n维格 $\Lambda$ ， $\Lambda$ 上的离散高斯分布定义为

$\forall x\in \Lambda$ , $D_{\Lambda ,\sigma ,c}=\frac{{\rho }_{\sigma ,c}\left(x\right)}{{\rho }_{\sigma ,c}\left(\Lambda \right)}=\frac{{\rho }_{\sigma ,c}\left(x\right)}{{\displaystyle {\sum }_{x\in \Lambda }{\rho }_{\sigma ,c}\left(x\right)}}$ .

当下标 $\sigma$ 和 $c$ 的值分别为1和 $0$ 时，可省去不写。

2.3. 格上的算法

引理1 ( [12] ) 令 $\delta >0$ 为任意固定常数。存在概率多项式时间算法 $\text{TrapGen}\left(n,q\right)$ ，它输入正整数n、 $q\ge 2$ 和 $m\ge \left(5+3\delta \right)\cdot n\log q$ ，输出 $A\in {\mathbb{Z}}_q^{n\times m}$ 和 $T\in {\mathbb{Z}}^{m\times m}$ ，并满足以下条件：① $A$ 的分布统计接近 ${\mathbb{Z}}_q^{n\times m}$ 上的均匀分布，② $T$ 为 ${\Lambda }^{\perp }\left(A\right)$ 的一组基，③ $\Vert \tilde{T}\Vert \le O\left(\sqrt{n\log q}\right)$ 。

引理2 ( [13] ) 存在概率多项式时间算法 $\text{SamplePre}\left(A,T_A,u,\sigma \right)$ ，它输入矩阵 $A\in {\mathbb{Z}}_q^{n\times m}$ 、 ${\Lambda }^{\perp }\left(A\right)$ 的一组基 $T_A$ 、向量 $u\in {\mathbb{Z}}_q^n$ 和参数 $\sigma \ge \Vert {\tilde{T}}_A\Vert \cdot \omega \left(\sqrt{\log m}\right)$ ，其中 $q\ge 2$ ， $m>n$ ，输出向量 $e\in {\mathbb{Z}}^m$ ，并且 $e$ 的分布统计接近分布 $D_{{\Lambda }_u^{\perp }\left(A\right),\sigma }$ 。

引理3 ( [13] ) 令n和q为正整数，且q为素数，令 $m\ge 2n\log q$ 。则对几乎所有的 $A\in {\mathbb{Z}}_q^{n\times m}$ 以及任意的 $\sigma \ge \omega \left(\sqrt{\log m}\right)$ ， $u=A\cdot e\mathrm{mod}q$ 的分布统计接近 ${\mathbb{Z}}_q^n$ 上的均匀分布，其中 $e\leftarrow D_{{\mathbb{Z}}^m,\sigma }$ 。

引理4 ( [14] ) 对任意n维格 $\Lambda$ 、向量 $c\in {ℝ}^n$ 以及实数 $0<\epsilon <1$ 和 $\sigma \ge {\eta }_{\epsilon }\left(\Lambda \right)$ ，有

$\underset{x\leftarrow D_{\Lambda ,\sigma ,c}}{\mathrm{Pr}}\left[\Vert x-c\Vert >\sigma \sqrt{n}\right]\le \frac{1+\epsilon }{1-\epsilon }\cdot 2^{-n}$ ,

其中 ${\eta }_{\epsilon }\left(\Lambda \right)$ 是光滑参数。对 $\Lambda$ 的任意一组基 $B$ ，有 ${\eta }_{\epsilon }\left(\Lambda \right)\le \Vert \tilde{B}\Vert \cdot \omega \left(\sqrt{\log n}\right)$ 。

2.4. 困难问题

定义4 令 $\lambda$ 为安全参数，令 $n=n\left(\lambda \right)$ 和 $q=q\left(\lambda \right)$ 为整数，令 $\chi =\chi \left(\lambda \right)$ 为 $\mathbb{Z}$ 上的概率分布。 ${\text{LWE}}_{n,q,\chi }$ 问题可叙述为：对任意 $m=\text{poly}\left(n\right)$ ，令 $A\leftarrow {\mathbb{Z}}_q^{n\times m}$ ， $s\leftarrow {\mathbb{Z}}_q^n$ ， $e\leftarrow {\chi }^m$ ， $u\leftarrow {\mathbb{Z}}_q^m$ ， $\left(A,A^{\text{T}}\cdot s+e\right)$ 和 $\left(A,u\right)$ 是计算不可区分的。

定义5 对整数上的分布系集 ${\left\{{\chi }_n\right\}}_{n\in \mathbb{N}}$ ，如果 ${\mathrm{Pr}}_{e\leftarrow {\chi }_n}\left[\left|e\right|>B\right]=\text{negl}\left(n\right)$ ，则称分布系集 ${\left\{{\chi }_n\right\}}_{n\in \mathbb{N}}$ 是B有界的。

引理5 ( [3] [15] ) 对任意 $\epsilon >0$ ，存在 $q=q\left(n\right)\le 2^n$ 、 $\chi =\chi \left(n\right)$ 和 $B=B\left(n\right)$ ，且 $\chi$ 是B有界的， $q/B\ge 2^{n^{\epsilon }}$ ，使得 ${\text{LWE}}_{n,q,\chi }$ 至少和 ${\text{GapSVP}}_{\gamma }$ 的经典困难性以及 ${\text{SIVP}}_{\gamma }$ 的量子困难性一样困难，其中 $\gamma =2^{\Omega \left(n^{\epsilon }\right)}$ 。

定义6对整数q和p，且 $q\ge p\ge 2$ ，取整函数 ${〚\cdot 〛}_p$ 定义为 ${〚\cdot 〛}_p:{\mathbb{Z}}_q\to {\mathbb{Z}}_p:x\mapsto 〚\frac{p}{q}\cdot x〛$ 。通过逐项处理，可把 ${〚\cdot 〛}_p$ 扩展到 ${\mathbb{Z}}_q$ 上的向量或矩阵。

定义7令 $\lambda$ 为安全参数，令 $n=n\left(\lambda \right)$ 、 $q=q\left(\lambda \right)$ 和 $p=p\left(\lambda \right)$ 为整数，且 $q\ge p\ge 2$ ， ${\text{LWR}}_{n,q,p}$ 问题可叙述为：对任意 $m=\text{poly}\left(n\right)$ ，令 $A\leftarrow {\mathbb{Z}}_q^{n\times m}$ ， $s\leftarrow {\mathbb{Z}}_q^n$ ， $u\leftarrow {\mathbb{Z}}_p^m$ ， $\left(A,{〚A^{\text{T}}\cdot s〛}_p\right)$ 和 $\left(A,u\right)$ 是计算不可区分的。

引理6 ( [8] ) 令 $\chi$ 是 $\mathbb{Z}$ 上可有效抽样的B有界分布，令 $q\ge p\cdot B\cdot n^{\omega \left(1\right)}$ ，则求解任一分布上 $s\in {\mathbb{Z}}_q^n$ 的 ${\text{LWR}}_{n,q,p}$ 问题，至少与求解同一分布上 $s\in {\mathbb{Z}}_q^n$ 的 ${\text{LWE}}_{n,q,\chi }$ 问题的一样困难。

3. CLFHE的定义及安全模型

3.1. 定义

CLFHE由系统参数生成Setup、部分私钥抽取Extract、公私钥生成KeyGen、加密Encrypt、解密Decrypt和密文计算Eval六个多项式时间算法组成。其中Setup和Extract算法由密钥生成中心(Key Generation Center, KGC)执行。

$\text{Setup}\left(1^{\lambda },1^L\right)$ ：输入安全参数 $\lambda$ 和电路深度L，输出系统主公钥mpk和主私钥msk。

$\text{Extract}\left(mpk,msk,id\right)$ ：输入主公钥mpk、主私钥msk和身份 $id\in {\left\{0,1\right\}}^{\ast }$ ，输出身份id的部分私钥 $d_{id}$ 。 $\text{KeyGen}\left(mpk,id,d_{id}\right)$ ：输入主公钥mpk、身份id和部分私钥 $d_{id}$ ，输出用户的公钥 $p{k}_{id}$ 和私钥 $s{k}_{id}$ 。

$\text{Encrypt}\left(mpk,id,p{k}_{id},\mu \right)$ ：输入主公钥mpk、接收方身份id、接收方公钥 $p{k}_{id}$ 以及消息 $\mu \in \mathcal{M}$ ，这里 $\mathcal{M}$ 为消息空间，输出密文 $c\in \mathcal{C}$ 或错误标识 $\perp$ ，这里 $\mathcal{C}$ 为密文空间。

$\text{Decrypt}\left(mpk,s{k}_{id},c\right)$ ：输入主公钥mpk、接收方私钥 $s{k}_{id}$ 以及密文 $c\in \mathcal{C}$ ，输出消息 $\mu \in \mathcal{M}$ 或错误标识 $\perp$ 。

$\text{Eval}\left(mpk,id,f,c_1,\cdots ,c_{\mathcal{l}}\right)$ ：输入主公钥mpk、身份id、电路 $f:{\mathcal{M}}^{\mathcal{l}}\to \mathcal{M}$ 和身份id下的一组密文 $\left\{c_1,\cdots ,c_{\mathcal{l}}\right\}$ ，输出密文 $c_f\in \mathcal{C}$ 。

CLFHE应满足正确性约束。即

假定 $\left(mpk,msk\right)\leftarrow \text{Setup}\left(1^{\lambda },1^L\right)$ ， $d_{id}\leftarrow \text{Extract}\left(mpk,msk,id\right)$ ， $\left(p{k}_{id},s{k}_{id}\right)\leftarrow \text{KeyGen}\left(mpk,id,d_{id}\right)$ ，则对全部 $c_f\leftarrow \text{Eval}\left(mpk,id,f,c_1,\cdots ,c_{\mathcal{l}}\right)$ ，其中 $f:{\mathcal{M}}^{\mathcal{l}}\to \mathcal{M}$ ， ${\left\{c_i\leftarrow \text{Encrypt}\left(mpk,id,p{k}_{id},{\mu }_i\right)\right\}}_{i\in \left\{1,\cdots ,\mathcal{l}\right\}}$ ，都有 $\text{Decrypt}\left(mpk,s{k}_{id},c_f\right)=f\left({\mu }_1,\cdots ,{\mu }_{\mathcal{l}}\right)$ 。

3.2. 安全模型

我们这里给出INDr-CPA的安全定义。INDr-CPA比IND-CPA的安全性更强。INDr-CPA包括IND-CPA安全性和接收方匿名性。CLFHE的攻击者分为两类，即第1类攻击者 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 和第2类攻击者 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 。 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 模拟外部攻击者，允许它替换用户的公钥。 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 模拟诚实但好奇的KGC，不允许它替换用户的公钥。

攻击者 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 的INDr-CPA安全游戏如下：

初始化：挑战者产生 $\left(mpk,msk\right)\leftarrow \text{Setup}\left(1^{\lambda },1^L\right)$ 。并把主公钥mpk发送给 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 。

阶段1： ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 可查询公钥询问(request public key)、公钥替换(replace public key)和部分私钥抽取(extract partial private key)预言机。

公钥询问预言机：输入身份id，它利用KeyGen和Extract产生公钥 $p{k}_{id}$ ，并返回 $p{k}_{id}$ 。同时它把身份id和它的 $p{k}_{id}$ 记载下来。

公钥替换预言机：输入身份id和公钥 $p{k^{\prime }}_{id}$ ，它修改身份id的有关记载，这以后id关联的公钥为 $p{k^{\prime }}_{id}$ 。部分私钥抽取预言机：输入身份id，它产生部分私钥 $d_{id}\leftarrow \text{Extract}\left(mpk,msk,id\right)$ ，并返回 $d_{id}$ 。

${\mathcal{A}}_{\mathrm{Ⅰ}}$ 结束查询输出目标身份 $i{d}^{\ast }$ 和消息 $\mu$ 。

挑战：挑战者随机选择 $b\leftarrow \left\{0,1\right\}$ 和密文 $c\leftarrow \mathcal{C}$ 。若 $b=0$ ，设置挑战密文 $c^{\ast }=\text{Encrypt}\left(mpk,i{d}^{\ast },p{k^{\prime }}_{i{d}^{\ast }},\mu \right)$ ，其中 $p{k^{\prime }}_{i{d}^{\ast }}$ 是 $i{d}^{\ast }$ 当前关联的公钥；若 $b=1$ ，设置挑战密文 $c^{\ast }=c$ 。挑战者把 $c^{\ast }$ 发送给 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 。

阶段2： ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 继续查询公钥询问、公钥替换和部分私钥抽取预言机。在结束查询时 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 输出猜测 $b^{\prime }\in \left\{0,1\right\}$ 。

如果 $b=b^{\prime }$ ，并且 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 在阶段1没有替换 $i{d}^{\ast }$ 的公钥或在两个查询阶段都没有询问 $i{d}^{\ast }$ 的部分私钥，则 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 赢得游戏。

${\mathcal{A}}_{\mathrm{Ⅰ}}$ 的优势定义为 ${\text{Adv}}_{{\mathcal{A}}_{\mathrm{Ⅰ}}}\left(\lambda \right)=\left|\mathrm{Pr}\left[b=b^{\prime }\right]-\frac{1}{2}\right|$ 。如果 ${\text{Adv}}_{{\mathcal{A}}_{\mathrm{Ⅰ}}}\left(\lambda \right)$ 是可忽略的，则称这个CLFHE方案在 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 攻击下是INDr-CPA安全的。

攻击者 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 的INDr-CPA安全游戏如下：

初始化：挑战者产生 $\left(mpk,msk\right)\leftarrow \text{Setup}\left(1^{\lambda },1^L\right)$ 。并把主公钥mpk和主私钥msk发送给 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 。

阶段1： ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 可查询公钥询问(request public key)预言机。

公钥询问预言机：输入身份id和部分私钥 $d_{id}$ ，它计算公钥 $\left(p{k}_{id},s{k}_{id}\right)\leftarrow \text{KeyGen}\left(mpk,id,d_{id}\right)$ ，并返回 $p{k}_{id}$ 。

${\mathcal{A}}_{\mathrm{Ⅱ}}$ 结束查询输出目标身份 $i{d}^{\ast }$ 和消息 $\mu$ 。

挑战：挑战者随机选择 $b\leftarrow \left\{0,1\right\}$ 和密文 $c\leftarrow \mathcal{C}$ 。若 $b=0$ ，设置挑战密文 $c^{\ast }=\text{Encrypt}\left(mpk,i{d}^{\ast },p{k}_{i{d}^{\ast }},\mu \right)$ ，其中 $p{k}_{i{d}^{\ast }}$ 是 $i{d}^{\ast }$ 关联的公钥；若 $b=1$ ，设置挑战密文 $c^{\ast }=c$ 。

阶段2： ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 继续查询公钥询问预言机。在结束查询时 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 输出猜测 $b^{\prime }\in \left\{0,1\right\}$ 。

如果 $b=b^{\prime }$ ，则 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 赢得游戏。

${\mathcal{A}}_{\mathrm{Ⅱ}}$ 的优势定义为 ${\text{Adv}}_{{\mathcal{A}}_{\mathrm{Ⅱ}}}\left(\lambda \right)=\left|\mathrm{Pr}\left[b=b^{\prime }\right]-\frac{1}{2}\right|$ 。如果 ${\text{Adv}}_{{\mathcal{A}}_{\mathrm{Ⅱ}}}\left(\lambda \right)$ 是可忽略的，则称这个CLFHE方案在 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 攻击下是INDr-CPA安全的。

4. 基于LWR问题CLFHE

4.1. 方案描述

我们令向量 $g={\left(1,\cdots ,2^{\lceil \log p\rceil -1}\right)}^{\text{T}}\in {\mathbb{Z}}_p^{\lceil \log p\rceil }$ 。令矩阵 $G=I_{2m+1}\otimes g^{\text{T}}\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ ，其中 $N=\left(2m+1\right)\cdot \lceil \log p\rceil$ 。定义反函数 $G^{-1}:{\mathbb{Z}}_p^{\left(2m+1\right)\times N}\to {\left\{0,1\right\}}^{N\times N}$ ，它把输入矩阵的每个元素 $a\in {\mathbb{Z}}_p$ 扩展为比特向量 ${\left(a_0,\cdots ,a_{\lceil \log p\rceil -1}\right)}^{\text{T}}\in {\left\{0,1\right\}}^{\lceil \log p\rceil }$ ，且满足 $a={\displaystyle {\sum }_{i=0}^{\lceil \log p\rceil -1}{2}^i}\cdot a_i$ 。对任意矩阵 $C\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ ，有 $G\cdot G^{-1}\left(C\right)=C$ 。

下面给出基于LWR问题的CLFHE方案，它的消息空间为 $\mathcal{M}=\left\{0,1\right\}$ ，密文空间为 $\mathcal{C}={\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 。

$\text{Setup}\left(1^{\lambda },1^L\right)$ ：KGC设置参数 $n=n\left(\lambda ,L\right)$ 、 $q=q\left(\lambda ,L\right)$ 、 $p=p\left(\lambda ,L\right)$ 、 $m=m\left(\lambda ,L\right)$ 、 ${\sigma }_1={\sigma }_1\left(\lambda ,L\right)$ 和 ${\sigma }_2={\sigma }_2\left(\lambda ,L\right)$ 。这些参数具体见4.3节。调用 $\text{TrapGen}\left(n,q\right)$ 产生矩阵 $A\in {\mathbb{Z}}_q^{n\times m}$ 和 ${\Lambda }^{\perp }\left(A\right)$ 的一组基 $T_A\in {\mathbb{Z}}^{m\times m}$ ，且 $\Vert {\tilde{T}}_A\Vert \le O\left(\sqrt{n\log q}\right)$ 。随机选择矩阵 $\bar{A}\leftarrow {\mathbb{Z}}_q^{n\times m}$ 和 $B\leftarrow {\mathbb{Z}}_q^{n\times m}$ 。选择哈希函数 $H:{\left\{0,1\right\}}^{\ast }\to {\mathbb{Z}}_q^n$ 。输出主公钥 $mpk=\left(n,q,p,m,{\sigma }_1,{\sigma }_2,A,\bar{A},B,H\right)$ 和主私钥 $msk=T_A$ 。

$\text{Extract}\left(mpk,msk,id\right)$ ：对身份 $id\in {\left\{0,1\right\}}^{*}$ ，KGC计算 $u=H\left(id\right)\in {\mathbb{Z}}_q^n$ 。调用 $\text{SamplePre}\left(A,T_A,u,{\sigma }_1\right)$ 产生向量 $d\in {\mathbb{Z}}^m$ 。输出部分私钥 $d_{id}=d$ 。这里有 $A\cdot d=u\mathrm{mod}q$ 。

$\text{KeyGen}\left(mpk,id,d_{id}\right)$ ：用户选择 $x\leftarrow D_{{\mathbb{Z}}^m,{\sigma }_2}$ ，令 $v=B\cdot x\mathrm{mod}q$ 。此外令 $\bar{u}=\bar{A}\cdot d\mathrm{mod}q$ 。令 $r=\left(\begin{array}{c}-d\\ -x\\ 1\end{array}\right)\in {\mathbb{Z}}^{2m+1}$ 。输出公钥 $p{k}_{id}=\left(v,\bar{u}\right)$ 和私钥 $s{k}_{id}=r$ 。

$\text{Encrypt}\left(mpk,id,p{k}_{id},\mu \right)$ ：对消息 $\mu \in \left\{0,1\right\}$ ，计算 $u=H\left(id\right)\in {\mathbb{Z}}_q^n$ 。随机选择矩阵 $S_1\leftarrow {\mathbb{Z}}_q^{n\times N}$ 、 $\bar{S}\leftarrow {\mathbb{Z}}_q^{n\times N}$ 和 $S_2\leftarrow {\mathbb{Z}}_q^{n\times N}$ ，输出密文

$C=\left(\begin{array}{c}{〚A^{\text{T}}\cdot S_1〛}_p+{〚{\bar{A}}^{\text{T}}\cdot \bar{S}〛}_p\\ {〚B^{\text{T}}\cdot S_2〛}_p\\ {〚u^{\text{T}}\cdot S_1〛}_p+{〚{\bar{u}}^{\text{T}}\cdot \bar{S}〛}_p+{〚v^{\text{T}}\cdot S_2〛}_p\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

$\text{Decrypt}\left(mpk,s{k}_{id},c\right)$ ：给定密文 $C\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ ，已知 $s{k}_{id}=r$ 。输出消息 ${\mu }^{\prime }=〚\frac{r^{\text{T}}\cdot c}{2^{\lceil \log p\rceil -2}}〛$ ，其中 $c$ 为密文 $C$ 的倒数第2列。

给定同一身份id下的两个密文 $C_1\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 和 $C_2\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ ，密文同态加法和乘法如下：

$\text{Add}\left(C_1,C_2\right)$ ：输出 $C_{\text{add}}=C_1+C_2\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 。

$\text{Mult}\left(C_1,C_2\right)$ ：输出 $C_{\text{mult}}=C_1\cdot G^{-1}\left(C_2\right)\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 。

4.2. 方案分析

4.2.1. 正确性

对于Encrypt输出的密文 $C\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ ，有

$\begin{array}{l}{r}^{\text{T}}\cdot C={\left(\begin{array}{c}-d\\ -x\\ 1\end{array}\right)}^{\text{T}}\cdot \left(\begin{array}{c}{〚A^{\text{T}}\cdot S_1〛}_p+{〚{\bar{A}}^{\text{T}}\cdot \bar{S}〛}_p\\ {〚B^{\text{T}}\cdot S_2〛}_p\\ {〚u^{\text{T}}\cdot S_1〛}_p+{〚{\bar{u}}^{\text{T}}\cdot \bar{S}〛}_p+{〚v^{\text{T}}\cdot S_2〛}_p\end{array}\right)+\mu \cdot r^{\text{T}}\cdot G\\ ={〚u^{\text{T}}\cdot S_1〛}_p+{〚{\bar{u}}^{\text{T}}\cdot \bar{S}〛}_p+{〚v^{\text{T}}\cdot S_2〛}_p-d^{\text{T}}\cdot \left({〚A^{\text{T}}\cdot S_1〛}_p+{〚{\bar{A}}^{\text{T}}\cdot \bar{S}〛}_p\right)-x^{\text{T}}\cdot {〚B^{\text{T}}\cdot S_2〛}_p+\mu \cdot r^{\text{T}}\cdot G\\ =\left({〚u^{\text{T}}\cdot S_1〛}_p-d^{\text{T}}\cdot {〚A^{\text{T}}\cdot S_1〛}_p\right)+\left({〚{\bar{u}}^{\text{T}}\cdot \bar{S}〛}_p-d^{\text{T}}\cdot {〚{\bar{A}}^{\text{T}}\cdot \bar{S}〛}_p\right)+\left({〚v^{\text{T}}\cdot S_2〛}_p-x^{\text{T}}\cdot {〚B^{\text{T}}\cdot S_2〛}_p\right)+\mu \cdot r^{\text{T}}\cdot G\\ =\frac{p}{q}\left(u^{\text{T}}-d^{\text{T}}{A}^{\text{T}}\right)S_1+e_1^{\text{T}}-d^{\text{T}}{E}_1+\frac{p}{q}\left({\bar{u}}^{\text{T}}-d^{\text{T}}{\bar{A}}^{\text{T}}\right)\bar{S}+{\bar{e}}^{\text{T}}-d^{\text{T}}\bar{E}+\frac{p}{q}\left(v^{\text{T}}-x^{\text{T}}{B}^{\text{T}}\right)S_2+e_2^{\text{T}}-x^{\text{T}}{E}_2+\mu \cdot r^{\text{T}}\cdot G\\ =e_1^{\text{T}}+{\bar{e}}^{\text{T}}+e_2^{\text{T}}-\left(d^{\text{T}}{E}_1+d^{\text{T}}\bar{E}+x^{\text{T}}{E}_2\right)+\mu \cdot r^{\text{T}}\cdot G\end{array}$

其中

$e_1^{\text{T}}={〚u^{\text{T}}\cdot S_1〛}_p-\frac{p}{q}\cdot u^{\text{T}}\cdot S_1\in {\left[-\frac{1}{2},\frac{1}{2}\right]}^{1\times N}$

$E_1={〚A^{\text{T}}\cdot S_1〛}_p-\frac{p}{q}\cdot A^{\text{T}}\cdot S_1\in {\left[-\frac{1}{2},\frac{1}{2}\right]}^{m\times N}$

${\bar{e}}^{\text{T}}={〚{\bar{u}}^{\text{T}}\cdot \bar{S}〛}_p-\frac{p}{q}\cdot {\bar{u}}^{\text{T}}\cdot \bar{S}\in {\left[-\frac{1}{2},\frac{1}{2}\right]}^{1\times N}$

$\bar{E}={〚{\bar{A}}^{\text{T}}\cdot \bar{S}〛}_p-\frac{p}{q}\cdot {\bar{A}}^{\text{T}}\cdot \bar{S}\in {\left[-\frac{1}{2},\frac{1}{2}\right]}^{m\times N}$

$e_2^{\text{T}}={〚v^{\text{T}}\cdot S_2〛}_p-\frac{p}{q}\cdot v^{\text{T}}\cdot S_2\in {\left[-\frac{1}{2},\frac{1}{2}\right]}^{1\times N}$

$E_2={〚B^{\text{T}}\cdot S_2〛}_p-\frac{p}{q}\cdot B^{\text{T}}\cdot S_2\in {\left[-\frac{1}{2},\frac{1}{2}\right]}^{m\times N}$ .

令 $w^{\text{T}}=e_1^{\text{T}}+{\bar{e}}^{\text{T}}+e_2^{\text{T}}-\left(d^{\text{T}}{E}_1+d^{\text{T}}\bar{E}+x^{\text{T}}{E}_2\right)$ ，则 $C$ 的误差

$\begin{array}{c}{\Vert w^{\text{T}}\Vert }_{\infty }={\Vert e_1^{\text{T}}+{\bar{e}}^{\text{T}}+e_2^{\text{T}}-\left(d^{\text{T}}{E}_1+d^{\text{T}}\bar{E}+x^{\text{T}}{E}_2\right)\Vert }_{\infty }\\ \le {\Vert e_1^{\text{T}}+{\bar{e}}^{\text{T}}+e_2^{\text{T}}\Vert }_{\infty }+{\Vert d^{\text{T}}{E}_1+d^{\text{T}}\bar{E}+x^{\text{T}}{E}_2\Vert }_{\infty }\\ \le \frac{3}{2}+m\cdot {\Vert d\Vert }_{\infty }\cdot {\Vert E_1\Vert }_{\infty }+m\cdot {\Vert d\Vert }_{\infty }\cdot {\Vert \bar{E}\Vert }_{\infty }+m\cdot {\Vert x\Vert }_{\infty }\cdot {\Vert E_2\Vert }_{\infty }\\ \le \frac{3}{2}+m\cdot {\Vert d\Vert }_{\infty }+\frac{1}{2}\cdot m\cdot {\Vert x\Vert }_{\infty }\\ \le \frac{3}{2}+m\cdot \Vert d\Vert +\frac{1}{2}\cdot m\cdot \Vert x\Vert \\ \le \frac{3}{2}+m\sqrt{m}\cdot \left({\sigma }_1+\frac{1}{2}\cdot {\sigma }_2\right)\end{array}$

其中 $\Vert d\Vert \le {\sigma }_1\cdot \sqrt{m}$ ， $\Vert x\Vert \le {\sigma }_2\cdot \sqrt{m}$ 。我们记 ${\Vert w^{\text{T}}\Vert }_{\infty }\le \Delta =\frac{3}{2}+m\sqrt{m}\cdot \left({\sigma }_1+\frac{1}{2}\cdot {\sigma }_2\right)$ 。

对 $\text{Add}\left(C_1,C_2\right)$ 输出的密文 $C_{\text{add}}$ ，有

$r^{\text{T}}\cdot C_{\text{add}}=r^{\text{T}}\cdot \left(C_1+C_2\right)=w_1^{\text{T}}+w_2^{\text{T}}+\left({\mu }_1+{\mu }_2\right)\cdot r^{\text{T}}\cdot G$ .

令 $w_{\text{add}}^{\text{T}}=w_1^{\text{T}}+w_2^{\text{T}}$ ，则 $C_{\text{add}}$ 的误差 ${\Vert w_{\text{add}}^{\text{T}}\Vert }_{\infty }={\Vert w_1^{\text{T}}+w_2^{\text{T}}\Vert }_{\infty }\le {\Vert w_1^{\text{T}}\Vert }_{\infty }+{\Vert w_2^{\text{T}}\Vert }_{\infty }\le 2\Delta$ 。

对 $\text{Mult}\left(C_1,C_2\right)$ 输出的密文 $C_{\text{mult}}$ ，有

$\begin{array}{c}{r}^{\text{T}}\cdot C_{\text{mult}}=r^{\text{T}}\cdot C_1\cdot G^{-1}\left(C_2\right)\\ =\left(w_1^{\text{T}}+{\mu }_1\cdot r^{\text{T}}\cdot G\right)\cdot G^{-1}\left(C_2\right)\\ =w_1^{\text{T}}\cdot G^{-1}\left(C_2\right)+{\mu }_1\cdot r^{\text{T}}\cdot G\cdot G^{-1}\left(C_2\right)\\ =w_1^{\text{T}}\cdot G^{-1}\left(C_2\right)+{\mu }_1\cdot r^{\text{T}}\cdot C_2\\ =w_1^{\text{T}}\cdot G^{-1}\left(C_2\right)+{\mu }_1\cdot \left(w_2^{\text{T}}+{\mu }_2\cdot r^{\text{T}}\cdot G\right)\\ =w_1^{\text{T}}\cdot G^{-1}\left(C_2\right)+{\mu }_1\cdot w_2^{\text{T}}+{\mu }_1{\mu }_2\cdot r^{\text{T}}\cdot G\end{array}$

令 $w_{\text{mult}}=w_1^{\text{T}}\cdot G^{-1}\left(C_2\right)+{\mu }_1\cdot w_2^{\text{T}}$ ，则 $C_{\text{mult}}$ 的误差

$\begin{array}{c}{\Vert w_{\text{mult}}\Vert }_{\infty }={\Vert w_1^{\text{T}}\cdot G^{-1}\left(C_2\right)+{\mu }_1\cdot w_2^{\text{T}}\Vert }_{\infty }\\ \le {\Vert w_1^{\text{T}}\cdot G^{-1}\left(C_2\right)\Vert }_{\infty }+{\Vert {\mu }_1\cdot w_2^{\text{T}}\Vert }_{\infty }\\ \le N\cdot {\Vert w_1\Vert }_{\infty }\cdot {\Vert G^{-1}\left(C_2\right)\Vert }_{\infty }+\Delta \\ \le N\Delta +\Delta =\left(N+1\right)\Delta \end{array}$

通过迭代调用 $\text{Add}\left(C_1,C_2\right)$ 和 $\text{Mult}\left(C_1,C_2\right)$ ，密文计算 $\text{Eval}\left(f,C_1,\cdots ,C_{\mathcal{l}}\right)$ 可输出密文 $C_f\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 。因为 $f:{\mathcal{M}}^{\mathcal{l}}\to \mathcal{M}$ 的电路深度 $\text{depth}\left(f\right)\le L$ 。又知道有 ${\Vert w_{\text{add}}^{\text{T}}\Vert }_{\infty }\le 2\Delta$ ， ${\Vert w_{\text{mult}}\Vert }_{\infty }\le \left(N+1\right)\Delta$ ，即 ${\Vert w_{\text{add}}^{\text{T}}\Vert }_{\infty }\ll {\Vert w_{\text{mult}}\Vert }_{\infty }$ 。故 $C_f\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 的误差 ${\Vert w_f\Vert }_{\infty }\le {\left(N+1\right)}^L\Delta$ 。于是对 $C_f\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 的倒数第2列 $c_f\in {\mathbb{Z}}_p^{2m+1}$ ，有 $r^{\text{T}}\cdot c_f\le {\Vert w_f^{\text{T}}\Vert }_{\infty }+{\mu }_f\cdot 2^{\lceil \log p\rceil -2}$ 。因为 $2^{\lceil \log p\rceil -2}\in \left[p/4,p/2\right)$ ，故如果 ${\Vert w_f^{\text{T}}\Vert }_{\infty }\le {\left(N+1\right)}^L\Delta <p/8$ ， $\text{Eval}\left(f,C_1,\cdots ,C_{\mathcal{l}}\right)$ 输出的密文 $C_f\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 可正确解密得到消息 ${\mu }_f=f\left({\mu }_1,\cdots ,{\mu }_{\mathcal{l}}\right)$ 。

4.2.2. 安全性

所提出的CLFHE在 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 攻击下是INDr-CPA安全的。即：

定理1令哈希函数H为随机预言机。若攻击者 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 在INDr-CPA安全游戏中以优势 ${\text{Adv}}_{{\mathcal{A}}_{\mathrm{Ⅰ}}}\left(\lambda \right)$ 攻破所提出的CLFHE方案，且H预言、公钥询问次数为 $q_{\text{H}}$ 、 $q_{\text{rpk}}$ 。则存在以优势 ${\text{Adv}}_{\mathcal{B}}\left(\lambda \right)$ 解决 ${\text{LWR}}_{n,q,p}$ 问题的算法 $\mathcal{B}$ 。其中

${\text{Adv}}_{{\mathcal{A}}_{\mathrm{Ⅰ}}}\left(\lambda \right)\le 2\left(q_{\text{rpk}}+q_{\text{H}}\right)\cdot {\text{Adv}}_{\mathcal{B}}\left(\lambda \right)$ .

证明：我们基于游戏序列进行证明。并定义 $Y_i$ 为攻击者 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 在Game i中赢得游戏这一事件。

Game 0 它是攻击所提出的方案的 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 和挑战者之间的原始INDr-CPA游戏。在这个游戏中， ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 的优势 ${\text{Adv}}_{{\mathcal{A}}_{\mathrm{Ⅰ}}}^{\text{CLFHE}}\left(\lambda \right)=\left|\mathrm{Pr}\left[Y_0\right]-\frac{1}{2}\right|$ 。

Game 1这个游戏相比Game 0的变化是以下四个方面：

① 始化：挑战者随机选择 $A\leftarrow {\mathbb{Z}}_q^{n\times m}$ 。

② H预言机：当 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 询问身份id的H预言时，挑战者选择 $d\leftarrow D_{{\mathbb{Z}}^m,{\sigma }_1}$ ，令 $u=A\cdot d\mathrm{mod}q$ 和 $\bar{u}=\bar{A}\cdot d\mathrm{mod}q$ ，把元组 $\left(id,u,\bar{u},d\right)$ 存储起来，并返回 $u$ 给 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 。

③ 公钥询问预言机：当 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 询问身份id的公钥时，挑战者选择 $x\leftarrow D_{{\mathbb{Z}}^m,{\sigma }_2}$ ，令 $v=B\cdot x\mathrm{mod}q$ 。从H记载里找到元组 $\left(id,u,\bar{u},d\right)$ 。令公钥 $p{k}_{id}=\left(v,\bar{u}\right)$ ，把元组 $\left(id,p{k}_{id},\ast \right)$ 存储起来，并返回 $p{k}_{id}$ 给 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 。其中 $\ast$ 表示该元素空缺，它用于存储替换公钥 $p{k^{\prime }}_{id}$ 。

④ 部分私钥抽取预言机：当 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 询问身份id的部分私钥时，挑战者从H记载里找到元组 $\left(id,u,\bar{u},d\right)$ ，把 $d$ 返回给 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 。

由引理3等可知，Game 0和Game 1是统计不可区分的。故 $\left|\mathrm{Pr}\left[Y_0\right]-\mathrm{Pr}\left[Y_1\right]\right|=\text{negl}\left(\lambda \right)$ 。

Game 2 这个游戏相比Game 1调整了以下两个地方：

① 始化：挑战者随机产生猜测 $\eta \leftarrow \left\{0,1\right\}$ 。 $\eta =0$ 表示 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 会询问目标身份的部分私钥， $\eta =1$ 表示 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 不会询问目标身份的部分私钥。

② 获胜条件：令Extract表示 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 询问了目标身份的部分私钥。则

如果 $\eta =0$ ，并且Extract发生了，则在 $b=b^{\prime }$ 时 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 获胜；

如果 $\eta =1$ ，并且Extract发生了，则 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 以概率 $\frac{1}{2}$ 获胜；

如果 $\eta =0$ ，并且Extract没有发生，则 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 以概率 $\frac{1}{2}$ 获胜；

如果 $\eta =1$ ，并且Extract没有发生，则在 $b=b^{\prime }$ 时 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 获胜。

经简单计算可知 $\left|\mathrm{Pr}\left[Y_2\right]-\frac{1}{2}\right|=\frac{1}{2}\left|\mathrm{Pr}\left[Y_1\right]-\frac{1}{2}\right|$ 。又

$\begin{array}{c}\left|\mathrm{Pr}\left[Y_2\right]-\frac{1}{2}\right|=\left|\frac{1}{2}\mathrm{Pr}\left[Y_2|\eta =0\right]+\frac{1}{2}\mathrm{Pr}\left[Y_2|\eta =1\right]-\frac{1}{2}\right|\\ \le \frac{1}{2}\left|\mathrm{Pr}\left[Y_2|\eta =0\right]-\frac{1}{2}\right|+\frac{1}{2}\left|\mathrm{Pr}\left[Y_2|\eta =1\right]-\frac{1}{2}\right|\end{array}$

于是接下来我们依据猜测 $\eta \in \left\{0,1\right\}$ 的值把游戏分为两条不同的链。即猜测 $\eta =0$ 下的链 $\left\{\text{Game}{i}_{\eta =0}\right\}$ 和猜测 $\eta =1$ 下的链 $\left\{\text{Game}{i}_{\eta =1}\right\}$ 。因为猜测 $\eta \in \left\{0,1\right\}$ 只能为0或1，所以在Game 2之后只可能选择其中的一条链执行。

$\text{Game}{3}_{\eta =0}$ 这个游戏相比Game 2的变化是以下三点：

① 初始化：挑战者选择 $i\leftarrow \left\{1,\cdots ,q_{\text{rpk}}\right\}$ 。

② 公钥询问预言机：如果身份id是第i次公钥询问，挑战者随机选择 $v_i\leftarrow {\mathbb{Z}}_q^n$ 。从H记载里找到元组 $\left(id,u,\bar{u},d\right)$ 。令公钥 $p{k}_{id}=\left(v_i,\bar{u}\right)$ ，把元组 $\left(id,p{k}_{id},\ast \right)$ 存储起来，并返回 $p{k}_{id}$ 给 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 。否则，挑战者选择 $x\leftarrow D_{{\mathbb{Z}}^m,{\sigma }_2}$ ，令 $v=B\cdot x\mathrm{mod}q$ 。从H记载里找到元组 $\left(id,u,\bar{u},d\right)$ 。令公钥 $p{k}_{id}=\left(v,\bar{u}\right)$ ，把元组 $\left(id,p{k}_{id},\ast \right)$ 存储起来，并返回 $p{k}_{id}$ 给 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 。

③ 挑战：如果目标身份 $i{d}^{\ast }$ 不是第i次询问的公钥预言机，则挑战者中止并输出 $\perp$ 。否则挑战者选择 $S_1\leftarrow {\mathbb{Z}}_q^{n\times N}$ 、 $\bar{S}\leftarrow {\mathbb{Z}}_q^{n\times N}$ 和 $S_2\leftarrow {\mathbb{Z}}_q^{n\times N}$ ，设定挑战密文

$C^{\ast }=\left(\begin{array}{c}{〚A^{\text{T}}\cdot S_1〛}_p+{〚{\bar{A}}^{\text{T}}\cdot \bar{S}〛}_p\\ {〚B^{\text{T}}\cdot S_2〛}_p\\ {〚u^{\text{T}}\cdot S_1〛}_p+{〚{\bar{u}}^{\text{T}}\cdot \bar{S}〛}_p+{〚v_i^{\text{T}}\cdot S_2〛}_p\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

在这个游戏中， ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 若没有询问目标身份 $i{d}^{\ast }$ 的部分私钥，挑战者输出一个随机比特，否则输出 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 的猜测 $b^{\prime }$ 。

$\text{Game}{3}_{\eta =0}$ 不中止输出 $\perp$ 的概率为 $\mathrm{Pr}\left[\neg \text{abort}\right]=\frac{1}{q_{\text{rpk}}}$ 。故 $\left|\mathrm{Pr}\left[Y_3|\eta =0\right]-\frac{1}{2}\right|=\frac{1}{q_{\text{rpk}}}\cdot \left|\mathrm{Pr}\left[Y_2|\eta =0\right]-\frac{1}{2}\right|$ 。

$\text{Game}{3}_{\eta =1}$ 这个游戏相比Game 2的变化是以下四点：

① 初始化：挑战者选择 $j\leftarrow \left\{1,\cdots ,q_{\text{H}}\right\}$ 。

② H预言机：如果id是第j次H询问，挑战者随机选择 $u_j\leftarrow {\mathbb{Z}}_q^n$ 和 $\bar{u}\leftarrow {\mathbb{Z}}_q^n$ ，把元组 $\left(id,u_j,\bar{u},\perp \right)$ 存储起来，并把 $u_j$ 返回给 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 。否则，挑战者选择 $d\leftarrow D_{{\mathbb{Z}}^m,{\sigma }_1}$ ，令 $u=A\cdot d\mathrm{mod}q$ 和 $\bar{u}=\bar{A}\cdot d\mathrm{mod}q$ ，把元组 $\left(id,u,\bar{u},d\right)$ 存储起来，并返回 $u$ 给 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 。

③ 部分私钥抽取预言机：当 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 提交身份id询问其部分私钥时，挑战者从H记载里找到元组 $\left(id,u,\bar{u},d\right)$ ，如果 $d=\perp$ ，挑战者中止并输出一个随机比特。否则把 $d$ 返回给 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 。

④ 挑战：如果目标身份 $i{d}^{\ast }$ 不是第j次询问的H预言机，则挑战者中止并输出 $\perp$ 。否则挑战者选择 $S_1\leftarrow {\mathbb{Z}}_q^{n\times N}$ 、 $\bar{S}\leftarrow {\mathbb{Z}}_q^{n\times N}$ 和 $S_2\leftarrow {\mathbb{Z}}_q^{n\times N}$ ，设定挑战密文

$C^{\ast }=\left(\begin{array}{c}{〚A^{\text{T}}\cdot S_1〛}_p+{〚{\bar{A}}^{\text{T}}\cdot \bar{S}〛}_p\\ {〚B^{\text{T}}\cdot S_2〛}_p\\ {〚u_j^{\text{T}}\cdot S_1〛}_p+{〚{{\bar{u}}^{\prime }}^{\text{T}}\cdot \bar{S}〛}_p+{〚{v^{\prime }}^{\text{T}}\cdot S_2〛}_p\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ ,

其中 $p{k^{\prime }}_{i{d}^{\ast }}=\left(v^{\prime },{\bar{u}}^{\prime }\right)$ 是目标身份 $i{d}^{\ast }$ 当前关联的公钥。

$\text{Game}{3}_{\eta =1}$ 不中止输出 $\perp$ 的概率为 $\mathrm{Pr}\left[\neg \text{abort}\right]=\frac{1}{q_{\text{H}}}$ 。故 $\left|\mathrm{Pr}\left[Y_3|\eta =1\right]-\frac{1}{2}\right|=\frac{1}{q_{\text{H}}}\cdot \left|\mathrm{Pr}\left[Y_2|\eta =1\right]-\frac{1}{2}\right|$ 。

$\text{Game}{4}_{\eta =0}$ 这个游戏只对 $\text{Game}{3}_{\eta =0}$ 进行了一处修改。即

挑战：挑战者随机选择 $\tilde{B}\leftarrow {\mathbb{Z}}_p^{m\times N}$ 和 $\tilde{b}\leftarrow {\mathbb{Z}}_p^N$ ，令挑战密文

$C^{\ast }=\left(\begin{array}{c}{〚A^{\text{T}}\cdot S_1〛}_p+{〚{\bar{A}}^{\text{T}}\cdot \bar{S}〛}_p\\ \tilde{B}\\ {〚u^{\text{T}}\cdot S_1〛}_p+{〚{\bar{u}}^{\text{T}}\cdot \bar{S}〛}_p+{\tilde{b}}^{\text{T}}\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

假设 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 以不可忽略的优势区分 $\text{Game}{3}_{\eta =0}$ 和 $\text{Game}{4}_{\eta =0}$ ，则利用 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 可构造解决 ${\text{LWR}}_{n,q,p}$ 问题的算法 $\mathcal{B}$ 。 $\mathcal{B}$ 的输入是一个 ${\text{LWR}}_{n,q,p}$ 问题实例 $\left(\left(F|f\right),\left(\begin{array}{c}Z\\ z^{\text{T}}\end{array}\right)\right)\in {\mathbb{Z}}_q^{n\times \left(m+1\right)}\times {\mathbb{Z}}_p^{\left(m+1\right)\times N}$ 。 $\mathcal{B}$ 模拟挑战者与 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 交互如下：初始化： $\mathcal{B}$ 令 $B=F$ 。并选择 $i\leftarrow \left\{1,\cdots ,q_{\text{rpk}}\right\}$ 。

公钥询问预言机：如果id是第i次公钥询问， $\mathcal{B}$ 令 $v_i=f$ 。从H记载里找到元组 $\left(id,u,\bar{u},d\right)$ 。令公钥 $p{k}_{id}=\left(f,\bar{u}\right)$ ，把元组 $\left(id,p{k}_{id},\ast \right)$ 存储起来，并返回 $p{k}_{id}$ 给 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 。

挑战： $\mathcal{B}$ 选择 $S_1\leftarrow {\mathbb{Z}}_q^{n\times N}$ 和 $\bar{S}\leftarrow {\mathbb{Z}}_q^{n\times N}$ ，设定挑战密文

$C^{\ast }=\left(\begin{array}{c}{〚A^{\text{T}}\cdot S_1〛}_p+{〚{\bar{A}}^{\text{T}}\cdot \bar{S}〛}_p\\ Z\\ {〚u^{\text{T}}\cdot S_1〛}_p+{〚{\bar{u}}^{\text{T}}\cdot \bar{S}〛}_p+z^{\text{T}}\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

其余的内容 $\mathcal{B}$ 都与 $\text{Game}{3}_{\eta =0}$ 一样进行处置。

若 $\left(\begin{array}{c}Z\\ z^{\text{T}}\end{array}\right)\in {\mathbb{Z}}_p^{\left(m+1\right)\times N}$ 是通过密钥 $S\in {\mathbb{Z}}_q^{n\times N}$ 产生的， $C^{\ast }$ 的分布和 $\text{Game}{3}_{\eta =0}$ 中一样。若 $\left(\begin{array}{c}Z\\ z^{\text{T}}\end{array}\right)\in {\mathbb{Z}}_p^{\left(m+1\right)\times N}$ 是随机选择的， $C^{\ast }$ 的分布和 $\text{Game}{4}_{\eta =0}$ 中一样。故 $\left|\mathrm{Pr}\left[Y_3|\eta =0\right]-\mathrm{Pr}\left[Y_4|\eta =0\right]\right|={\text{Adv}}_{\mathcal{B}}\left(\lambda \right)$ 。

$\text{Game}{4}_{\eta =1}$ 这个游戏只对 $\text{Game}{3}_{\eta =1}$ 进行了一处修改。即

挑战：挑战者随机选择 $\tilde{A}\leftarrow {\mathbb{Z}}_p^{m\times N}$ 和 $\tilde{a}\leftarrow {\mathbb{Z}}_p^N$ ，令挑战密文

$C^{\ast }=\left(\begin{array}{c}\tilde{A}+{〚{\bar{A}}^{\text{T}}\cdot \bar{S}〛}_p\\ {〚B^{\text{T}}\cdot S_2〛}_p\\ {\tilde{a}}^{\text{T}}+{〚{{\bar{u}}^{\prime }}^{\text{T}}\cdot \bar{S}〛}_p+{〚{v^{\prime }}^{\text{T}}\cdot S_2〛}_p\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

假设 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 以不可忽略的优势区分 $\text{Game}{3}_{\eta =1}$ 和 $\text{Game}{4}_{\eta =1}$ ，则利用 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 可构造解决 ${\text{LWR}}_{n,q,p}$ 问题的算法 $\mathcal{B}$ 。 $\mathcal{B}$ 的输入是一个 ${\text{LWR}}_{n,q,p}$ 问题实例 $\left(\left(F|f\right),\left(\begin{array}{c}Z\\ z^{\text{T}}\end{array}\right)\right)\in {\mathbb{Z}}_q^{n\times \left(m+1\right)}\times {\mathbb{Z}}_p^{\left(m+1\right)\times N}$ 。 $\mathcal{B}$ 模拟挑战者与 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 交互如下：

初始化： $\mathcal{B}$ 令 $A=F$ 。并选择 $j\leftarrow \left\{1,\cdots ,q_{\text{H}}\right\}$ 。

H预言机：如果id是第j次H询问， $\mathcal{B}$ 令 $u_j=f$ 。 $\mathcal{B}$ 随机选择 $\bar{u}\leftarrow {\mathbb{Z}}_q^n$ 。把元组 $\left(id,f,\bar{u},\perp \right)$ 存储起来，并把 $f$ 返回给 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 。

挑战： $\mathcal{B}$ 选择 $\bar{S}\leftarrow {\mathbb{Z}}_q^{n\times N}$ 和 $S_2\leftarrow {\mathbb{Z}}_q^{n\times N}$ ，设定挑战密文

$C^{\ast }=\left(\begin{array}{c}Z+{〚{\bar{A}}^{\text{T}}\cdot \bar{S}〛}_p\\ {〚B^{\text{T}}\cdot S_2〛}_p\\ z^{\text{T}}+{〚{{\bar{u}}^{\prime }}^{\text{T}}\cdot \bar{S}〛}_p+{〚{v^{\prime }}^{\text{T}}\cdot S_2〛}_p\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

其余的内容 $\mathcal{B}$ 都与 $\text{Game}{3}_{\eta =1}$ 一样进行处置。

若 $\left(\begin{array}{c}Z\\ z^{\text{T}}\end{array}\right)\in {\mathbb{Z}}_p^{\left(m+1\right)\times N}$ 是由密钥 $S\in {\mathbb{Z}}_q^{n\times N}$ 产生的， $C^{\ast }$ 的分布和 $\text{Game}{3}_{\eta =1}$ 中一样。若 $\left(\begin{array}{c}Z\\ z^{\text{T}}\end{array}\right)\in {\mathbb{Z}}_p^{\left(m+1\right)\times N}$ 是随机选择的， $C^{\ast }$ 的分布和 $\text{Game}{4}_{\eta =1}$ 中一样。故 $\left|\mathrm{Pr}\left[Y_3|\eta =1\right]-\mathrm{Pr}\left[Y_4|\eta =1\right]\right|={\text{Adv}}_{\mathcal{B}}\left(\lambda \right)$ 。

$\text{Game}{5}_{\eta =0}$ 它只对 $\text{Game}{4}_{\eta =0}$ 进行了一处修改。即

挑战：挑战者随机选择 $\hat{b}\leftarrow {\mathbb{Z}}_p^N$ ，令挑战密文为

$C^{\ast }=\left(\begin{array}{c}{〚A^{\text{T}}\cdot S_1〛}_p+{〚{\bar{A}}^{\text{T}}\cdot \bar{S}〛}_p\\ \tilde{B}\\ {\hat{b}}^{\text{T}}\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

在 $\text{Game}{4}_{\eta =0}$ 中， $\tilde{b}\leftarrow {\mathbb{Z}}_p^N$ 是均匀随机的，故 ${〚u^{\text{T}}\cdot S_1〛}_p+{〚{\bar{u}}^{\text{T}}\cdot \bar{S}〛}_p+{\tilde{b}}^{\text{T}}$ 亦是均匀随机的。故

$\left|\mathrm{Pr}\left[Y_4|\eta =0\right]-\mathrm{Pr}\left[Y_5|\eta =0\right]\right|=\text{negl}\left(\lambda \right)$ 。

$\text{Game}{5}_{\eta =1}$ 它只对 $\text{Game}{4}_{\eta =1}$ 进行了一处修改。即

挑战：挑战者随机选择 $\hat{A}\leftarrow {\mathbb{Z}}_p^{m\times N}$ 和 $\hat{a}\leftarrow {\mathbb{Z}}_p^N$ ，令挑战密文为

$C^{\ast }=\left(\begin{array}{c}\hat{A}\\ {〚B^{\text{T}}\cdot S_2〛}_p\\ \hat{a}\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

在 $\text{Game}{4}_{\eta =1}$ 中， $\tilde{A}\leftarrow {\mathbb{Z}}_p^{m\times N}$ 和 $\tilde{a}\leftarrow {\mathbb{Z}}_p^N$ 是均匀随机的，故 $\tilde{A}+{〚{\bar{A}}^{\text{T}}\cdot \bar{S}〛}_p$ 和 ${\tilde{a}}^{\text{T}}+{〚{{\bar{u}}^{\prime }}^{\text{T}}\cdot \bar{S}〛}_p+{〚{v^{\prime }}^{\text{T}}\cdot S_2〛}_p$ 亦是均匀随机的。故 $\left|\mathrm{Pr}\left[Y_4|\eta =1\right]-\mathrm{Pr}\left[Y_5|\eta =1\right]\right|=\text{negl}\left(\lambda \right)$ 。

$\text{Game}{6}_{\eta =0}$ 相比 $\text{Game}{5}_{\eta =0}$ 只进行了一处修改。即

挑战：挑战者随机选择 $A^{\prime }\leftarrow {\mathbb{Z}}_p^{m\times N}$ ，令挑战密文为

$C^{\ast }=\left(\begin{array}{c}{〚A^{\text{T}}\cdot S_1〛}_p+A^{\prime }\\ \tilde{B}\\ {\hat{b}}^{\text{T}}\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

假设 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 以不可忽略的优势区分 $\text{Game}{5}_{\eta =0}$ 和 $\text{Game}{6}_{\eta =0}$ ，则利用 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 可构造解决 ${\text{LWR}}_{n,q,p}$ 问题的算法 $\mathcal{B}$ 。 $\mathcal{B}$ 的输入是一个 ${\text{LWR}}_{n,q,p}$ 问题实例 $\left(F,Z\right)\in {\mathbb{Z}}_q^{n\times m}\times {\mathbb{Z}}_p^{m\times N}$ 。 $\mathcal{B}$ 模拟挑战者与 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 交互如下：

初始化： $\mathcal{B}$ 令 $\bar{A}=F$ 。

挑战： $\mathcal{B}$ 选择 $S_1\leftarrow {\mathbb{Z}}_q^{n\times N}$ ，令挑战密文为

$C^{\ast }=\left(\begin{array}{c}{〚A^{\text{T}}\cdot S_1〛}_p+Z\\ \tilde{B}\\ {\hat{b}}^{\text{T}}\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

其余的内容 $\mathcal{B}$ 都与 $\text{Game}{5}_{\eta =0}$ 一样进行处置。

若 $Z\in {\mathbb{Z}}_p^{m\times N}$ 是通过密钥 $S\in {\mathbb{Z}}_q^{n\times N}$ 产生的， $C^{\ast }$ 的分布和 $\text{Game}{5}_{\eta =0}$ 中一样。若 $Z\in {\mathbb{Z}}_p^{m\times N}$ 是随机选择的， $C^{\ast }$ 的分布和 $\text{Game}{6}_{\eta =0}$ 中一样。故 $\left|\mathrm{Pr}\left[Y_5|\eta =0\right]-\mathrm{Pr}\left[Y_6|\eta =0\right]\right|={\text{Adv}}_{\mathcal{B}}\left(\lambda \right)$ 。

$\text{Game}{6}_{\eta =1}$ 相比 $\text{Game}{5}_{\eta =1}$ 只进行了一处修改。即

挑战：挑战者随机选择 $B^{\prime }\leftarrow {\mathbb{Z}}_p^{m\times N}$ ，令挑战密文为

$C^{\ast }=\left(\begin{array}{c}\hat{A}\\ B^{\prime }\\ \hat{a}\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

假设 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 以不可忽略的优势区分 $\text{Game}{5}_{\eta =1}$ 和 $\text{Game}{6}_{\eta =1}$ ，则利用 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 可构造解决 ${\text{LWR}}_{n,q,p}$ 问题的算法 $\mathcal{B}$ 。 $\mathcal{B}$ 的输入是一个 ${\text{LWR}}_{n,q,p}$ 问题实例 $\left(F,Z\right)\in {\mathbb{Z}}_q^{n\times m}\times {\mathbb{Z}}_p^{m\times N}$ 。 $\mathcal{B}$ 模拟挑战者与 ${\mathcal{A}}_{\mathrm{Ⅰ}}$ 交互如下：

初始化： $\mathcal{B}$ 令 $B=F$ 。

挑战： $\mathcal{B}$ 令挑战密文为 $C^{\ast }=\left(\begin{array}{c}\hat{A}\\ Z\\ \hat{a}\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 。

其余的内容 $\mathcal{B}$ 都与 $\text{Game}{5}_{\eta =1}$ 一样进行处置。

若 $Z\in {\mathbb{Z}}_p^{m\times N}$ 是由密钥 $S\in {\mathbb{Z}}_q^{n\times N}$ 产生的， $C^{\ast }$ 的分布和 $\text{Game}{5}_{\eta =1}$ 中一样。若 $Z\in {\mathbb{Z}}_p^{m\times N}$ 是随机选择的， $C^{\ast }$ 的分布和 $\text{Game}{6}_{\eta =1}$ 中一样。故 $\left|\mathrm{Pr}\left[Y_5|\eta =1\right]-\mathrm{Pr}\left[Y_6|\eta =1\right]\right|={\text{Adv}}_{\mathcal{B}}\left(\lambda \right)$ 。

$\text{Game}{7}_{\eta =0}$ 相比 $\text{Game}{6}_{\eta =0}$ 只有一处修改。即

挑战：挑战者随机选择 $A^{″}\leftarrow {\mathbb{Z}}_p^{m\times N}$ ，令挑战密文为

$C^{\ast }=\left(\begin{array}{c}{A}^{″}\\ \tilde{B}\\ {\hat{b}}^{\text{T}}\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

在 $\text{Game}{6}_{\eta =0}$ 中， $A^{\prime }\leftarrow {\mathbb{Z}}_p^{m\times N}$ 是均匀随机的，故 ${〚A^{\text{T}}\cdot S_1〛}_p+A^{\prime }$ 亦是均匀随机的。故 $\left|\mathrm{Pr}\left[Y_6|\eta =0\right]-\mathrm{Pr}\left[Y_7|\eta =0\right]\right|=\text{negl}\left(\lambda \right)$ 。

$\text{Game}{7}_{\eta =1}$ 相比 $\text{Game}{6}_{\eta =1}$ 只有一处修改。即

挑战：挑战者随机选择 $C^{\ast }\leftarrow {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 。

在 $\text{Game}{6}_{\eta =1}$ 中 $\left(\begin{array}{c}\hat{A}\\ B^{\prime }\\ \hat{a}\end{array}\right)\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 是均匀随机的，故 $\left(\begin{array}{c}\hat{A}\\ B^{\prime }\\ \hat{a}\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 亦是均匀随机的。故

$\left|\mathrm{Pr}\left[Y_6|\eta =1\right]-\mathrm{Pr}\left[Y_7|\eta =1\right]\right|=\text{negl}\left(\lambda \right)$ 。

在 $\text{Game}{7}_{\eta =1}$ 中，挑战密文 $C^{\ast }\leftarrow {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 是均匀随机的，故 $\left|\mathrm{Pr}\left[Y_7|\eta =1\right]-\frac{1}{2}\right|=0$ 。

$\text{Game}{8}_{\eta =0}$ 只对 $\text{Game}{7}_{\eta =0}$ 进行了一处修改。即

挑战：挑战者随机选择 $C^{\ast }\leftarrow {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 。

在 $\text{Game}{7}_{\eta =0}$ 中 $\left(\begin{array}{c}{A}^{″}\\ \tilde{B}\\ {\hat{b}}^{\text{T}}\end{array}\right)\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 是均匀随机的，故 $\left(\begin{array}{c}{A}^{″}\\ \tilde{B}\\ {\hat{b}}^{\text{T}}\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 亦是均匀随机的。故

$\left|\mathrm{Pr}\left[Y_7|\eta =0\right]-\mathrm{Pr}\left[Y_8|\eta =0\right]\right|=\text{negl}\left(\lambda \right)$ 。

在 $\text{Game}{8}_{\eta =0}$ 中，挑战密文 $C^{\ast }\leftarrow {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 是均匀随机的，故 $\left|\mathrm{Pr}\left[Y_8|\eta =0\right]-\frac{1}{2}\right|=0$ 。

综上，我们有

$\begin{array}{c}{\text{Adv}}_{{\mathcal{A}}_{\mathrm{Ⅰ}}}\left(\lambda \right)=\left|\mathrm{Pr}\left[Y_0\right]-\frac{1}{2}\right|=2\left|\mathrm{Pr}\left[Y_2\right]-\frac{1}{2}\right|\\ \le \left|\mathrm{Pr}\left[Y_2|\eta =0\right]-\frac{1}{2}\right|+\left|\mathrm{Pr}\left[Y_2|\eta =1\right]-\frac{1}{2}\right|\\ =q_{\text{rpk}}\cdot \left|\mathrm{Pr}\left[Y_3|\eta =0\right]-\frac{1}{2}\right|+q_{\text{H}}\cdot \left|\mathrm{Pr}\left[Y_3|\eta =1\right]-\frac{1}{2}\right|\\ =2q_{\text{rpk}}\cdot {\text{Adv}}_{\mathcal{B}}\left(\lambda \right)+2q_{\text{eppk}}\cdot {\text{Adv}}_{\mathcal{B}}\left(\lambda \right)\\ =2\left(q_{\text{rpk}}+q_{\text{eppk}}\right)\cdot {\text{Adv}}_{\mathcal{B}}(\; \lambda \; )\end{array}$

所提出的CLFHE在 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 攻击下是INDr-CPA安全的。即：

定理2 若攻击者 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 在INDr-CPA安全游戏中以优势 ${\text{Adv}}_{{\mathcal{A}}_{\mathrm{Ⅱ}}}\left(\lambda \right)$ 攻破所提出的CLFHE方案，且公钥询问次数为 $q_{\text{rpk}}$ 。则存在以优势 ${\text{Adv}}_{\mathcal{B}}\left(\lambda \right)$ 解决 ${\text{LWR}}_{n,q,p}$ 问题的算法 $\mathcal{B}$ 。其中

${\text{Adv}}_{{\mathcal{A}}_{\mathrm{Ⅱ}}}\left(\lambda \right)\le 2q_{\text{rpk}}\cdot {\text{Adv}}_{\mathcal{B}}\left(\lambda \right)+\text{negl}\left(\lambda \right)$ .

证明：我们基于游戏序列进行证明。并定义 $Y_i$ 为攻击者 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 在Game i中赢得游戏这一事件。

Game 0它是攻击所提出的方案的 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 和挑战者之间的原始INDr-CPA游戏。在这个游戏中， ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 的优势 ${\text{Adv}}_{{\mathcal{A}}_{\mathrm{Ⅱ}}}\left(\lambda \right)=\left|\mathrm{Pr}\left[Y_0\right]-\frac{1}{2}\right|$ 。

Game 1 这个游戏相比Game 0修改了以下三点：

① 初始化：挑战者选择 $i\leftarrow \left\{1,\cdots ,q_{\text{rpk}}\right\}$ 。

② 公钥询问预言机：如果id是第i次公钥询问，挑战者随机选择 $v_i\leftarrow {\mathbb{Z}}_q^n$ ，令 $\bar{u}=\bar{A}\cdot d\mathrm{mod}q$ ，并返回 $p{k}_{id}=\left(v_i,\bar{u}\right)$ 给 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 。否则，挑战者计算 $\left(p{k}_{id},s{k}_{id}\right)\leftarrow \text{KeyGen}\left(mpk,id,d_{id}\right)$ ，并返回 $p{k}_{id}$ 给 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 。

③ 挑战：如果 $i{d}^{\ast }$ 不是第i次询问的公钥预言机，则挑战者中止并输出 $\perp$ 。否则挑战者选择 $S_1\leftarrow {\mathbb{Z}}_q^{n\times N}$ 、 $\bar{S}\leftarrow {\mathbb{Z}}_q^{n\times N}$ 和 $S_2\leftarrow {\mathbb{Z}}_q^{n\times N}$ ，令挑战密文

$C^{\ast }=\left(\begin{array}{c}{〚A^{\text{T}}\cdot S_1〛}_p+{〚{\bar{A}}^{\text{T}}\cdot \bar{S}〛}_p\\ {〚B^{\text{T}}\cdot S_2〛}_p\\ {〚u^{\text{T}}\cdot S_1〛}_p+{〚{\bar{u}}^{\text{T}}\cdot \bar{S}〛}_p+{〚v_i^{\text{T}}\cdot S_2〛}_p\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

Game 1不中止输出 $\perp$ 的概率为 $\mathrm{Pr}\left[\neg \text{abort}\right]=\frac{1}{q_{\text{rpk}}}$ 。故 $\left|\mathrm{Pr}\left[Y_1\right]-\frac{1}{2}\right|=\frac{1}{q_{\text{rpk}}}\cdot \left|\mathrm{Pr}\left[Y_0\right]-\frac{1}{2}\right|$ 。

Game 2 这个游戏相比Game 1只修改了一处。即

挑战：挑战者随机选择 $\tilde{B}\leftarrow {\mathbb{Z}}_p^{m\times N}$ 和 $\tilde{b}\leftarrow {\mathbb{Z}}_p^N$ ，令挑战密文

$C^{\ast }=\left(\begin{array}{c}{〚A^{\text{T}}\cdot S_1〛}_p+{〚{\bar{A}}^{\text{T}}\cdot \bar{S}〛}_p\\ \tilde{B}\\ {〚u^{\text{T}}\cdot S_1〛}_p+{〚{\bar{u}}^{\text{T}}\cdot \bar{S}〛}_p+{\tilde{b}}^{\text{T}}\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

假设 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 以不可忽略的优势区分Game 1和Game 2，则利用 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 可解决一个 ${\text{LWR}}_{n,q,p}$ 问题实例 $\left(\left(F|f\right),\left(\begin{array}{c}Z\\ z^{\text{T}}\end{array}\right)\right)\in {\mathbb{Z}}_q^{n\times \left(m+1\right)}\times {\mathbb{Z}}_p^{\left(m+1\right)\times N}$ 。于是，有 $\left|\mathrm{Pr}\left[Y_1\right]-\mathrm{Pr}\left[Y_2\right]\right|={\text{Adv}}_{\mathcal{B}}\left(\lambda \right)$ 。

Game 3 相比Game 2只修改了一个地方。即

挑战：挑战者随机选择 $\hat{b}\leftarrow {\mathbb{Z}}_p^N$ ，令挑战密文为

$C^{\ast }=\left(\begin{array}{c}{〚A^{\text{T}}\cdot S_1〛}_p+{〚{\bar{A}}^{\text{T}}\cdot \bar{S}〛}_p\\ \tilde{B}\\ {\hat{b}}^{\text{T}}\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

这里有 $\left|\mathrm{Pr}\left[Y_2\right]-\mathrm{Pr}\left[Y_3\right]\right|=\text{negl}\left(\lambda \right)$ 。

Game 4 相比Game 3只修改了一个地方。即

挑战：挑战者随机选择 $A^{\prime }\leftarrow {\mathbb{Z}}_p^{m\times N}$ ，令挑战密文为

$C^{\ast }=\left(\begin{array}{c}{〚A^{\text{T}}\cdot S_1〛}_p+A^{\prime }\\ \tilde{B}\\ {\hat{b}}^{\text{T}}\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

假设 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 以不可忽略的优势区分Game 3和Game 4，则利用 ${\mathcal{A}}_{\mathrm{Ⅱ}}$ 可解决一个 ${\text{LWR}}_{n,q,p}$ 问题实例 $\left(F,Z\right)\in {\mathbb{Z}}_q^{n\times m}\times {\mathbb{Z}}_p^{m\times N}$ 。于是，有 $\left|\mathrm{Pr}\left[Y_3\right]-\mathrm{Pr}\left[Y_4\right]\right|={\text{Adv}}_{\mathcal{B}}\left(\lambda \right)$ 。

Game 5 相比Game 4只进行了一处修改。即

挑战：挑战者随机选择 $A^{″}\leftarrow {\mathbb{Z}}_p^{m\times N}$ ，令挑战密文为

$C^{\ast }=\left(\begin{array}{c}{A}^{″}\\ \tilde{B}\\ {\hat{b}}^{\text{T}}\end{array}\right)+\mu \cdot G\in {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ .

这里有 $\left|\mathrm{Pr}\left[Y_4\right]-\mathrm{Pr}\left[Y_5\right]\right|=\text{negl}\left(\lambda \right)$ 。

Game 6 只对Game 5进行了一处修改。即

挑战：挑战者随机选择 $C^{\ast }\leftarrow {\mathbb{Z}}_p^{\left(2m+1\right)\times N}$ 。

这里，有 $\left|\mathrm{Pr}\left[Y_5\right]-\mathrm{Pr}\left[Y_6\right]\right|=\text{negl}\left(\lambda \right)$ ，且有 $\left|\mathrm{Pr}\left[Y_6\right]-\frac{1}{2}\right|=0$ 。

综上，我们有

$\begin{array}{c}{\text{Adv}}_{{\mathcal{A}}_{\mathrm{Ⅱ}}}^{\text{CLFHE}}\left(\lambda \right)=\left|\mathrm{Pr}\left[Y_0\right]-\frac{1}{2}\right|=q_{\text{rpk}}\cdot \left|\mathrm{Pr}\left[Y_1\right]-\frac{1}{2}\right|\\ \le q_{\text{rpk}}\cdot \left|\mathrm{Pr}\left[Y_2\right]+{\text{Adv}}_{\mathcal{B}}\left(\lambda \right)-\frac{1}{2}\right|+\text{negl}\left(\lambda \right)\\ \le q_{\text{rpk}}\cdot \left|\mathrm{Pr}\left[Y_4\right]+2{\text{Adv}}_{\mathcal{B}}\left(\lambda \right)-\frac{1}{2}\right|+\text{negl}\left(\lambda \right)\\ \le q_{\text{rpk}}\cdot \left|\mathrm{Pr}\left[Y_6\right]+2{\text{Adv}}_{\mathcal{B}}\left(\lambda \right)-\frac{1}{2}\right|+\text{negl}\left(\lambda \right)\\ \le 2q_{\text{rpk}}\cdot {\text{Adv}}_{\mathcal{B}}\left(\lambda \right)+\text{negl}(\; \lambda \; )\end{array}$

4.3. 参数设置

所提出的CLFHE方案应满足以下条件：

$m\ge 6n\log q$

${\sigma }_1\ge \Vert \tilde{T}\Vert \cdot \omega \left(\sqrt{\log m}\right)$ ，其中 $\Vert \tilde{T}\Vert \le O\left(\sqrt{n\log q}\right)$

${\sigma }_2\ge \omega \left(\sqrt{\log m}\right)$

$p>8{\left(N+1\right)}^L\Delta$ ，其中 $\Delta =\frac{3}{2}+m\sqrt{m}\cdot \left({\sigma }_1+\frac{1}{2}\cdot {\sigma }_2\right)$

$q\ge p\cdot B\cdot n^{\omega (\; 1\; )}$

$q\le 2^n$ ， $q/B\ge 2^{n^{\epsilon }}$ ，其中 $\epsilon >0$ 。

于是，所提出的CLFHE方案的系统参数可设置如下：

$n=n\left(\lambda ,L\right)$

$m=6n^{1+\xi }=O\left(n\cdot L\cdot \log n\right)$

${\sigma }_1=\sqrt{m}\cdot \omega \left(\sqrt{\log n}\right)$

${\sigma }_2=\omega \left(\sqrt{\log n}\right)$

$p=2^{O\left(L\cdot \log n\right)}$

$q=B\cdot 2^{O\left(L\cdot \log n\right)}$ ,

其中 $\xi$ 使得 $n^{\xi }>\lceil \log q\rceil =O\left(L\cdot \log n\right)$ 。

5. 结束语

本文提出了第一个基于LWR问题的CLFHE方案，并在随机预言机模型下证明了它是INDr-CPA安全的。LWR问题是LWE问题的变形。它省掉了LWE问题中的高斯噪声抽样。高斯噪声抽样计算开销非常大。因此本文所提出的CLFHE方案比现有基于LWE问题的CLFHE方案 [6] [7] 具有更高的计算效率。我们接下来会致力于基于所提出的CLFHE方案构造相关安全协议解决物联网、云计算和区块链等面临的安全问题。

参考文献