FO-like Transformation

参考文献：

1. [RS91] Rackoff C, Simon D R. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack[C]//Annual international cryptology conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 1991: 433-444.
2. [BR93] Bellare M, Rogaway P. Random oracles are practical: A paradigm for designing efficient protocols[C]//Proceedings of the 1st ACM Conference on Computer and Communications Security. 1993: 62-73.
3. [FO99] Fujisaki, Eiichiro, and Tatsuaki Okamoto. “Secure integration of asymmetric and symmetric encryption schemes.” Annual international cryptology conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999.
4. [OP01] Okamoto T, Pointcheval D. REACT: Rapid enhanced-security asymmetric cryptosystem transform[C]//Topics in Cryptology—CT-RSA 2001: The Cryptographers’ Track at RSA Conference 2001 San Francisco, CA, USA, April 8–12, 2001 Proceedings. Springer Berlin Heidelberg, 2001: 159-174.
5. [CS03] Cramer R, Shoup V. Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack[J]. SIAM Journal on Computing, 2003, 33(1): 167-226.
6. [Dent03] Dent A W. A designer’s guide to KEMs[C]//IMA International Conference on Cryptography and Coding. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003: 133-151.
7. [FO13] Fujisaki E, Okamoto T. Secure integration of asymmetric and symmetric encryption schemes[J]. Journal of cryptology, 2013, 26: 80-101.
8. [HHK17] Hofheinz D, Hövelmanns K, Kiltz E. A modular analysis of the Fujisaki-Okamoto transformation[C]//Theory of Cryptography Conference. Cham: Springer International Publishing, 2017: 341-371.
9. [AOP+17] Albrecht M R, Orsini E, Paterson K G, et al. Tightly secure ring-LWE based key encapsulation with short ciphertexts[C]//Computer Security–ESORICS 2017: 22nd European Symposium on Research in Computer Security, Oslo, Norway, September 11-15, 2017, Proceedings, Part I 22. Springer International Publishing, 2017: 29-46.
10. PKE 安全性的提升方式：Naor-Yung、Fischlin、Fujisaki-Okamoto
11. 量子计算：基本概念

KEM & DEM

[RS91] 给出了 IND-CCA 安全的概念，[BR93] 给出了 ROM 的设计范式。

[CS03] 最先提出了基于 KEM（Asymmetrickey Key Encapsulation Mechanism）和 DEM（Symmetric Data Encapsulation Mechanism）构造出 hybrid constructions 的设计思路。[CS03] 指出，任意的 IND-CCA KEM（比 PKE 更弱）组合上任意的 One-time CCA DEM（对称加密），需要它们的安全属性相互独立，那么就得到了一个 IND-CCA PKE

但是 IND-CCA KEM 通常难以构造（直接归约到底层困难问题是很麻烦的），因此人们往往先构造 IND-CPA KEM，然后再利用某些转换方案得到 IND-CCA KEM

一般地，我们直接将 General-Purpose PKE 作为 KEM 来使用，但是也许可能直接实现 KEM 会更加高效。

之后的 [Dent03] 推广和提出了一些简单高效的 IND-CCA KEM 构造，其中包括了 KEM 版本 FO 和 REACT/GEM 的现代化描述。

Security

[HHK17] 研究了 FO-like，发现目前唯一的从 CPA 安全提升到 IND-CCA 安全的手段，实际上就只有 FO 转换（及其变体）。另外，[FO13] 的归约不紧，并且需要底层 PKE 解密无差错，以及一些其他的更强要求。[HHK17] 给出了从 CPA 到 CCA 的更细粒度转换方案，归约中考虑了解密差错的鲁棒性，将它们相互组合可以得到多种 FO 变体。因此我们先给出一些的安全性描述。

Correctness

原始 [FO99] [FO13] 以及其他变体的缺陷：

1. 在 FO 和 REACT/GEM 的归约中，要求底层 PKE 的解密是完美正确的（perfect correct）。但是 LWE-based PKE 不可避免地引入噪声，导致存在解密失败的情况。
2. 另外，原始 FO 转换的归约是不紧的；REACT/GEM 转换的归约是紧的，但它要求底层 PKE 是 OW-PCA 安全。由于 D-LWE 和 S-LWE 的等价性，导致了许多自然的格密码方案不能够达到 OW-PCA 安全 。

[HHK17] 解释说已有的格密码方案的解密正确性的定义有些微妙，因此他们使用了一种精心挑选的定义，使得它既符合 FO 归约需要，又使得所有格密码也都满足这个定义。

正确性（Correctness）：我们称某个 PKE 是 $\delta$-correct，如果它满足
$$\underset{(sk,pk)\leftarrow Gen(1^{\lambda })}{\mathbb{E}}\left[\underset{m\in M}{\max }\underset{r\leftarrow R}{\mathrm{Pr}}[Dec(sk,c)\ne m\mid c\leftarrow Enc(pk,m;r)]\right]\le \delta$$
这个期望是关于 $(sk,pk)$ 的，而每一个确定的公私钥对，对于每一个消息 $m$，都有关于随机带 $r$ 的解密失败概率。

或者更方便地，可以将它基于游戏来定义：

对于任意的（无界）敌手 $A$，使得：
$$\mathrm{Pr}[CO{R}_{PKE}^A\to 1]\le \delta$$
对于 RO Model，假如敌手可以访问随机神谕 $G,H,\cdots$（若干个），查询次数限制为 $q_G,q_H,\cdots$，那么就有：
$$\mathrm{Pr}[COR\text{-}R{O}_{PKE}^A\to 1]\le \delta (q_G,q_H,\cdots )$$
Standard Model 可以视为 RO Model 的特殊情况（没有 $q_G$ 等输入），函数 $\delta (q_G,q_H,\cdots )$ 成为了某个常数 $\delta$

有效密文（valid ciphertext）：解密函数 $Dec$ 检查密文是否是有效的，对于无效密文，输出特殊符号 $\perp \notin M$ 表示拒绝。

单射性（Injectivity）：对于所有的 $(sk,pk)\leftarrow Gen$，总是有
$$Enc(pk,m;r)=Enc(pk,m^{\prime };r^{\prime })⟹(m,r)=(m^{\prime },r^{\prime }),\forall m,m^{\prime }\in M,r,r^{\prime }\in R$$
也就是说，函数 $Enc(pk,\cdots ):M\times R\to C$ 是单射，必要条件是 $|C|\ge |M|\cdot |R|$ 足够大。此时，每个有效密文都只能解密出唯一的消息，以及唯一的随机带。

刚性（Rigidity）：这是针对确定性 PKE 的，对于所有的 $(sk,pk)\leftarrow Gen$，总是有
$$Dec(sk,c)=\perp \text{ or }Enc(pk,Dec(sk,c))=c$$
也就是说，除了非法的密文，有效密文总是可以解密出正确的消息，不存在解密错误。注意区分：拒绝（识别非法密文并输出特殊符号）、失败（解密出的结果与原始消息不一致）。

$\gamma$-Spread：我们定义密文 $Enc(pk,m;r)$ 的最小熵
$$\gamma (pk,m):=-\log \underset{c\in C}{\max }\underset{r\leftarrow R}{\mathrm{Pr}}[Enc(pk,m;r)=c]$$
如果存在常数 $\gamma$ ，满足 $\gamma (pk,m)\ge \gamma ,\forall (pk,sk)\leftarrow Gen,\forall m\in M$。这直接导致了
$$\underset{r\leftarrow R}{\mathrm{Pr}}[Enc(pk,m;r)=c]\le 2^{-\gamma },\forall c\in C$$
即对于固定的 $(sk,pk)$ 和 $m$，随机带 $r$ 使得此消息的加密是高熵的。

OW & IND

One-Way 安全性（OW）：这是比 IND 更强的攻击目标，要求敌手根据密文 $c^{\ast }\leftarrow Enc(pk,m^{\ast };r)$，找出消息 $m^{\prime }\in M$，满足 $m^{\prime }=Dec(sk,c^{\ast })$

Indistinguishability 安全性（IND）：只要求敌手无法区分 $c^{\ast }$ 是哪个消息 $m_0,m_1$ 的加密。攻击难度比 OW 更低，这是更强的安全性要求。

PCA & VA & PCVA

现在我们考虑攻击手段，也就是敌手能够访问某些神谕

1. 明文检查神谕（Plaintext Checking Oracle）：输入密文 $c$ 和消息 $m$，检查消息 $m$ 是否就是密文 $c$ 所加密的，记为 $Pco(m,c)$
2. 密文有效性神谕（Ciphertext Validity Oracle）：输入密文 $c$，检查密文 $c$ 是否会输出 $\perp$，记为 $Cvo(c)$

当然，需要约束下神谕的能力：

• 明文检查神谕只能回答 $m\in M$ 的那些请求，对于请求 $(m\notin M,c)$ 应当回复 $\perp$ 而非 $0/1$，否则 $Pco(\perp ,c)$ 就完全模拟了 $Cvo(c)$
• 密文有效性神谕对于请求 $c=c^{\ast }$ 应当回复 $\perp$ 而非 $0/1$，否则 $Cvo(c^{\ast })$ 就可以用于区分 $c^{\ast }$ 是随机生成的（如果它是非法密文）还是正确加密的（必然是有效密文）

现在我们定义 PKE 的 OW-ATK 安全性，其中的 ATK 标志着敌手可以访问哪些神谕：

对应的游戏是：

而 IND-CPA PKE 和 IND-CCA KEM 安全性的定义，是很自然的，游戏为：

QROM

量子力学的基本概念：量子比特、量子寄存器、标准正交计算基、叠加态、测量、坍缩。

量子神谕（Quantum Oracles）：它是一个映射
$$|x⟩|y⟩\mapsto |x⟩|y\oplus f(x)⟩$$
其中的 f : { 0 , 1 } n → { 0 , 1 } m f:\{0,1\}^n \to \{0,1\}^m f:{0,1}n→{0,1}m 是待查询的函数， x ∈ { 0 , 1 } n x \in \{0,1\}^n x∈{0,1}n 是经典输入（叠加在寄存器 $|x⟩$ 中）， f ( x ) ∈ { 0 , 1 } m f(x) \in \{0,1\}^m f(x)∈{0,1}m 是经典输出。

量子敌手（Quantum Adversaries）：记为 $A^{|f⟩}$，它查询 $f$ 时利用序列 $U\circ f$，其中的 $U$ 是酉算子。

Quantum Random Oracle Model：随机神谕是量子访问的（quantum access），而其他的神谕都是经典访问的（classical access），包括 Pco、Cvo、Dec 都是经典的。

有文章指出，不存在量子敌手 $A^{|f⟩}$，仅仅量子查询 $q$ 次量子神谕 $|f⟩$，就将它从 $2q$-wise independent function 区分出来。因此，量子随机神谕 $|G⟩$ 可以被视为一个有限域 $GF(2^m)$ 上度数为 $2q_H$ 的随机多项式，将查询 QRO 视为对这个随机多项式的求值。

QROM 下的解密失败率的定义为
$$\mathrm{Pr}[COR\text{-}QR{O}_{PKE}^A\to 1]\le \delta (q_G)$$
对应的游戏是

Fine-Grained FO

[HHK17] 给出了细粒度的变换，先从 OW-CPA 构造出 IND-CPA 或者 OW-PCA，然后再继续构造出 IND-CCA，他们的归约比之前的工作更紧。

将这些细粒度转换相互组合，可以获得多种 FO-like 变换：

它的归约算法中考虑了解密失败率的影响，并且 ROM 下的归约过程比之前的工作更紧。不过 QROM 下的归约是十分不紧的，这是个 Open Problem。

T 变换

采取了去随机化（Derandomization）和重加密（Re-encryption）的结构，

1. 它将任意的 OW-CPA PKE 转化为 OW-PCA det.PKE
2. 如果底层 PKE 额外满足 IND-CPA，那么 ROM 归约是紧的
3. 如果底层 PKE 额外满足 $\gamma$-spraed，那么得到的 det.PKE 也是 OW-VA 的

Encrypt-with-Hash construction：给定底层加密方案 $PKE$ 和哈希函数 $G$，输出的 $PK{E}_1=T[PKE,G]$ 是一个确定性的加密方案。

加密：将 $G(m)$ 作为随机带，
$$En{c}_1(pk,m):=Enc(pk,m;G(m))$$
解密：先计算 $m^{\prime }\leftarrow Dec(sk,c)$，然后使用重加密检查密文的有效性，
$$De{c}_1(sk,c):=\{\begin{array}{rlr}{m}^{\prime },& & [En{c}_1(pk,m^{\prime })=c]\\ \perp ,& & [En{c}_1(pk,m^{\prime })\ne c]\end{array}$$
在 ROM 下，从 OW-CPA 转换到 OW-PCA 的归约是不紧的，

在 ROM 下，从 IND-CPA 转换到 OW-PCA 的归约是紧的，

在 QROM 下，变换 T 也是安全的，不过归约是不紧的，

U 变换

[HHK17] 根据隐式/显式拒绝，以及产生共享秘钥的计算方式，给出了四种变换，

• 它们将 OW-PCA PKE 转化为 IND-CCA KEM
• 如果 PKE 额外是确定性的，那么就只需它是 OW-CPA 的

一、采取 $K=H(c,m)$ 的转换方案（底层 PKE 任意），封装算法：随机采样 $m\leftarrow M$，
$$Encaps(pk):=(c\leftarrow Enc(pk,m;r),K:=H(c,m))$$
解封装：先计算 $m^{\prime }\leftarrow Dec(sk,c)$，然后检查是否拒绝，

1. 隐式拒绝（implicit rejection）
   $$Decap{s}^{/\perp }(sk,c):=\{\begin{array}{rlr}H(c,m^{\prime }),& & [m^{\prime }\ne \perp ]\\ H(c,s),& & [m^{\prime }=\perp ]\end{array}$$
   其中的 s ∈ { 0 , 1 } n s \in \{0,1\}^n s∈{0,1}n 是随机种子，作为 $sk$ 的一部分

2. 显式拒绝（explicit rejection）
   $$Decap{s}^{\perp }(sk,c):=\{\begin{array}{rlr}H(c,m^{\prime }),& & [m^{\prime }\ne \perp ]\\ \perp ,& & [m^{\prime }=\perp ]\end{array}$$
   这其实就是 KEM 版本的 REACT/GEM 变换，见 [Dent03]

二、采取 $K=H(m)$ 的转换方案（它要求 PKE 是确定性的，比如 T 变换的结果），封装算法：随机采样 $m\leftarrow M$，
$$Encap{s}_m(pk):=(c\leftarrow det.Enc(pk,m),K:=H(m))$$
解封装：先计算 $m^{\prime }\leftarrow Dec(sk,c)$，然后检查是否拒绝，

1. 隐式拒绝（implicit rejection）
   $$Decap{s}_m^{/\perp }(sk,c):=\{\begin{array}{rlr}H(m^{\prime }),& & [m^{\prime }\ne \perp ]\\ H(c,s),& & [m^{\prime }=\perp ]\end{array}$$
   其中的 s ∈ { 0 , 1 } n s \in \{0,1\}^n s∈{0,1}n 是随机种子，作为 $sk$ 的一部分

2. 显式拒绝（explicit rejection）
   $$Decap{s}_m^{\perp }(sk,c):=\{\begin{array}{rlr}H(m^{\prime }),& & [m^{\prime }\ne \perp ]\\ \perp ,& & [m^{\prime }=\perp ]\end{array}$$
   这其实就是 KEM 版本的原始 FO 变换，见 [Dent03]

在 ROM 下，变换 $U^{\perp }$ 的归约是紧的，

在 ROM 下，变换 $U^{/\perp }$ 的归约是紧的，

在 ROM 下，变换 $U_m^{\perp }$ 的归约是紧的，需要 PKE 是 det 的

在 ROM 下，变换 $U_m^{/\perp }$ 的归约是紧的，需要 PKE 是 det 的

在 QROM 下 U 变换不工作。

FO-like KEM

现在，我们组合 T 变换、U 变换，可以得到四种 FO 变换：

在 ROM 下，综合 T 变换以及 U 变换的归约结果，给出 IND-CCA 敌手的最终优势，以及相关参数的选取建议：

QU 变换

可以证明 T 变换在 QROM 下依然工作，但是上述的四种 U 变换并不行。略微修改 $U_m^{\perp }$，就可以获得量子下安全的转换方案。

封装算法：随机采样 $m\leftarrow M$，密文中额外添加 $m$ 的摘要 $d$，要求 $H^{\prime },H$ 是独立的 QRO，
$$QEncap{s}_m(pk):=(ct:=(c\leftarrow Enc(pk,m),d:=H^{\prime }(m)),K:=H(m))$$
解封装：

1. 显式拒绝：先计算 $m^{\prime }\leftarrow Dec(sk,(c,d))$，然后检查是否拒绝，
   $$QDecap{s}_m^{\perp }(sk,c):=\{\begin{array}{rlr}H(m^{\prime }),& & [m^{\prime }\ne \perp ]\wedge [H^{\prime }(m^{\prime })=d]\\ \perp ,& & [m^{\prime }=\perp ]\vee [H^{\prime }(m^{\prime })\ne d]\end{array}$$

2. 隐式拒绝：先计算 $m^{\prime }\leftarrow Dec(sk,(c,d))$，然后检查是否拒绝，
   $$QDecap{s}_m^{/\perp }(sk,c):=\{\begin{array}{rlr}H(m^{\prime }),& & [m^{\prime }\ne \perp ]\wedge [H^{\prime }(m^{\prime })=d]\\ H((c,d),s),& & [m^{\prime }=\perp ]\vee [H^{\prime }(m^{\prime })\ne d]\end{array}$$

在 QROM 下，变换 $Q{U}_m^{\perp }$ 的归约是不紧的，注意这里不再需要 PKE 是 det 的，

在 QROM 下，变换 $Q{U}_m^{/\perp }$ 的归约是不紧的，注意这里也不需要 PKE 是 det 的，

另外，在 ROM 下两者都是紧的。

Quantum KEM

现在，我们组合 T 变换、QU 变换，可以得到两种 QFO 变换：

上述的 $G,H,H^{\prime }$ 的输入都是同一个 $m$，因此实例化的时候可以使用一个输出足够长的 Hash 函数（NTTRU 的思路），统一地计算出随机摘要，然后切分成 3 块来分别使用。

S 变换

因为 T 变换从 OW-CPA 到 IND-CPA 是不紧的，[HHK17] 给出了一种 trade-off between efficiency and tightness.，利用多个独立的 PKE 密文，使得归约时嵌入 OW-CPA 挑战时更加容易，猜测次数变少，从而减小了损失因子。

加密：随机采样 $x_1,\cdots ,x_l$，以及随机带 $r_1,\cdots ,r_l$，
$$En{c}_l(pk,m):=(m\oplus F(x_1,\cdots ,x_l),Enc(pk,x_1;r_1),\cdots ,Enc(pk,x_l;r_l))$$
解密：计算 $x_i^{\prime }\leftarrow Dec(sk,c_i),\forall i=1,\cdots ,l$，
$$De{c}_l(sk,(c_0,c_1,\cdots ,c_l))=c_0\oplus F(x_1^{\prime },\cdots ,x_l^{\prime })$$
在 ROM 下，从 OW-CPA 到 IND-CPA 是紧的，代价是计算效率增加、解密失败率增加，

它在 QROM 下不工作。

Reduce RLWE to IND-CCA

[AOP+17] 使用底层 RLWE-based PKE 特有的弱同态性质，在 ROM 下直接将 RLWE 归约到了 IND-CCA KEM，并不存在中间的 IND-CPA PKE，获得了紧的归约。它不是通用的转换，仅仅适用于格密码，他们称之为 LIMA（LattIce MAthematics）。对比 [Dent03] 的通用结果是不紧的。

此外，LIMA 的 IND-CCA KEM 相较于 IND-CPA PKE 并没有 ciphertext overhead，两者的通信开销是完全一样的。

首先，构造 IND-CPA 安全的 RLWE-based PKE，

然后，简单地根据 [Dent03] 的现代化 FO-KEM 描述，将它转化为 IND-CCA KEM，

不过，如果直接应用 [Dent03] 的通用归约结果（从 OW-CPA 到 IND-CCA），它是不紧的。[HHK17] 已经证明了 [Dent03] 的通用构造对于 IND-CPA 是紧的。而恰好上述的 RLWE-based PKE 是紧归约到 RLWE 问题的，因此 [AOP+17] 完全可以视为 [HHK17] 的一个特例。

针对于 LWE 的特殊性，[AOP+17] 给出了一个不通用的紧归约，

其中的 $Ad{v}^{LWE}$ 游戏是：