Floating-Point Homomorphic Encryption

Introduction

浮動小数点数は、計算機で実数を近似的に表現する最も一般的な方法であり、計算機システムや集中的な科学計算で広く利用されています。
浮動小数点数は、x=±s*b^(e-k)のように4つの整数で表現され、bは基底、eは指数、kは精度（符号の有効桁数）、sは0≤s≤b^k-1を満たす.
浮動小数点演算は、通常の演算と、記号への丸めステップで構成されています。
同相暗号化（Homomorphic Encryption:HE）は、暗号化されたデータを復号化せずに同相演算を可能にする暗号方式です。Gentryが同相暗号化方式を発見して以来、Gentryの設計図をもとに多くのHE方式が提案されてきました（[DGHV10,BV11a,BV11b,Bra12,BGV12,GSW13,CLT14,CS15,DM15]など）。しかし、HE方式は実数計算、特に浮動小数点演算の非効率性が高いため、実用化された例は少ない。

loating-Point Homomorphic Encryption

本論文では、2つのメッセージm1, m2の暗号化を入力として、m1+m2とm1m2の最上位ビット（MSBs）の暗号化を出力する暗号文の浮動小数点付加と乗算をサポートする浮動小数点同型暗号化（Floating-Point Homomorphic Encryption: FPHE）方式を構築する一般的な考え方を提案する。
ここでは、古典的なLWEベースの方式[BGV12]をベースに、モジュラス切り替えなどの操作を変更して、レベル付きFPHE方式を具体的に構築します。
2まず、図1のように平文と一緒に右端に暗号化ノイズを配置し、どこかの空間に対して〈c,s〉=m+e(modq)を満たすように暗号化します。
暗号文cから正確な値を復元することはできませんが、挿入されたノイズは浮動小数点演算の際に発生したエラーと考えられます。
この近似値+emは、|e|が十分に小さい場合には、浮動小数点演算で元のメッセージをほぼ同じ精度で置き換えることができます。
入力データが小さすぎたり大きすぎたりする場合は、スケーリングファクタを掛けてメッセージの大きさを符号化し、スケーリングファクタ(または指数)を独立して格納することができます。
本方式の同型演算は、〈cadd,s〉modq≈m1+m2と〈cmult,s〉modq≈m1m2を満足する暗号文を出力する。
乗算処理には、[BV11a,BGV12]で提案されている鍵切換え技術を使用しています。変調度切換え技術は、挿入誤差の大きさを減らすために[BV11a,BGV12]で提案されていますが、我々のスキームでは全く異なる役割を持っています。 このモジュラス切り替え手順と同型演算（図１のような）の構成は、通常の（暗号化されていない）浮動小数点演算を模倣しています。
この方式は精度の面ではほぼ最適であり、暗号化されていない浮動小数点演算の場合と同様に、得られるメッセージの精度が1ビット程度失われます。

FPHEの構築に基づき、定数加算・乗算、積、多項式、多分割逆数を含む回路をホモモルフィックに評価する。本研究では、回路の深さと複雑さを最小化するアルゴリズムを記述し、同相評価時のノイズと精度損失を解析する。したがって、定数加算は暗号文の絶対誤差をほとんど変化させない(端数部分はノイズに加算できる)。また、適切なスケーリングを選択した定数乗算処理は、入力暗号文の相対誤差をほとんど変化させない。メッセージm1,…,mdがηビットの精度で暗号化されているとすると、我々の階層型FPHE方式では、(d-1)同型乗算で(η-dlogde)ビットの精度で、(d-1)の同型乗算でその積を計算する。例えば、20ビットの精度で16個の暗号文が与えられた場合、15ビットの精度で約315msでその積を計算することができます。多項式の評価についても同様の結果が得られ、さらにテイラー分解を用いて指数関数やロジスティック関数などの解析関数にも拡張しています。

1/2≤x≦1の与えられた実数xに対して、 ̄x= 1-xとします。等式x(1 + ̄x)(1 + ̄x2)---(1 + ̄x2k-1) = (1- ̄x2k),x-1 は (1 + ̄x)(1 + ̄x2)---(1 + ̄x2k-1) で 2^kbits の精度で近似できます。この等式を変換して、乗算逆数を安全に計算します。さらに、精度ηビットの暗号文が与えられた場合、深さlogηのFPHEスキームは、暗号文の2blogη乗算において、(η-1)ビットの精度で乗算逆数を計算することができます。例えば、20ビットの精度を入力すると、深さ5のFPHE方式の8回の乗算で19ビットの精度でその乗算逆数の暗号化を計算することができ、セキュリティパラメータλ=80での実装には約168msかかります。

Related Works

関連する著作物.実数を暗号化して処理することについては、かなりの数の研究が行われてきました。実数を整数にスケーリングする方法は自明ですが、平文母数はメッセージの長さが指数関数的になります。例えば、Bosら[BLN14]は、スケーリングされた入力データを用いてロジスティック回帰関数を評価することで、心臓発作を起こす可能性を私的に予測する方法を記述しています。一方、Dowlinら[DGL+15]は、奇数整数B≧3の場合の基底B表現を用いて、[-(B-1)/2, (B-1)/2]の範囲の係数を持つ多項式として符号化し、固定小数点数を効率的に表現する方法を提示している。一方、除算は、医療、金融、広告、機械学習などの実社会での応用には不可欠な演算であるが、有効ビット数が多いと多項式環の次数が大きくなる。Algesheimerら[ACS02]は、2つの暗号化されたofaandbが与えられ、入力に関する情報を漏らさずにbabcの暗号化を決定するような安全な整数除算を解く問題を紹介しました。この問題は、安全なマルチパーティ計算プロトコルを用いたニュートン反復法に基づいています。このプロトコルは、Jakobsenによって、受動的に安全な3者設定[Jak06]で実装されました。 DNT12]では、2パーティ設定で問題を解くための安全な計算プロトコルを提案した。 これらのプロトコルの計算コストは扱いやすいものですが，多くの相互作用を必要とします．最近では，Cetinet al. [cDSM15]が，ワードベースの暗号化データを用いた比較と同型分割のための新しいアイデアを述べています． 彼らは近似技術を用いてアプローチを見つけましたが、近似の精度については正確な説明がありませんでした。

第2節では、浮動小数点演算法とLWE問題に関する表記法と前置きを簡単に紹介し、第3節では浮動小数点同型暗号化方式を紹介し、基本的な同型演算の間のノイズの増加を解析します。第3節では、浮動小数点同型暗号化方式を紹介し、基本的な同型演算時のノイズの増加を解析します。第4節では、典型的な回路を同相的に評価し、出力の精度を計算するためのアルゴリズムを提案する。最後に、第5節では、本方式の実装と性能について述べる。

2 Preliminaries

表記法.対数は特に断りのない限りすべて基数2である。ベクトルは太字、例えば a、行列は大文字の太字、例えば A と表記する。本論文ではすべてのベクトルは列ベクトルである。ここでは2つのベクトルの通常の点積を〈-,-〉とする。実数[r]は最も近い整数を示し、同数の場合は上向きに丸める。ここでは分布Dに従ったサンプリングを表すためにD←Dを使用します。本稿では、安全性パラメータをλとし、対象となる暗号方式に対する既知の有効な攻撃はすべてΩ(2λ)ビット演算を取るべきであるとする。

2.1 Floating-Point Arithmetic
浮動小数点は、範囲と精度のトレードオフをサポートするように実数を近似する数式表現です。
数値は一般的に、有効数字（シグニフィシェンド）の固定数に近似して表現されるので、実数はコンピュータの有限ワードの長さで近似することができます。termfloatingとは、数値の基底点が浮いていることを指します。
より正確には、浮動小数点数xは4つの整数
$x=\pm s\cdot b^{e-k}$
で表され、

• bは基数
• eは指数
• kは精度（符号の有効桁数）
• sは$0\leqq s\le b\le k-1$ を満たす符号である。

ここでは、$x^{\ast }$（浮動小数点系で最も近い数）の浮動小数点値を $x=fl(x^{\ast })$ と表記します。 精度の指標として最も有用なのは、

• 絶対誤差 $E_{abs}(x)=|x-x^{\ast }|$
• 相対誤差 $E_{rel}(x)=\frac{x-x^{\ast }}{x^{\ast }}$

精度を決定するために、unit-round off u=1/2-b^(1-k)を定義します。
これは、実数と最も近い浮動小数点数との間の、ユニティーに対する最後尾の距離です。
浮動小数点数を足し算（引き算）する簡単な方法は、まず通常の足し算（引き算）を行います。その後、同じビットの精度で四捨五入されるので、丸め誤差が生じます。
乗算は、指数を加算しながら符号を乗算し、その結果を四捨五入します。

Example

$x=1101_{(2)}\cdot 2^2,y=1001_{(2)}\cdot 2^{-3}$ と4ビットの精度で与えられた場合、

• まず真の積値 $x\cdot y=11010101_{(2)}\cdot 2^{-1}$ を求め
• 4ビットの精度で $fl(x-y)=1111_{(2)}\cdot 2^2$に丸めます

これらの誤差の処理
特に、計算結果がアルゴリズムの正確な値にどれだけ近いかというフォワードエラーに焦点を当てています。より明確な概要については、[Gol91,Hig02,Ein05]を参照することをお勧めします。 ここにWilkinson [Wil61]によって導入された浮動小数点演算の標準モデルがあります：もし x, y: float
$fl(x?y)=(x?y)(1+ϵ)$
相対誤差

LWE

• 正の整数 $n$
• $q\geqq 2,t\in {\mathbb{Z}}_q^n$
• 分布 $\chi$ over $\mathbb{Z}$ とする
• ただし ${\mathbb{Z}}_q:=\mathbb{Z}\cap (-\frac{q}{2},\frac{q}{2}]$

$A_{q,\chi }^{\mathrm{LWE}}(\mathbf{t})$ をサンプリンガ←Znqande←χで得られた分布と定義し、c=(〈a,t〉+e,a)∈Zq×Znqを返す。LWEn,q,χ(D)と呼ばれる誤差を伴う（決定）学習問題は、固定t←Dに対してALWEq,χ(t)に従って選択された任意の多数の独立サンプルをZq×Znq上の一様分布から区別する問題です。
5LWE問題は自己還元可能であり、任意の分布Dに対してLWEn,q,χ(D)を LWE_{n,q,\chi}(U(Znq))$ に還元することができます。さらに、χが適切なパラメータを持つガウス分布であれば、LWEn,q,χ(U(Znq))を効率的にLWEn,q,χ(χ)に還元することができます[ACPS09]。また、LWEとワーストケース格子問題との間に古典的な還元があることを示しました[Pei09]。これらの結果の詳細については、[Reg05,Pei09]を参照されたい。

3 Floating-Point Homomorphic Encryption

本節では、LWE問題の困難性に基づいて、暗号文の浮動小数点計算を可能にする新しいレベル同型暗号化方式について述べる。m1, m2の暗号化が与えられると、浮動小数点加算(または乗算)は、2つの整数m1,m2の暗号化を入力すると、m1+m2(m1m2)のいくつかのMSBの暗号化を出力します。これは、整数の積の近似値、乗算の逆数、および冪級数の計算に適用することができる。本節ではBGVスキーム[BGV12]をベースにしていますが、この考え方は[GHS12b]のような他の(Ring)LWEベースのHEスキームにも適用可能です。

3.1 Basic Encryption Scheme

本節では、まず基本的な公開鍵同型暗号化方式について述べる。 この方式は、(n,q,$\chi$)-LWE問題が困難であるという前提の下で、IND-CPAで安全である.

memo(IND-CPA)

• IND-CPA: 選択平文攻撃に対する識別不能性安全性

1. E.Setup(1^λ)
   モジュラス $q=q(\lambda )$ とする.
   パラメータ $n=n(\lambda ,q)$ と $B_{err}$-Bounded分布 $\chi =\chi (\lambda ,q)$ を ${\mathrm{LWE}}_{\mathrm{n},\mathrm{q},\chi }$ に対して適切に選択.
   少なくとも $2^{\lambda }$ security.
   $\tau =2(n+1)\lceil \log q\rceil$とする.
   $(n,q,\chi ,\tau )$ を得る.

2. E.SecretKeyGen($\mathrm{params}$)
   ベクトル $\mathbf{t}\leftarrow {\chi }^n$, をサンプリングし, 秘密鍵 $sk=s\leftarrow (1,-t)\in Zq\times Znq$

3. E.PublicKeyGen($\mathrm{params},\mathrm{sk}$)
   $pk:(n+1,\tau )$ = $\mathbf{A}\leftarrow A_{q,\chi }^{\mathrm{LWE}}(\mathbf{t})$
   (n+1)×τmatrixpk=A←ALWEq,χ(t)τ(Aの各列は分布ALWEq,χ(t)から独立してサンプリングされる)

4. E.Enc_{pk}(m)
   を生成して出力する。メッセージM∈Zが与えられたとき、ベクトルr←{0,1}τand letm←(m,0,…,0).Outputc←m+A-rmodq

5. E.Dec_sk(c)
   Outputm′←〈c,s〉modq.

既存の多くの方式（[Bra12,GHS12b,BLLN13]など）を除けば、我々の方式では、挿入されたエラーと平文空間が固定されていない、あるいは分離されていない。この浮動小数点暗号化方式は、復号回路の出力m′= m + e が元のメッセージmと若干異なるため、不思議に思われるかもしれません。しかし，これらは十分に小さい場合には，全く同じ浮動小数点演算と考えることができます．より正確には、入力されたメッセージが真の値に対してηビットの精度を持っていれば、m′も(η-1)ビットの精度を持った近似値であると考えられます.

Examples

例えば、$x=1001_{(2)}\cdot 2^{-3}$ を4ビットの精度で暗号化

• 基数点を移動させて(定数 $2^5$ を乗じて)、スケーリングされた値$m=100100_{(2)}$ を暗号化処理の入力メッセージとして使用します.
• 暗号化誤差が $|e|\le 2^2$ であるとすると、$m^{\prime }=m+e$ は9ビットの精度で$x\cdot 2^5$ の近似値である.
  入力データのスケーリング係数は、計算結果を正しく理解するために独立して保存・管理する必要があります.

この近似暗号化の概念は過去の研究でも部分的に用いられており、例えば[BV11a,Bra12,BGV12,CS15]では乗算のための付加情報を、[DGHV10,CLT14]ではスクラッシュ復号回路の中間値を同様に暗号化しています。なお、これらの暗号文は誤差の少ない近似計算で使用されていますが、同型演算の場合、回路の複雑さや入力メッセージの大きさに応じてパラメータを大きくする必要があります。基本的な暗号化方式の安全性は、次節で述べるレベル付き浮動小数点HE方式の安全性証明から直接得ることができる。

3.2 Leveled Floating-Point Homomorphic Encryption Scheme

まず、[BGV12]の表記法を我々のコンテキストに合わせ、[BV11a,BGV12]のLWEベースの暗号化方式の同相演算のための鍵切り替えとモジュラス削減技術を思い出してみましょう.
ベクトル $x\in {\mathbb{Z}}_q^n$ が与えられると
そのビット分解と2の累乗は

• $BD(x)=(u_0,\dots ,u_{\lfloor \log q\rfloor })\in {\{0,1\}}^{n(1+\lfloor \log q\rfloor )}$ と
• $x={\sum }_{i=0}^{\lfloor \log q\rfloor }{2}^i{u}_i$ とし、$P_2(x)=(x,...,2^{\lfloor \log q\rfloor })$

で定義される。とすると, $〈BD(x),P2(y)〉=〈x,y〉$ となります。我々はまた、ベクトル空間 ${\mathbb{R}}^n\times {\mathbb{R}}^m$ 上のテンソル積 $u\otimes v=(u_1{v}_1,u_1{v}_2,...,u_1{v}_m,...,u_n{v}_1,...,u_n{v}_m)$ の定義と、内積との関係を想起する

$〈u\otimes v,u^{\prime }\otimes v^{\prime }〉=〈u,u^{\prime }〉-〈v,v^{\prime }〉$

これらの暗号文は，いくつかのスマルイに対して，
$〈c_i,s〉=m_i+e_i\mathrm{mod}\mathrm{q}$
を満たす二次方程式 $Q_{c_1,c_2}(x):=〈c_1,x〉-〈c_2,x〉=〈c_1\otimes c_2,x\otimes x〉$ を考える。

もし $m_i^{{}^{\prime }}=m_i+e_i$ が十分に小さいならば、我々は
$Q_{c1,c2}(s)modq=m_1^{\prime }{m}_2^{\prime }=m_1{m}_2+e$
を得、望まれるように、そしてc←c1⊗c2は秘密⊗sを持つm1m2の暗号化である。
しかし、これは暗号文の次元とhomomomorphic乗算の複雑さを増大させる代償を伴う。
BrakerskiとVaikuntanathan [BV11a]は、長い秘密鍵⊗sの下でLWE暗号文を別の秘密鍵の下で同じ平文の別のLWE暗号文に変換するために、鍵切り替えのテクニックを使用する。
大雑把に言えば、このプロセスは、新しい秘密鍵で暗号化された補助情報 $s\otimes s=(s_i^{{}^{\prime }}{)}_i$を公開し、暗号文 $c=(c_i{)}_i$ を新しい暗号文$c^{\prime }\leftarrow {\sum }_i{c}_i\cdot {\mathrm{Enc}}_{\tilde{\mathrm{s}}}({\mathrm{s}}_{\mathrm{i}}^{\prime })$ に変換する。
したがって、同じ暗号文サイズを維持したまま、最大L 定数倍数レベルまでの評価を行うためには、秘密鍵の連鎖が必要となる。
本論文では、便宜上、円環セキュリティを仮定しており、階層化されたHEの秘密鍵を自身の公開鍵で暗号化しても安全である。
Brakerski, Gentry and Vaikuntanathan [BV11a,BGV12]は、LWEベースのHE方式における誤りの大きさを管理するために、モジュラススイッチング技術を開発した。これは、誤りのある暗号文cmモジュラスqを、同じメッセージの暗号文c′に変換し、新しいモジュラスq′と誤り≈q′qeに変換するものである。ノイズと変調度の比/qはほぼ同じ値を維持するが、ノイズの大きさと次の演算でのエラーの増加を最も小さくする。その結果、最大のモジュラスのビットサイズは乗算深さに応じて指数関数的にではなく線形に成長する。我々は、浮動小数点HEにモジュラス切り替え技術を適用していますが、全く異なる目的のために適用しています。大まかに言えば、q′/qの係数でスケーリングし、適切に丸めて整数の暗号文を得ることで、メッセージのLSB(誤り部分)を捨て、符号の大きさを制御します。

tl; dr

• LWE問題を背景としている
• 加算でも乗算でも誤差が一定値以下なので復元可能
• モジュラススイッチングを利用
  • スイッチできる回数は上限があり、レベル と呼ばれる. 生成時に決定.

$LW{E}_{s,\ell }(m,B)$

• レベル $\ell$
• 誤差が $B$ で制限される
• $m$ under $\mathbf{s}$ レベル暗号の集合

例: ある $|e|\leqq B$ の場合、ベクトル $c\in {\mathbb{Z}}_q\times {\mathbb{Z}}_{nq}$ が $LW{E}_{s,\ell }(m,B)$ に含まれる. ($<c,s>\equiv m+e(mod{q}_{\ell })$)

FP.ModEmbed : $c(modq‘)7\to c(modq)from$LWE_{\ell}(m,B)$ toLWE(m,B) for any > があります。 変換された暗号文c←FP.ModEmbedq→q′(c)は、メッセージとエラーASCが全く同じなので、この手順ではメッセージの規模は変わりません。このエンベッディングは、異なるレベルの暗号文間の操作を行うために使用することができます。

前述したように、我々のモジュラススイッチング技術は、Brakerski, Gentry and Vaikuntanathan [BV11a,BGV12]のものと類似している。 しかし、我々の論文では、FP.ModSwitchという手順により、メッセージを別の小さいメッセージに変更しています。メッセージが台無しになるわけではなく、メッセージの表現（スケール）を変えていくだけです。より正確には、浮動小数点系の数値をbasepで表現すると、モジュラス切り替え処理は、メッセージの最小(-′)桁を切り上げて、指数部分を(-′)増やしながら、その指数を左に移動させます。その結果、メッセージのほとんどの符号桁は、このモジュラス切り替え手順では不変ですが、符号の大きさだけが減少します。

tl; dr

• 既存(2011, Gentryら) のモジュラススイッチングと類似しているがこの論文では $m$ のビット数を小さくしている
• 下部 $\ell -{\ell }^{{}^{\prime }}$ ビットを切り上げ

補助情報を含む暗号文形式

本方式の実用的な利用のためには、基底点の位置を記憶し、同型評価時のメッセージとエラーの境界を計算するために、(c,,M,B,exp)形式の完全な暗号文に補助情報を保持しておくことが推奨される。ここで、,M,Bandexpはそれぞれ暗号文cのレベル、メッセージとエラーの境界、メッセージの指数部を表す。そうすると、我々のスキームは以下のように記述することができます。

異なるレベルの暗号文の同相演算

• 暗号文 $c$ in $LW{E}_{\ell }(m,B)$ をレベル ${\ell }^{{}^{\prime }}$ の暗号文と乗算するには，まずレベル $\ell {}^{\prime }$ の暗号文に変換しなければならない.

• FP.ModSwitch${}_{\ell \to {\ell }^{{}^{\prime }}}$ は $m$ を変更

  • より小さな $m$ を格納できる

• FP.ModEmbed${}_{\ell \to {\ell }^{{}^{\prime }}}$ は変更しない.

  • 追加のノイズが発生しないので正確な計算ができる

-> 2つの暗号文の演算はどちらか小さい方のレベルへの ModEmbed を行ったあと演算

4. omomorphic Evaluation of Floating-Point Arithmetics

我々のFPHEにおけるノイズの増加は、暗号化されていない浮動小数点演算とほぼ同じであることを示した。代表的な浮動小数点回路をホモモルフィクショナルに評価することから始め、定数による乗算、単項式、多項式の乗算を行います。 また、一般的な多項式、逆数、指数、分析関数にも拡張しています。評価時に発生するノイズの増加に対する境界を推論し、結果の精度を解析する。

まず、実数a∈Rに対する関数sf(x) =x+a, f(x) =axを評価する簡単な演算を紹介します。

前述のリーマにおいて、与えられた暗号文cの相対誤差をα=B/Mbeとすると、α=B/Mbeとなる。ベクトルc′←bpu-aechasはメッセージboundM′=pu-|a|Mであり、相対誤差α′=B′M′=α+B+M2pu-|a|M≤α+1pu-|a|である。相対誤差が大きくならないように十分な整数化を選択してもよい。特に、いくつかの整数suandˆaに対してformp-u-ˆaのスカラ（Ris）がある場合には、一定の乗算を行っても相対誤差は変わらない。

$x^d$ ($d=2^k$) の計算

$x^d$ (制限なし) の計算

• 2の累乗に分解して計算するだけ

多項式 ${\sum }_{i=0}^d{a}_i{x}^i$ の計算