Ring Homomorphic Encryption Schemes

Abstruct

• FHE schemeの可換環準同型性について
• quantum IND-CCA secureじゃないことをいう

Introduction

• FHE は暗号の聖杯(holy grail) と言われている

  • 任意の計算が暗号化したまま出来るので計算をoutsourceしたい
  • Gen1: Gentryがfirst plausible(もっともな) methodを考えた
    • イデアル格子上に作った
  • Gen2以降: LWE 仮定に基づく
    • noiseがつきまとう -> noise-free なFHEは無いの?
      • 平文空間と暗号空間はringになり, decryptionはring homomorphism
      • そのようなschemeを ring homomorphic encryption scheme と呼ぶ, 考える時は ${\mathbb{F}}_2$ を探せば良い.

• 19: 別の noise-free FHE

  • 非可換な演算でNANDが出来る
  • 暗号文空間: 可換有限環 $R$, 平文空間: $F_2$
    • ${\mathbb{F}}_2$-代数 $\hat{E}(R)$ を取り付けた任意の2つの可換有限環は $R\to {\mathbb{F}}_2$ の準同型を持つ
    • 特に, $\mathrm{dec}:\hat{E}(R)\to {\mathbb{F}}_2$

さらに、べき乗F2代数からF2への任意の環同型は単なる射影なので、Eˆ(R)の直交基底（順列まで一意）を計算し、圧倒的な確率でその射影べき乗を見つけることができ、これが解読鍵の役割を果たすことになる。

本手法は秘密鍵に対する量子攻撃であるため、量子計算で射影要素を求めた後は、古典的に復号を行うことを強調した。もし、復号化アルゴリズムを量子的に実行できるようにすれば、より一般的な結果を得ることができます。例えば、[1]では、任意の（可換）群暗号化方式が量子耐性を持たないことを証明している。しかし，暗号文を復号するためには，毎回，量子アルゴリズムを実行しなければならない．また，[1]の著者らは，より強い安全性概念であるIND-CPAを満たさないことを証明しています．実は，我々のIND-CCA安全性の証明も，全く同じ方法（δ-covering subsets）を使って彼らのケースに修正することができます．この修正は新しい知見をもたらさないので、我々は[1]の均一サンプリング仮定と等価なIND-CCA安全性のケースを使うことにした。

ss2: 有限可換半群の構造
ss3: 有限可換環の構造
ss4: FHE schemeの定義と性質
ss5: 可換半群に対する量子計算
ss6: rFHEでのdecアルゴリズムの計算方法, rFHEがIND-CCA secureでないこと示す
ss7: モノイド代数の構造を明示的に計算

2. Finite commutative semigroups

• $(G,\cdot )$: 可換有限半群
• $g_1^{{}^{\exists }m}=g_2^{{}^{\exists }n}$ の時 $g_1,g_2$ は “powerfully equal” といい, 同値類とする. $g_1{g}_2$
• $G$ が Monoid の時, 全ての元で同値類作れる

rfhe_1

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

Link to original

参考文献

• https://eprint.iacr.org/2018/583.pdf