ACWC：Worst-Case to Average-Case Decryption Error

本文主要是介绍ACWC：Worst-Case to Average-Case Decryption Error，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考文献：

1. [LS19] Lyubashevsky V, Seiler G. NTTRU: Truly Fast NTRU Using NTT[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019: 180-201.
2. [DHK+23] Duman J, Hövelmanns K, Kiltz E, et al. A thorough treatment of highly-efficient NTRU instantiations[C]//IACR International Conference on Public-Key Cryptography. Cham: Springer Nature Switzerland, 2023: 65-94.
3. [KP23] Kim J, Park J H. NTRU+: compact construction of NTRU using simple encoding method[J]. IEEE Transactions on Information Forensics and Security, 2023.
4. NTRU 加密方案
5. NTTRU：兼容 NTT 算法
6. FO-like Transformation in QROM

自从 [LS19] 提出了 NTT-friendly NTRU-based KEM，其计算效率终于可以和 MLWE/RLWE-based KEM 相竞争，并且 NTRU 具有更紧凑的密文（但是使用模切换之后并不明显）。但是其 Worst-Case Decryption Error 远远大于 Average-Case Decryption Error，这可能被 decryption-error attacks 所利用，导致私钥信息的泄露。

多项式环 $R_q={\mathbb{Z}}_q[X]/(F(X))$，NTRU 的私钥形如 $f=p{f}^{\prime }+1$，公钥形如 $h=pg/f$，其中 $p$ 是明文模数。加密是 $c=hr+m\in R_q$，其中 $r\leftarrow \eta$ 是短的随机多项式，$m\in R_p$ 是消息。解密是 $[fc{]}_p\in R_p$，只要满足 $\Vert p(gr+f^{\prime }m)+m{\Vert }_{\infty }<q/2$ 即可解密正确。

PKE 最基本的要求是 Average-Case Decryption Error 可忽略。为了抵御 decryption-error attacks，还需要保证 Worst-Case Decryption Error 也是可忽略的。

• 在 third-round NTRU 中，设置 $m,r\leftarrow {\psi }_k$ 并选取相对较大的 $q$，获得了 perfect correctness error，从而 Worst-Case Decryption Error 也是零。
• 在 NTTRU 中，使用更小空间中的消息 $m^{\prime }\in M$ 生成 $m=H(m^{\prime })\in R_p$，然后使用 NTRU 加密 $m$，使用 $G(m)$ 对消息 $m^{\prime }$ 做一次一密。由于明文空间缩小了，于是随机的 $(sk,pk)$ 存在某些 $m^{\prime }$ 使得解密失败的概率可忽略。

Worst-Case to Average-Case Decryption Error

[DHK+23] 提出了两种转换方法，它们都将 Average-Case OW-CPA PKE 转换到 Worst-Case OW-CPA PKE，在 ROM 以及 QROM 都工作，安全归约请看论文。

ACWC0

这个方法类似于 [LS19] 或者 [FO99]，先将随机数用 PKE 加密，然后再把消息用随机数加密，这两部分组成了最终的密文。

好处：没有解密失败率的损失，支持任意分布的消息。

坏处：密文携带的一些冗余（比如 256-bit 的协商密钥）。

GOTP

[DHK+23] 定义了 on-time pad 的一般化：

最简单的 GOTP 就是：设置 X , U , Y = { 0 , 1 } n X,U,Y = \{0,1\}^n X,U,Y={0,1}n，以及 ψ X , ψ Y , ψ U = U ( { 0 , 1 } n ) \psi_X,\psi_Y,\psi_U = \mathcal U(\{0,1\}^n) ψX​,ψY​,ψU​=U({0,1}n)，这就是 on-time pad 本身。

ACWC

这个转换把 PKE 的明文空间分为 $M=M_1\times M_2$，对应的分布是 ${\psi }_M={\psi }_{M_1}\times {\psi }_{M_2}$。假设消息空间是 $M^{\prime }$，给定 $GOTP:M^{\prime }\times U\to M_2$ 以及随机神谕 $F:M_1\to U$。转换过程是：

好处：密文长度不变。

坏处：解密失败率有损失，消息必须服从 GOTP 所要求的分布。

NTRU

基于 $RNTR{U}_{\eta }$（KeyGen 中的 $(f,h=pg/f)$ 实例）和 $RLW{E}_{\eta }$（Enc 中的 $(h,c=hr+m)$ 实例），

1. 设置 $p=2$ 以及 $\eta ={\psi }_2$，利用 ACWC 把对应的 OW-CPA NTRU 转换成 OW-CPA NTRU-A，然后使用 FO 把它转换成 IND-CCA KEM
2. 设置 $p=3$ 以及 η = U ( { − 1 , 0 , 1 } ) \eta=\mathcal U(\{-1,0,1\}) η=U({−1,0,1})，利用 ACWC 把对应的 OW-CPA NTRU 转换成 OW-CPA NTRU-B，然后使用 FO 把它转换成 IND-CCA KEM
3. 设置 $p=3$ 以及 ${\psi }_2\mathrm{mod}{}^{\pm }3$，利用 ACWC 把对应的 OW-CPA NTRU 转换成 OW-CPA NTRU-C，然后使用 FO 把它转换成 IND-CCA KEM

Semi-generalized One-time Pad

[KP23] 针对 NTRU 天然具有的 Randomness Recoverability（不需要 $f$，只给定 $m$，则 $r=(c-m)h^{-1}$）、Message Recoverability（不需要 $f$，只给定 $r$，则 $m=c-hr$）、Injectivity 性质，提出了更简单的 GOLP，并且移除了 FO 中的 Re-encryption 步骤。

SOLP

[KP23] 提出了 GOTP 的一种简单变体：

它只需要保证消息的隐藏性，对于随机性的要求从隐藏性替换为了刚性。

ACWC2

[KP23] 利用 SOTP 给出了新的 ACWC 转换：

它把 Average-Case OW-CPA PKE 转换到 Worst-Case IND-CPA PKE，在 ROM 和 QROM 都工作，并且比 ACWC 更紧。安全归约请看论文。

FO-Equivalent Transform Without Re-encryption

进一步的，利用 PKE 的 MR 和 RR 性质，可以消除 FO 中的 Re-encryption 步骤，直接比较 RO 产生的加密随机带即可。

在原始的 FO 转换中，强制敌手的解密查询的输入是 well-formed 密文（用 Enc Orcale 获得），从而不泄露额外的知识。即使 $m^{\prime }=m$，对于不同的 $r^{\prime \prime }\ne r$，也不能保证 $c=Enc(pk,m^{\prime };r^{\prime \prime })$，因此 Re-encryption 是不可缺少的。但是因为 NTRU 具有 RR（实际构造中用到）和 MR（归约中用到）性质，那么 $(m^{\prime },r^{\prime })$ 都可以从密文中恢复，从而只需测试 $r^{\prime }=r^{\prime \prime }$ 即可。

NTRU+

SOTP 实例化：

使用 $p=3$ 和 $\eta ={\psi }_1$， 利用 ACWC2 将对应的 OW-CPA NTRU转化为 INC-CPA NTRU+，最后使用 ${\overline{FO}}^{\perp }$ 转化为 IND-CCA KEM

这篇关于ACWC：Worst-Case to Average-Case Decryption Error的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---