FO-like Transformation in QROM Oracle Cloning

2023-12-09 06:10

本文主要是介绍FO-like Transformation in QROM Oracle Cloning,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

参考文献:

  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. [HNP+03] Howgrave-Graham N, Nguyen P Q, Pointcheval D, et al. The impact of decryption failures on the security of NTRU encryption[C]//Annual International Cryptology Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003: 226-246.
  8. [BDF+11] Boneh D, Dagdelen Ö, Fischlin M, et al. Random oracles in a quantum world[C]//Advances in Cryptology–ASIACRYPT 2011: 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings 17. Springer Berlin Heidelberg, 2011: 41-69.
  9. [FO13] Fujisaki E, Okamoto T. Secure integration of asymmetric and symmetric encryption schemes[J]. Journal of cryptology, 2013, 26: 80-101.
  10. [TU16] Targhi E E, Unruh D. Post-quantum security of the Fujisaki-Okamoto and OAEP transforms[C]//Theory of Cryptography: 14th International Conference, TCC 2016-B, Beijing, China, October 31-November 3, 2016, Proceedings, Part II 14. Springer Berlin Heidelberg, 2016: 192-216.
  11. [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.
  12. [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.
  13. [JZC+18] Jiang H, Zhang Z, Chen L, et al. IND-CCA-secure key encapsulation mechanism in the quantum random oracle model, revisited[C]//Advances in Cryptology–CRYPTO 2018: 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceedings, Part III 38. Springer International Publishing, 2018: 96-125.
  14. [BDG20] Bellare M, Davis H, Günther F. Separate your domains: NIST PQC KEMs, oracle cloning and read-only indifferentiability[C]//Advances in Cryptology–EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part II 30. Springer International Publishing, 2020: 3-32.
  15. PKE 安全性的提升方式:Naor-Yung、Fischlin、Fujisaki-Okamoto
  16. 量子计算:基本概念

文章目录

  • KEM & DEM
  • Security
    • Correctness
    • OW & IND
    • PCA & VA & PCVA
  • QROM
  • Fine-Grained FO
    • T 变换
    • U 变换
    • FO-like KEM
    • QU 变换
    • Quantum KEM
    • S 变换
  • Reduce RLWE to IND-CCA
  • Remove the Additional Hash
    • qPCA & qPVCA & DS Security
    • Modular FO in QROM
  • Oracle Cloning
    • Domain Separation
    • Oracle Cloning Functor

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 版本 FOREACT/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,如果它满足
E ( s k , p k ) ← G e n ( 1 λ ) [ max ⁡ m ∈ M Pr ⁡ r ← R [ D e c ( s k , c ) ≠ m ∣ c ← E n c ( p k , m ; r ) ] ] ≤ δ \underset{(sk,pk)\gets Gen(1^\lambda)}{\mathbb E} \left[ \max_{m \in M} \underset{r \gets R}{\Pr}[Dec(sk,c) \neq m \mid c \gets Enc(pk,m;r)] \right] \le \delta (sk,pk)Gen(1λ)E[mMmaxrRPr[Dec(sk,c)=mcEnc(pk,m;r)]]δ
这个期望是关于 ( s k , p k ) (sk,pk) (sk,pk) 的,而每一个确定的公私钥对,对于每一个消息 m m m,都有关于随机带 r r r 的解密失败概率。

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

在这里插入图片描述

对于任意的(无界)敌手 A A A,使得:
Pr ⁡ [ C O R P K E A → 1 ] ≤ δ \Pr[COR_{PKE}^A \to 1] \le \delta Pr[CORPKEA1]δ
对于 RO Model,假如敌手可以访问随机神谕 G , H , ⋯ G,H,\cdots G,H,(若干个),查询次数限制为 q G , q H , ⋯ q_G,q_H,\cdots qG,qH,,那么就有:
Pr ⁡ [ C O R - R O P K E A → 1 ] ≤ δ ( q G , q H , ⋯ ) \Pr[COR\text-RO_{PKE}^A \to 1] \le \delta(q_G,q_H,\cdots) Pr[COR-ROPKEA1]δ(qG,qH,)
Standard Model 可以视为 RO Model 的特殊情况(没有 q G q_G qG 等输入),函数 δ ( q G , q H , ⋯ ) \delta(q_G,q_H,\cdots) δ(qG,qH,) 成为了某个常数 δ \delta δ

有效密文(valid ciphertext):解密函数 D e c Dec Dec 检查密文是否是有效的,对于无效密文,输出特殊符号 ⊥ ∉ M \perp \notin M /M 表示拒绝。

单射性(Injectivity):对于所有的 ( s k , p k ) ← G e n (sk,pk) \gets Gen (sk,pk)Gen,总是有
E n c ( p k , m ; r ) = E n c ( p k , m ′ ; r ′ ) ⟹ ( m , r ) = ( m ′ , r ′ ) , ∀ m , m ′ ∈ M , r , r ′ ∈ R Enc(pk,m;r) = Enc(pk,m';r') \Longrightarrow (m,r)=(m',r'),\,\, \forall m,m'\in M,r,r'\in R Enc(pk,m;r)=Enc(pk,m;r)(m,r)=(m,r),m,mM,r,rR
也就是说,函数 E n c ( p k , ⋯ ) : M × R → C Enc(pk,\cdots):M \times R \to C Enc(pk,):M×RC 是单射,必要条件是 ∣ C ∣ ≥ ∣ M ∣ ⋅ ∣ R ∣ |C| \ge |M| \cdot |R| CMR 足够大。此时,每个有效密文都只能解密出唯一的消息,以及唯一的随机带。

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

γ \gamma γ-Spread:我们定义密文 E n c ( p k , m ; r ) Enc(pk,m;r) Enc(pk,m;r)最小熵
γ ( p k , m ) : = − log ⁡ max ⁡ c ∈ C Pr ⁡ r ← R [ E n c ( p k , m ; r ) = c ] \gamma(pk,m) := -\log\max_{c \in C} \underset{r \gets R}{\Pr}[Enc(pk,m;r)=c] γ(pk,m):=logcCmaxrRPr[Enc(pk,m;r)=c]
如果存在常数 γ \gamma γ ,满足 γ ( p k , m ) ≥ γ , ∀ ( p k , s k ) ← G e n , ∀ m ∈ M \gamma(pk,m) \ge \gamma,\,\, \forall(pk,sk)\gets Gen,\,\, \forall m \in M γ(pk,m)γ,(pk,sk)Gen,mM。这直接导致了
Pr ⁡ r ← R [ E n c ( p k , m ; r ) = c ] ≤ 2 − γ , ∀ c ∈ C \underset{r \gets R}{\Pr}[Enc(pk,m;r) = c] \le 2^{-\gamma},\,\, \forall c \in C rRPr[Enc(pk,m;r)=c]2γ,cC
即对于固定的 ( s k , p k ) (sk,pk) (sk,pk) m m m,随机带 r r r 使得此消息的加密是高熵的

OW & IND

One-Way 安全性(OW):这是比 IND 更强的攻击目标,要求敌手根据密文 c ∗ ← E n c ( p k , m ∗ ; r ) c^* \gets Enc(pk,m^*;r) cEnc(pk,m;r),找出消息 m ′ ∈ M m' \in M mM,满足 m ′ = D e c ( s k , c ∗ ) m'=Dec(sk,c^*) m=Dec(sk,c)

Indistinguishability 安全性(IND):只要求敌手无法区分 c ∗ c^* c 是哪个消息 m 0 , m 1 m_0,m_1 m0,m1 的加密。攻击难度比 OW 更低,这是更强的安全性要求。

PCA & VA & PCVA

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

  1. 明文检查神谕(Plaintext Checking Oracle):输入密文 c c c 和消息 m m m,检查消息 m m m 是否就是密文 c c c 所加密的,记为 P c o ( m , c ) Pco(m,c) Pco(m,c)
  2. 密文有效性神谕(Ciphertext Validity Oracle):输入密文 c c c,检查密文 c c c 是否会输出 ⊥ \perp ,记为 C v o ( c ) Cvo(c) Cvo(c)

当然,需要约束下神谕的能力:

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

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

在这里插入图片描述

对应的游戏是:

在这里插入图片描述

IND-CPA PKEIND-CCA KEM 安全性的定义,是很自然的,游戏为:

在这里插入图片描述

QROM

[BDF+11] 给出了 Quantum ROM 的概念。量子力学的基本概念:量子比特、量子寄存器、标准正交计算基、叠加态、测量、坍缩。

量子神谕(Quantum Oracles):它是一个映射
∣ x ⟩ ∣ y ⟩ ↦ ∣ x ⟩ ∣ y ⊕ f ( x ) ⟩ |x\rangle|y\rangle \mapsto |x\rangle|y\oplus f(x)\rangle xyxyf(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 ⟩ |x\rangle x 中), f ( x ) ∈ { 0 , 1 } m f(x) \in \{0,1\}^m f(x){0,1}m 是经典输出。

量子敌手(Quantum Adversaries):记为 A ∣ f ⟩ A^{|f\rangle} Af,它查询 f f f 时利用序列 U ∘ f U \circ f Uf,其中的 U U U 是酉算子。

Quantum Random Oracle Model:随机神谕是量子访问的(quantum access),而其他的神谕都是经典访问的(classical access),包括 Pco、Cvo、Dec 都是经典的。

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

QROM 下的解密失败率的定义为
Pr ⁡ [ C O R - Q R O P K E A → 1 ] ≤ δ ( q G ) \Pr[COR\text-QRO_{PKE}^A \to 1] \le \delta(q_G) Pr[COR-QROPKEA1]δ(qG)
对应的游戏是

在这里插入图片描述

Fine-Grained FO

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

在这里插入图片描述

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

在这里插入图片描述

在原始 FO 的归约中,要求底层 PKE 是无差错的。但是对于 Lattice-based PKE 来说,解密失败往往是不可避免的;解密失败不仅仅影响 FO 归约,甚至会提供弱点:[HNP+03] 利用了 NTRU 标准参数集下的解密失败,给出了私钥恢复攻击

在 [HHK17] 的归约中考虑了解密失败率的影响,并且 ROM 下的归约过程比之前的工作更紧。不过 QROM 下的归约是十分不紧的,U 变换甚至在 QROM 下没有给出归约。之后的 [JZC+18] 证明了 [HHK17] 的这些转换都是 QROM 安全的(底层 PKE 的安全性要求更强一点),并且给出了更紧的 QROM 归约。

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:给定底层加密方案 P K E PKE PKE 和哈希函数 G G G,输出的 P K E 1 = T [ P K E , G ] PKE_1=T[PKE,G] PKE1=T[PKE,G] 是一个确定性的加密方案。

加密:将 G ( m ) G(m) G(m) 作为随机带,
E n c 1 ( p k , m ) : = E n c ( p k , m ; G ( m ) ) Enc_1(pk,m) := Enc(pk,m;G(m)) Enc1(pk,m):=Enc(pk,m;G(m))
解密:先计算 m ′ ← D e c ( s k , c ) m'\gets Dec(sk,c) mDec(sk,c),然后使用重加密检查密文的有效性,
D e c 1 ( s k , c ) : = { m ′ , [ E n c 1 ( p k , m ′ ) = c ] ⊥ , [ E n c 1 ( p k , m ′ ) ≠ c ] Dec_1(sk,c) := \left\{\begin{aligned} m',&& [Enc_1(pk,m') = c]\\ \perp,&& [Enc_1(pk,m') \neq c]\\ \end{aligned}\right. Dec1(sk,c):={m,,[Enc1(pk,m)=c][Enc1(pk,m)=c]
在 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 ) K=H(c,m) K=H(c,m) 的转换方案(底层 PKE 任意),封装算法:随机采样 m ← M m \gets M mM
E n c a p s ( p k ) : = ( c ← E n c ( p k , m ; r ) , K : = H ( c , m ) ) Encaps(pk) := (c \gets Enc(pk,m;r), K:=H(c,m)) Encaps(pk):=(cEnc(pk,m;r),K:=H(c,m))
解封装:先计算 m ′ ← D e c ( s k , c ) m' \gets Dec(sk,c) mDec(sk,c),然后检查是否拒绝,

  1. 隐式拒绝(implicit rejection)
    D e c a p s ⊥̸ ( s k , c ) : = { H ( c , m ′ ) , [ m ′ ≠ ⊥ ] H ( c , s ) , [ m ′ = ⊥ ] Decaps^{\not\perp}(sk,c) := \left\{\begin{aligned} H(c,m'),&& [m' \neq \perp]\\ H(c,s),&& [m' = \perp]\\ \end{aligned}\right. Decaps(sk,c):={H(c,m),H(c,s),[m=][m=⊥]
    其中的 s ∈ { 0 , 1 } n s \in \{0,1\}^n s{0,1}n 是随机种子,作为 s k sk sk 的一部分

  2. 显式拒绝(explicit rejection)
    D e c a p s ⊥ ( s k , c ) : = { H ( c , m ′ ) , [ m ′ ≠ ⊥ ] ⊥ , [ m ′ = ⊥ ] Decaps^{\perp}(sk,c) := \left\{\begin{aligned} H(c,m'),&& [m' \neq \perp]\\ \perp,&& [m' = \perp]\\ \end{aligned}\right. Decaps(sk,c):={H(c,m),,[m=][m=⊥]
    这其实就是 KEM 版本的 REACT/GEM 变换,见 [Dent03]

、采取 K = H ( m ) K=H(m) K=H(m) 的转换方案(它要求 PKE 是确定性的,比如 T 变换的结果),封装算法:随机采样 m ← M m \gets M mM
E n c a p s m ( p k ) : = ( c ← d e t . E n c ( p k , m ) , K : = H ( m ) ) Encaps_m(pk) := (c \gets det.Enc(pk,m), K:=H(m)) Encapsm(pk):=(cdet.Enc(pk,m),K:=H(m))
解封装:先计算 m ′ ← D e c ( s k , c ) m' \gets Dec(sk,c) mDec(sk,c),然后检查是否拒绝,

  1. 隐式拒绝(implicit rejection)
    D e c a p s m ⊥̸ ( s k , c ) : = { H ( m ′ ) , [ m ′ ≠ ⊥ ] H ( c , s ) , [ m ′ = ⊥ ] Decaps^{\not\perp}_m(sk,c) := \left\{\begin{aligned} H(m'),&& [m' \neq \perp]\\ H(c,s),&& [m' = \perp]\\ \end{aligned}\right. Decapsm(sk,c):={H(m),H(c,s),[m=][m=⊥]
    其中的 s ∈ { 0 , 1 } n s \in \{0,1\}^n s{0,1}n 是随机种子,作为 s k sk sk 的一部分

  2. 显式拒绝(explicit rejection)
    D e c a p s m ⊥ ( s k , c ) : = { H ( m ′ ) , [ m ′ ≠ ⊥ ] ⊥ , [ m ′ = ⊥ ] Decaps^{\perp}_m(sk,c) := \left\{\begin{aligned} H(m'),&& [m' \neq \perp]\\ \perp,&& [m' = \perp]\\ \end{aligned}\right. Decapsm(sk,c):={H(m),,[m=][m=⊥]
    这其实就是 KEM 版本的原始 FO 变换,见 [Dent03]

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

在这里插入图片描述

在 ROM 下,变换 U ⊥̸ U^{\not\perp} U 的归约是紧的

在这里插入图片描述

在 ROM 下,变换 U m ⊥ U_m^{\perp} Um 的归约是紧的,需要 PKE 是 det 的

在这里插入图片描述

在 ROM 下,变换 U m ⊥̸ U_m^{\not\perp} Um 的归约是紧的,需要 PKE 是 det 的

在这里插入图片描述

在 QROM 下 U 变换不工作。

FO-like KEM

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

在这里插入图片描述

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

在这里插入图片描述

QU 变换

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

封装算法:随机采样 m ← M m \gets M mM,密文中额外添加 m m m 的摘要 d d d,要求 H ′ , H H',H H,H 是独立的 QRO,
Q E n c a p s m ( p k ) : = ( c t : = ( c ← E n c ( p k , m ) , d : = H ′ ( m ) ) , K : = H ( m ) ) QEncaps_m(pk) := (ct:=(c \gets Enc(pk,m), d:=H'(m)), K:=H(m)) QEncapsm(pk):=(ct:=(cEnc(pk,m),d:=H(m)),K:=H(m))
解封装:

  1. 显式拒绝:先计算 m ′ ← D e c ( s k , ( c , d ) ) m' \gets Dec(sk,(c,d)) mDec(sk,(c,d)),然后检查是否拒绝,
    Q D e c a p s m ⊥ ( s k , c ) : = { H ( m ′ ) , [ m ′ ≠ ⊥ ] ∧ [ H ′ ( m ′ ) = d ] ⊥ , [ m ′ = ⊥ ] ∨ [ H ′ ( m ′ ) ≠ d ] QDecaps^{\perp}_m(sk,c) := \left\{\begin{aligned} H(m'),&& [m' \neq \perp] \wedge [H'(m')=d]\\ \perp,&& [m' = \perp] \vee [H'(m')\neq d]\\ \end{aligned}\right. QDecapsm(sk,c):={H(m),,[m=][H(m)=d][m=⊥][H(m)=d]

  2. 隐式拒绝:先计算 m ′ ← D e c ( s k , ( c , d ) ) m' \gets Dec(sk,(c,d)) mDec(sk,(c,d)),然后检查是否拒绝,
    Q D e c a p s m ⊥̸ ( s k , c ) : = { H ( m ′ ) , [ m ′ ≠ ⊥ ] ∧ [ H ′ ( m ′ ) = d ] H ( ( c , d ) , s ) , [ m ′ = ⊥ ] ∨ [ H ′ ( m ′ ) ≠ d ] QDecaps^{\not\perp}_m(sk,c) := \left\{\begin{aligned} H(m'),&& [m' \neq \perp] \wedge [H'(m')=d]\\ H((c,d),s),&& [m' = \perp] \vee [H'(m')\neq d]\\ \end{aligned}\right. QDecapsm(sk,c):={H(m),H((c,d),s),[m=][H(m)=d][m=⊥][H(m)=d]

在 QROM 下,变换 Q U m ⊥ QU_m^{\perp} QUm 的归约是不紧的,注意这里不再需要 PKE 是 det 的,

在这里插入图片描述

在 QROM 下,变换 Q U m ⊥̸ QU_m^{\not\perp} QUm 的归约是不紧的,注意这里也不需要 PKE 是 det 的,

在这里插入图片描述

另外,在 ROM 下两者都是紧的

Quantum KEM

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

在这里插入图片描述

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

S 变换

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

加密:随机采样 x 1 , ⋯ , x l x_1,\cdots,x_l x1,,xl,以及随机带 r 1 , ⋯ , r l r_1,\cdots,r_l r1,,rl
E n c l ( p k , m ) : = ( m ⊕ F ( x 1 , ⋯ , x l ) , E n c ( p k , x 1 ; r 1 ) , ⋯ , E n c ( p k , x l ; r l ) ) Enc_l(pk,m) := (m\oplus F(x_1,\cdots,x_l),Enc(pk,x_1;r_1),\cdots,Enc(pk,x_l;r_l)) Encl(pk,m):=(mF(x1,,xl),Enc(pk,x1;r1),,Enc(pk,xl;rl))
解密:计算 x i ′ ← D e c ( s k , c i ) , ∀ i = 1 , ⋯ , l x_i' \gets Dec(sk,c_i),\forall i=1,\cdots,l xiDec(sk,ci),i=1,,l
D e c l ( s k , ( c 0 , c 1 , ⋯ , c l ) ) = c 0 ⊕ F ( x 1 ′ , ⋯ , x l ′ ) Dec_l(sk,(c_0,c_1,\cdots,c_l)) = c_0 \oplus F(x_1',\cdots,x_l') Decl(sk,(c0,c1,,cl))=c0F(x1,,xl)
在 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] 给出了一个不通用的紧归约

在这里插入图片描述

其中的 A d v L W E Adv^{LWE} AdvLWE 游戏是:

在这里插入图片描述

Remove the Additional Hash

[BDF+11] 给出了 Quantum ROM 的概念,因为 QROM 下的模拟器无法学习敌手的 RO queries 信息(不存在 RO-query List),他们介绍了一种 history-free reduction 技术,并证明了它意味着 QROM 下安全。

[TU16] 提出,在密文上添加额外的保长哈希(additional length-preserving hash),被建模为 RO,那么在归约过程中,模拟器可以使用某独立函数模拟这个 RO,从而不需要私钥,就可以直接给出解密响应。不过有文章认为,似乎这个保长哈希仅仅是归约技巧,并不提供安全性。

[HHK17] 提出的 Modular FO transformations,他们仅仅证明了变换 T 是 QROM 工作的,并没有给出变换 U 在 QROM 下的归约。他们使用了 [TU16] 的技术,在密文上添加额外的哈希函数,证明了变换 QU 是在 QROM 下安全的。

一般来说,为了提供 128 128 128 比特的量子安全性,只需要使得哈希函数的输出长度为 256 256 256 比特。然而,[TU16] 的归约技术强烈依赖于保长哈希,但是消息空间的规模往往远大于 256 256 256 比特(比如 NTRU 的为 1128 1128 1128 比特),导致了密文规模的扩张较大。[JZC+18] 开发了一种新的 QROM 下归约技术,可以使得模拟器无需读取敌手 RO queries,从而移除了这个哈希。他们给出了变换 U 在 QROM 下的归约,并且通过减少 one-way to hiding (OW2H) lemma 的调用次数,给出了比 [HHK17] 的 QFO 更紧的 FO 的归约。

qPCA & qPVCA & DS Security

[JZK+18] 提出了两个量子加强的安全性:qPCAqPVCA,也就是敌手可以量子访问 plaintext checking oracle(Pco),不过 validity checking oracle(Val)依旧是经典的。

在这里插入图片描述

另外,针对于确定性 PKE(简记 DPKE),可以定义一种不标准的安全性:不交的可模拟性(Disjoint Simulatability, DS),

在这里插入图片描述

所有的 DS-secure DPKE 都是 OW-qPCA 安全的,并且如果底层 DPKE 满足这种安全性,那么可以使得转换 U 的 QROM 归约更紧

Modular FO in QROM

[JZK+18] 的结果汇总如下:

在这里插入图片描述

首先是 [HHK17] 的两个 FO 变换的 QROM 归约结果,

  1. 定义 K E M - I : = F O ⊥̸ [ P K E , G , H ] KEM\text-I := FO^{\not\perp}[PKE, G, H] KEM-I:=FO[PKE,G,H],其中 G G G 用于产生底层 PKE 的随机带 G ( m ) G(m) G(m) H H H 用于生成共享秘密 H ( m , c ) H(m,c) H(m,c),它们都建模为 RO
  2. 定义 K E M - I ⁣ I : = F O m ⊥̸ [ P K E , G , H , f ] KEM\text-I\!I := FO^{\not\perp}_m[PKE, G, H, f] KEM-II:=FOm[PKE,G,H,f],其中 G G G 用于产生底层 PKE 的随机带 G ( m ) G(m) G(m) H H H 用于生成共享秘密 H ( m ) H(m) H(m),另外的 f f f 是一族 PRF,用于隐式拒绝 f s ( c ) f_s(c) fs(c),在 [HHK17] 中它被实例为 H ( s , c ) H(s,c) H(s,c)

它们在 QROM 下的归约,比 [HHK17] 的 QFO 更紧

在这里插入图片描述

接下来是变换 T 的 QROM 归约结果,简记 P K E ′ = T [ P K E , G ] PKE'=T[PKE,G] PKE=T[PKE,G],[HHK17] 已经证明了它的转换结果是 QROM 下 OW-CPA 安全的,而 [JZK+18] 进一步证明了它也是 OW-qPCA 安全的

在这里插入图片描述

最后是四个 U 变换的 QROM 归约结果,

  1. 定义 K E M - I ⁣ I ⁣ I : = U ⊥̸ [ P K E ′ , H ] KEM\text-I\!I\!I := U^{\not\perp}[PKE', H] KEM-III:=U[PKE,H],隐式拒绝为 H ( s , c ) H(s,c) H(s,c)
  2. 定义 K E M - I ⁣ V : = U ⊥ [ P K E ′ , H ] KEM\text-I\!V := U^{\perp}[PKE', H] KEM-IV:=U[PKE,H],显式拒绝
  3. 定义 K E M - V : = U m ⊥̸ [ P K E ′ , H , f ] KEM\text-V := U^{\not\perp}_m[PKE', H, f] KEM-V:=Um[PKE,H,f],隐式拒绝为 f s ( c ) f_s(c) fs(c),这里的 f f f 是 PRF
  4. 定义 K E M - V ⁣ I : = U m ⊥ [ P K E ′ , H ] KEM\text-V\!I := U^{\perp}_m[PKE', H] KEM-VI:=Um[PKE,H],显式拒绝

[HHK17] 没能给出它们在 QROM 下的归约,[JZK+18] 采用新的归约技术,给出了它们的 QROM 归约,并且足够紧。

对于 K = H ( m , c ) K=H(m,c) K=H(m,c) 的两个变换,它需要底层 PKE 是 qPCA 以及 qPVCA 安全的,而 [HHK17] 中只要求 PCA 和 PCVA(但 QROM 不工作),

在这里插入图片描述

对于 K = H ( m ) K=H(m) K=H(m) 的两个变换,[JZK+18] 需要的条件和 [HHK17] 一样,

在这里插入图片描述

Oracle Cloning

Domain Separation

[BR93] 明确了 Random Oracle 范式,并给出了 CCA-PKE、Hash-based Sign、FS-type NIZK 的应用。

ROM 范式流程:

  1. 形式化定义密码协议 Π \Pi Π(理想世界),各个参与方可以访问某 Random Oracle
  2. 设计有效的密码协议 P P P(现实世界,但是可访问 RO)
  3. 证明协议 P P P 满足 Π \Pi Π 的定义
  4. 将 RO 替换为某个 Hash 函数

[BR93] 指出,困难问题和密码协议都应当独立于 Hash 函数,否则可以构造出某方案,使得它在 ROM 下可证明安全,但是采取此 Hash 函数的实例化并不安全!

虽然已有的 Hash 函数不一定是好的,但是可以通过一些简单变换,打破它们的结构:

  1. 对输出截断(truncate)或者折叠(fold)
  2. 对输入限制长度,例如 ∣ x ∣ ≤ 256 |x|\le 256 x256
  3. 非标准化的方式调用,例如 H ( x ) → H ( x x ) H(x) \to H(xx) H(x)H(xx)
  4. 首先执行块压缩(block compress),例如 H ′ : { 0 , 1 } 512 → { 0 , 1 } 128 H':\{0,1\}^{512} \to \{0,1\}^{128} H:{0,1}512{0,1}128,设置 H ( H ′ ( x ) ) H(H'(x)) H(H(x))

Oracle Cloning Functor

[BDG20] 指出,密码协议如果使用使用了多个 RO,不同的 RO 实例化应当是相互独立的。否则将存在特别高效的攻击,他们甚至打破了若干个 NIST PQC 1-Round 的 KEM 方案。 在 [HHK17] 的 FO/QFO 中需要使用三个独立的 RO,另外底层 PKE 本身也需要使用一个 RO,一共需要四个随机神谕。现在的问题是,如何只用单个 Hash 函数,安全地实例化 IND-CCA KEM 中的全部神谕。

[BDG20] 形式化了域分离,定义了 “神谕克隆技术”。他们提出了一个强度介于 MRH-indiff 和 reset-indiff 之间的只读不可辨别性(Read-Only Indifferentiability, rd-indiff)的安全框架,可在多阶段游戏中保持安全性,足够 KEM 的需要。

函子 F : S S → E S \textbf F: SS \to ES F:SSES,domain 是一组起始函数(Starting-function Space),range 输一组结束函数(Ending-function Space),函子的不可辨别性指的是, F [ s ] , s ← R E S F[s],s \gets_R ES F[s],sRES 可以模拟 e ← R E S e \gets_R ES eRES,因此使用组合定理(composition theorem)密码协议中的 e e e 可以被 F ( s ) F(s) F(s) 安全地代替。

他们提出了可翻译函子(translating functors)以及它们的(invertibility),

在这里插入图片描述

我们称某函子 F \textbf F F 是可翻译的,如果存在 QT(query translator)和 AT(answer translator),使得 F = TF Q T , A T \textbf F=\textbf{TF}_{QT,AT} F=TFQT,AT。我们称某函子 F \textbf F F 关于工作域 W \mathcal W W 是可逆的,如果存在 QTIATI,使得对于 ∀ e ∈ E S , ∀ W ∈ W \forall e \in ES,\forall W \in \mathcal W eES,WW 都有 TF Q T , A T [ P [ e ] Q T I , A T I ] ( W ) = e ( W ) \textbf{TF}_{QT,AT}[P[e]_{QTI,ATI}](W)=e(W) TFQT,AT[P[e]QTI,ATI](W)=e(W)。[BDG20] 证明了:任意的可逆可翻译函子都满足 rd-indiff 安全的。

他们给出了三种实用的函子:令 s s s 是单个 Hash 函数,我们需要构造出 n n n 个 RO 实例 e ( i , ⋅ ) e(i,\cdot) e(i,)

  • 前缀函子(prefix functor):某个公开确定的向量 p = [ p i ] i ∈ I p=[p_i]_{i \in I} p=[pi]iI,它是无前缀的(prefix-free),即每个 p i p_i pi 都不是其他 p j , j ≠ i p_j,j\neq i pj,j=i 的前缀,那么定义
    F p f ( p ) [ s ] ( i , X ) : = s ( p i ∥ X ) \textbf F_{pf(p)}[s](i,X) := s(p_i\|X) Fpf(p)[s](i,X):=s(piX)

  • 分裂函子(output-splitting functor):假设 s s s 的输出长度满足 l = l 1 + ⋯ + l n l_{}=l_1+\cdots+l_n l=l1++ln,其中 l i l_i li 是各个 e ( i , ⋅ ) e(i,\cdot) e(i,) 的输出长度,设置 L i = l 1 + ⋯ + l i L_i=l_1+\cdots+l_i Li=l1++li,那么定义
    F s p l [ s ] ( i , X ) : = s ( X ) [ L i − 1 + 1 , ⋯ , L i ] \textbf F_{spl}[s](i,X) := s(X)[L_{i-1}+1,\cdots ,L_i] Fspl[s](i,X):=s(X)[Li1+1,,Li]

  • 恒等函子(identity functor):这个函子就直接是
    F i d [ s ] ( i , X ) : = s ( X ) \textbf F_{id}[s](i,X) := s(X) Fid[s](i,X):=s(X)
    但是需要额外约束虚拟域分裂(virtual domain separation),即对于不同的 e ( i , ⋅ ) e(i,\cdot) e(i,) 它们的输入值互不相同。比如强制输入长度分化(length differentiation),即对于不同的 e ( i , ⋅ ) e(i,\cdot) e(i,) 它们的输入长度不同。

此外,[BDG20] 还定义了工作域(working domain)的概念,即使某函子在 full-domain 上不是 rd-indiff 的,在合适的子域上依旧可以实现 rd-indiff 安全性。他们进而提出了兼容工作域的组合定理(working-domain-conscious composition theorem for KEMs),归约是紧的,从而完成 CCA-IND KEM 中的 RO 实例化。

在这里插入图片描述

这篇关于FO-like Transformation in QROM Oracle Cloning的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/472754

相关文章

Mybatis中的like查询

<if test="templateName != null and templateName != ''">AND template_name LIKE CONCAT('%',#{templateName,jdbcType=VARCHAR},'%')</if>

Oracle type (自定义类型的使用)

oracle - type   type定义: oracle中自定义数据类型 oracle中有基本的数据类型,如number,varchar2,date,numeric,float....但有时候我们需要特殊的格式, 如将name定义为(firstname,lastname)的形式,我们想把这个作为一个表的一列看待,这时候就要我们自己定义一个数据类型 格式 :create or repla

ORACLE 11g 创建数据库时 Enterprise Manager配置失败的解决办法 无法打开OEM的解决办法

在win7 64位系统下安装oracle11g,在使用Database configuration Assistant创建数据库时,在创建到85%的时候报错,错误如下: 解决办法: 在listener.ora中增加对BlueAeri-PC或ip地址的侦听,具体步骤如下: 1.启动Net Manager,在“监听程序”--Listener下添加一个地址,主机名写计

Oracle Start With关键字

Oracle Start With关键字 前言 旨在记录一些Oracle使用中遇到的各种各样的问题. 同时希望能帮到和我遇到同样问题的人. Start With (树查询) 问题描述: 在数据库中, 有一种比较常见得 设计模式, 层级结构 设计模式, 具体到 Oracle table中, 字段特点如下: ID, DSC, PID; 三个字段, 分别表示 当前标识的 ID(主键), DSC 当

oracle分页和mysql分页

mysql 分页 --查前5 数据select * from table_name limit 0,5 select * from table_name limit 5 --limit关键字的用法:LIMIT [offset,] rows--offset指定要返回的第一行的偏移量,rows第二个指定返回行的最大数目。初始行的偏移量是0(不是1)。   oracle 分页 --查前1-9

ORACLE语法-包(package)、存储过程(procedure)、游标(cursor)以及java对Result结果集的处理

陈科肇 示例: 包规范 CREATE OR REPLACE PACKAGE PACK_WMS_YX IS-- Author : CKZ-- Created : 2015/8/28 9:52:29-- Purpose : 同步数据-- Public type declarations,游标 退休订单TYPE retCursor IS REF CURSOR;-- RETURN vi_co_co

Oracle主键和外键详解及实用技巧

在 Oracle 数据库中,主键(Primary Key)和外键(Foreign Key)用于维护数据库表之间的数据完整性。 1. 主键(Primary Key) 主键是一列或多列,能够唯一标识表中的每一行。表中只能有一个主键,并且主键列不能为空(即 NOT NULL)。 特性: 唯一性:主键中的每一个值都是唯一的,不能重复。非空性:主键列不能包含 NULL 值。索引:Oracle 自动为

分享MSSQL、MySql、Oracle的大数据批量导入方法及编程手法细节

1:MSSQL SQL语法篇: BULK INSERT      [ database_name . [ schema_name ] . | schema_name . ] [ table_name | view_name ]         FROM 'data_file'        [ WITH       (      [ [ , ] BATCHSIZE = batch_siz

Oracle start with connect BY 死循环

解决办法 检查start with前有没有where条件, 如果有的话,套一层select,再 Oracle start with connect BY

Java调用Oracle存储过程一

一、通过PL/SQL工具连接上Oracle数据库,创建表zx_test_procedure 二、创建存储过程 ①无返回值的存储过程 存储过程为: create or replace procedure testa (para1 in varchar2,para2 in varchar2) as begin insert into zx_test_procedure(i_id,i_n