当$S=(KeyGenS,Sign,Verify)$表示一个签名方案时，其中：

• $KeyGenS$是密钥生成算法。
• $Sign$是签名算法。
• $Verify$是验证算法。

$AkeyGen(sz,I)$：接受素数大小为 sz（以比特为单位）和整数$I$（表示每个数据集中加密的消息数量上限）作为输入。算法计算安全的私钥 sk 和公钥 pk 参数，步骤如下：

1. 从大小为 $\frac{sz}{2}$的四个（安全的）素数 $p_E,q_E,p_S,q_S$中选择，使得 $N_E=p_E\cdot q_E$和 $N_S=p_S\cdot q_S$，同时满足 $\varphi (N_S)=(p_S-1)\cdot (q_S-1)$，其中 $\varphi$表示欧拉函数。
2. 生成群元素 $g_0,g_1,h_1,...,h_I\in {\mathbb{Z}}_{N_S}^{\ast }$和 $g\in {\mathbb{Z}}_{N_E^2}^{\ast }$，其阶为 $N_E$。
3. 选择哈希函数 $H$。
4. 最后，运行 $KeyGenS(sz)$以获取安全的私钥和签名密钥 $(s{k}_S,p{k}_S)$。返回密钥对 $(sk,pk)$，其中 $pk=(N_E,g,N_S,g_0,g_1,h_1,...,h_I,H,p{k}_S)$，而 $sk=(p_E,q_E,p_S,q_S,s{k}_S)$。

$AEncrypt(sk,\tau ,i,m)$是一个概率算法，它接受秘密参数 $sk$、消息 $m\in M$、数据集标识符 $\tau$和索引 $i\in \{1,...,I\}$作为输入，用于计算包含带有验证标记的消息的加密后的密文 $c$。

具体步骤如下：

1. 计算消息 $m$的 Paillier 加密 $C$。
2. 取 $R = H(\tau || i) $，其中 $H$是哈希函数。
3. 计算出元组 $(a,b)\in {\mathbb{Z}}_{N_E}\times {\mathbb{Z}}_{N_E}^{\ast }$，使得 $g^{a}b^{N_{E}} \equiv CR \pmod {N_{E}^{2}} $，其中 $g$是生成群元素。
4. 如果 $\tau$是第一次使用，选择一个长度为 $l\le \frac{sz}{2}$的尚未使用的素数 $e$，满足 $gcd(e{N}_E,\varphi (N_S))=1$，计算其逆 $e^{-1}(\mathrm{mod}\varphi (N_S))$和签名 ${\mu }_e={\text{Sign}}_{s{k}_S}(\tau ||e)$，并将 $(\tau ,e,e^{-1},{\mu }_e)$存储在列表 $L$中。否则，从列表 $L$中取出 $(\tau ,e,e^{-1},{\mu }_e)$。
5. 从 ${\mathbb{Z}}_{e{N}_E}$中随机均匀选择一个元素 $s$，并使用 $p_S$和 $q_S$计算 $x$，使得 $x^{eN_E} \equiv g^{s}0h_i g^{a} \pmod{N_S} $。
6. 返回 $c=(C,e_i,e_i^{-1},{\mu }_e,\tau ,\sigma )$，其中 $\sigma =(a,b,s,x)$是验证标记。

这个算法的主要目的是将消息 $m$加密为一个密文，并在密文中附加了用于验证正确性的标记 $\sigma$。

$AEval(pk,\tau ,f,\{c_i{\}}_{i\in [I]})$: 接受公钥 $pk$、数据集标识符 $\tau$、线性函数 $f=(f_i{)}_{i\in I}$和 $I$个密文 $\{c_i{\}}_{i\in [I]}=(C_i,e_i,e_i^{-1},{\tau }_i,{\sigma }_i)$作为输入。输出是一个密文 $c$。这一步的目的是对给定的一组密文进行验证和线性函数的评估，并生成一个新的密文作为输出。

该算法首先执行一系列检查：

1. 检查是否存在索引 $l\in [I]$使得 $\tau \ne {\tau }_l$，或者签名的验证 $(\text{Verify}(p{k}_S,\tau ||e_l,{\mu }_{e_l})=0)$成立。
2. 检查是否有两个索引 $i\ne j\in [I]$使得 $e_i\ne e_j$。

如果其中一项检查为真，则该算法将中止。否则：

1. 设置 $e=e_1,e^{-1}=e_1^{-1},{\mu }_e={\mu }_{e_1}$并在密文上评估线性函数 $f$。
2. 计算新的密文 $C=\prod _{i=1}^I{C}_i^{f_i}(\mathrm{mod}{N}_E^2)$。
3. 通过对标签进行评估以获得新的标签 $(a,b,s,x)$，计算如下：
   • $a=\sum _{i=1}^I{f}_i{a}_i(\mathrm{mod}{N}_E)$
   • $b=\prod _{i=1}^I{b}_i^{f_i}(\mathrm{mod}{N}_E^2)$
   • $s=\sum _{i=1}^I{f}_i{s}_i(\mathrm{mod}e{N}_E)$
   • $s^{\prime }=(\sum _{i=1}^I{f}_i{s}_i-s)/(e{N}_E)$
   • $a^{\prime }=(\sum _{i=1}^I{f}_i{a}_i-a)/(N_E)$
   • $x=\frac{\prod _{i=1}^I{x}_i^{f_i}}{g_0^{s^{\prime }}{g}_1^{a^{\prime }{e}^{-1}}}\mathrm{mod}{N}_S$
4. 返回密文 $c=(C,e,e^{-1},{\mu }_e,\sigma )$。

$AVerify(pk,\tau ,c,f)$: 接受公钥 $pk$、数据集标识符 $\tau$、密文 $c=(C,a,b,e,s,\tau ,x)$以及线性函数 $f=(f_i{)}_{i\in [I]}$作为输入，用于检测密文 $c$是否为有效或无效。为达到此目的，算法检查以下条件：

$$\{\begin{array}{l}Verify(p{k}_S,\tau \parallel e,{\sigma }_e)=1;\\ a,s\in {\mathbb{Z}}_{e{N}_E};\\ x^{e{N}_E}=g_0^s\prod _{i=1}^I{h}_i^{f_i}{g}_1^a\mathrm{mod}{N}_S;\\ g^a{b}^{N_E}=C\prod _{i=1}^{I}H(\tau \parallel i{)}^{f_i}\mathrm{mod}{N}_E^2;\end{array}$$

如果所有检查都通过，算法输出1（即 $c$是一个有效的密文），否则输出0（即 $c$是一个无效的密文）。

$ADecrypt(sk,\tau ,c,f)$: 接受秘密参数 $sk$、数据集标识符 $\tau$、密文 $c$以及线性函数 $f=(f_i{)}_{i\in [I]}$作为输入，用于计算密文 $c$的解密或 ⊥（如果 $c$是无效的密文）。然后，它通过运行 $AVerify(pk,\tau ,c,f)$来验证 $c$是否为有效密文。如果验证通过，算法返回通过 $Dec(c)$获得的消息 $m$。否则，返回 ⊥。

CMP14还存在一个关于函数$H_p$的小的实际问题，该函数为每个数据集绑定一个唯一的质数。它没有检查这个质数与群${\mathbb{Z}}_{N_S}$的阶是否互素。如果不是这种情况，在AEncrypt过程中计算签名值$x$相当于破解RSA假设，而这被认为是不可行的。