2020-09-12

Two-Sided Malicious Security for Private Intersection-Sum with Cardinality(CRYPTO2020)を読んだ

Oblivious Pseudo Randomness Function Private Set Intersection

どういう論文か
- Private Intersection-Sum with Cardinality(以下PI-SCA)
- 関連技術
新規性
手法
まとめ
参考文献

どういう論文か

Private Intersection-Sum with Cardinalityに関する研究である。

f:id:ATen:20200912003537p:plain — プロトコル同士の関連性

Private Intersection-Sum with Cardinality(以下PI-SCA)

共通集合の濃度と同時に、共通集合に属する要素に関連づけられた値の和を算出するPSIのバリアントである。例えば、集合 $A={a,b,c}$ と集合 $B={b,c,d}$ であれば $A\cup B={b,c}$ である。ここで $a$ が $1$ に関連づけられていることを $a:1$ と書くことにすると、

$a:4\\ b:2\\ c:3\\ d:1$

のように対応していればそのIntersection-Sumは $2+3=5$ である。このIntersection-Sumはpaillier暗号のような加法準同型性を持つ暗号で実現できる。

新規性

以前はPI-SCAのMalicious Securityなモデルでは、受信者と送信者のうちで片方向、例えば受信者のみが出力を得るような方法しか存在しなかった。
この研究でTwo-Sided Malicious Security、つまり両方向出力をしつつもをMalicious Securityを保証するプロトコルを提案する。これにより両方が出力得たいようなシナリオに対応することができる。
PI-SCAで初めてMalicious Securityと同時に線形の通信量と計算量を達成している。

手法

まずこのPI-SCAプロトコルが何をやろうとしているのかの概要図を紹介する。（なお、コミットメントや証明などはまだよくわかっていないため省略）

f:id:ATen:20200912004444p:plain — プロトコル概要

まず、両方向出力にするためには、まず受信者が得た出力が正確なものであることを証明しなければならない。そのため、プロトコルを役割を入れ替えて並行実行する手法をとる。（1,2の並行実行）

手法の中心となるのはDOPRF(Distrubuted Oblivious Psuedo-Randomness Function)である。これは共有鍵を用いてOPRFをすることを可能にするプロトコルであり、並行実行されたOPRFの出力を並び替えることができる(shuffled)。

Semi-honest SecurityなPI-SCAの構成方法

DOPRFを利用してPSIを構成する。
shuffled DOPRFプロトコルを構成し、PSI-CAに拡張する。
関連づけられた値をre-randomizable(つまり確率暗号)な加法準同型暗号を使ってPI-SCAを構成する。

ここでPSI-CAにDOPRFでなくてshuffled DOPRFを使うのは、ミックスネットのように暗号文と平文の対応をわからなくすることが目的である。対応関係がわからなくなれば平文そのものの情報が漏れることがなくその濃度だけを得られる。

Note 関連づけられた値をre-radomizeする必要があるのはビットパターンを平文を変えることなく変更する目的がある。

Malicious SecurityなDOPRFの構成

まずはDOPRFをSemi-honest Securityで実現する。

Semi-honest SecurityなPRFをq-DH仮定のもとで成立させる。
PRFの鍵を共有鍵にすることで、DOPRFプロトコルを構成することが可能である

先行研究で利用されていたDH仮定ベースのDOPRFでは困難であるとされるため、q-DH仮定で定義しなおしている。次にMalicious SecurityなDOPRF実現する。そのために

暗号化（準同型）のCorrectness
Consistency（二つの値の内部で使われている値 $a$ が一致していること）

をCamenish-Shoup暗号を使いΣプロトコルによってゼロ知識証明する。これによりMalicious Securityを達成する。

Malicious SecurityなPI-SCAの構成

これらのプロトコルは全て出力を双方向に得ることを目標としていることに注意されたい。

Malicious SecurityなDOPRF→PSI

Malicious SecurityなPSIを構成する。

問題　PSIプロトコルで使用するDOPRFで出力を得た受信者が出力を送り返すとともに暗号文とPRF値のCorectnessを証明する必要がある。

手法　この証明はΣプロトコルによって実現できる。

DOPRF→shuffled DOPRF

Malicious Securityな PSI-CAを構成するためにDOPRFをshuffled DOPRFへ拡張する。

問題　shuffled DOPRFは送り返す前に出力をシャッフルできるが、このシャッフルのCorrectnessを証明する必要がある。

手法　平文と暗号文の集合が与えられた時、平文がある暗号文を並び替えたものの復号に対応することが効率的にゼロ知識証明できるプロトコルを使う。[BG12]

PSI→PSI-CA

Malicious Securityな PSI-CAを構成する。

問題　Malicious Securityにするには二つのPSI-CAを役割を逆にして並行に実行しなければならない。この時、各プロトコルの共有鍵の一貫性（ Consistency）を証明する必要がある。

手法　各パーティは最初に共有鍵をコミットしてから一貫性の証明を行う。この証明にはΣプロトコルを利用する。

PSI-CA→PI-SCA

Malicious Securityな PI-SCAを構成する。

問題　PRFとそれに関連づけられた値 $v$ に対してシャッフルを行うとき、 $v$ をre-randomizeしつつシャッフルするが、その $v$ がPRFに対するシャッフルと対応しているか証明する必要がある。また得られた暗号文を共有鍵を用いてhalf-decryptできるが、この復号のCorrectnessを証明する必要がある。

手法　前者の証明は[BG12]で実現できる。後者はΣプロトコルを使う必要がある。

指数領域への拡張　

ここまでの議論では多項式サイズの入力でしかプロトコル成立しなかったが、緩めた選択的安全性を定義しPI-SCAが多項式サイズのみならず指数サイズの入力でも安全であることが示せる。

バッチ処理

今回のプロトコルは効率化のためにバッチ処理を提案する。今回のプロトコルでは重要な構成要素である以下の３つをバッチ処理している。

Pedersen コミットメント
CS暗号
Σプロトコル

これらのテクニックにより通信量を低減することができている。独立した関心事なのではないかと思われる。

まとめ

双方向通信やhalf-decryptで双方向で出力を得る仕組みがとても面白いと思った。コミットメントや安全性証明の理解度が浅いため、読みながら理解を深めたい。

参考文献

Two-Sided Malicious Security for Private Intersection-Sum with Cardinality

Efficient Zero-Knowledge Argument for Correctness of a Shuffle Stephanie(BG12)

2020-07-22

PSIとPSUについて調べた

Private Set Intersection マルチパーティ計算

PSIとPSU、そしてactiveな敵に対して安全なプロトコルについて簡単に調べたのでメモを残しておきます。以下の論文はgoogle scholarで出ます。

Extending Oblivious Transfers Efficiently(2003)

Y Ishai, J Kilian, K Nissim ,E Petrankの研究。

概要この研究では1回のOTが安全なら複数回のOTが安全であることを証明しています。

より形式的には $k ^ c$ OTを $k$ OTに帰着します。 $k$ が安全なら、それをブラックボックス的に用いた $k ^ c$ も安全であるという事実を示しています。

まず、一方向性関数が存在すれば、疑似ランダム関数が存在するということが知られています。しかし、一方向性関数からOTへの帰着は困難です。しかし、Beaverの定理によれば一方向性関数と小さなOTが存在すれば、大きなOTが存在すること（拡張の存在）が分かりました。

この研究でやられたことは主に

一方向性関数から疑似ランダム関数を構成し、ランダムオラクルモデルにおけるOTを効率的に拡張するプロトコルを提案。
Correlational robustnessという性質を定義した。疑似ランダム性のような性質で、疑似ランダム関数族を得るのに使える。

です。

Efficient Private Matching and Set Intersection(2004)

M J. Freedman,K Nissim, B PinkasnによるPSIの概念や他の応用方法(PSI-CAやマルチパーティ型PSI)が提案された研究です。

Private Set IntersectionまたはPrivate Set Unionとはサーバーとクライアントの持つ各々の集合について共通集合または和集合を計算し、その結果をクライアントが得る。サーバーは何も得られないというプロトコルです。データベース上の計算において集合演算は幅広く活用されています。もともとはTTPを用いた方法や安全性のない平文でのやりとりが行われていましたが、PSIはそれを解決しています。

この論文でPSIは

Oblivious Polynomial Evaluation (OPE,1999)
paillier暗号などの加法準同型性を持つ暗号

を用いて与えられました。

Privacy Preserving Set Operations(2005)

L Kissner , D Song の研究。

和集合、共通集合、element reduction(要調査)に対するマルチパーティ計算プロトコルを提案しました。PPT-bounded adversaryモデルにおいても、passiveとactiveに対する安全性が保証されます。ここで提案されたプロトコルは、のちにMPSIやMPSUと呼ばれています。

Keyword Search and Oblivious Pseudorandom Functions(2005)

M J. Freedman, Y Ishai, B Pinkas, O Reingoldの研究。OPRFとはOPEの鍵付き疑似ランダム関数版のことです。

送信者は鍵 $k$ を入力し、受信者は $x$ を入力する。
受信者は $f _ k(x)$ を得られる。送信者の鍵 $k$ の情報も受信者の入力 $x$ の値も漏れない。

OTやOPE同様にPSIに利用されます。

Honest-Verifier Private Disjointness Testing without Random Oracles (2006)

Susan Hohenberger Stephen A. Weisの研究。

PSI-CAを初めて正式に定義しました。 PSI－CAとは共通集合や部分集合の要素集合ではなく、その大きさ（つまり濃度）しか学習しないプロトコルです。つまり、サーバーが集合 $S$ 、クライアントが集合 $C$ を入力したとき、 $|S \cap C|$ を出力します。実装は困難であり、PSIやPSUでは情報量が多すぎるような場合に利用するPSIのより発展的な研究です。計算量が[tex:O(n²)]です。

Efficient Oblivious Pseudorandom Function with Applications to Adaptive OT and Secure Computation of Set Intersection(2009)

Stanisław Jarecki and Xiaomin Liuの研究です。プロトコルにOPRFを用いて、通信ラウンド数が一定かつコミット型という特徴を持ちます。

Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model(2010）

E D Cristofaro, J Kim, G Tsudikの研究。ここで初めてAPSI(Authorized Private Set Intersection)が定義されました。DDH仮定のもと、ランダムオラクルモデルで安全性が証明されます。CRSモデルを使わず、計算複雑性と通信複雑度が線形である初めての研究です。

ディジタル署名での認証とPSIの合わせ技で、PPIT(Privacy Policy based Information Transfer)と関連している。PPITとはクライアントが取得権限を持っている情報しか得られないプロトコルです。APSIは、共通集合のうちユーザーが権限を持っている情報しか得られません。

Semi-homomorphic Encryption and Multiparty Computation(2011)

R Bendlin, I Damg˚ard, C Orlandi,S Zakariasの研究です。BDOZとも呼ばれています。加法準同型性を活用して、効率的にactiveな敵に対して安全なマルチパーティ計算プロトコルを提案しました。このプロトコルのプリプロセスの考え方はSPDZに活用されています。

Fast and Private Computation of Cardinality of Set Intersection and Union(2012)

E D Cristofaro,P Gasti,G Tsudikの研究。初めて線形時間で動作するPSI-CAとPSU-CAのプロトコルを実現しました。

Phasing: Private set intersection using permutation-based hashing(2015)

M Zohner,G Segev,T Schneider,B Pinkasの研究。 Permutation based-hashingを活用し、この2015年時点で最速のPSIを実現しました。

MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer (2016)

M Keller, E Orsiniの研究。activeな敵に対して安全かつ高速なマルチパーティ計算プロトコルです。オンラインフェーズはSPDZのものと全く同じですが、プリプロセスにおけるトリプルの生成が高速化されています。

この研究より前にFredriskenは、SPDZのプリプロセスにおけるトリプルの生成を二元体上で高速化しました。MASCOTでは任意の大きな有限体において、OTを使用したプリプロセスの実行を可能にしました。トリプルの生成には２つのk-bitの積を計算するgilboaの提案したプロトコルを利用します。

まとめ

認識に間違いがありましたら、コメント等で教えてください！何卒よろしくお願いします！

参考

Privacy Preserving Set Operations

Fast and Private Computation of Cardinality of Set Intersection and Union

Extending Oblivious Transfers Efficiently

Efficient Private Matching and Set Intersection

Faster Private Set Intersection Based on OT Extension

Practical Private Set Intersection Protocols with Linear Complexity

Honest-Verifier Private Disjointness Testing without Random Oracles

Phasing: Private Set Intersection using Permutation-based Hashing

MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer

Keyword Search and Oblivious Pseudorandom Functions

Efficient Oblivious Pseudorandom Function with Applications to Adaptive OT and Secure Computation of Set Intersection

Semi-homomorphic Encryption and Multiparty Computation

2020-07-12

なんとなく分かってもらうためのSPDZ解説（プリプロセスフェーズ編）

SPDZ マルチパーティ計算モデル FHE 秘密分散

SPDZはsomewhat準同型暗号(以下SHE)を使うことで高い効率性と安全性を実現したマルチパーティ計算プロトコルです。

SHEによる効率的なプリプロセスフェーズの実現。
semi-honest secureよりも高い、active secureの効率的な実装。
active secureなので、n個のパーティのうちn-1がcorruptされていてもUC安全性が保障される。

のような性質を持っています。これについて解説します。

はじめに
- 加算と乗算
- MACでの認証
サブプロトコル
プリプロセス（オフライン）フェーズ
まとめ
参考文献

はじめに

ここから登場する記号は太字の場合はすべて $\mathbf{v} \in (\mathbb{F _ {p ^ k}}) ^ s$ である有限体上の $s$ 次元ベクトル $\mathbf{v}$ です。そうでなければ $v \in \mathbb{F _ {p ^ k}}$ である有限体の要素 $v$ です。

SHEとは加算と乗算に対して準同型性を持つが、計算回数が制限されたものです。SHEのなかでもBVというスキームを活用します。BVでは暗号文のまま十分な数と加算と1回の乗算を行うことが出来ます。暗号文での乗算が1回を超すと、正しく復号できなくなることに注意してください。

SPDZではSHEの準同型性を生かし、平文を暗号化し、暗号文の状態でブロードキャストや計算を行います。この時、

暗号文なので平文の情報は漏れない。
SHEの準同型性によって暗号文のまま計算ができる。

となります。こうして、プリプロセスフェーズで必要な情報を各パーティが使用可能な状態にしておくことで、オンラインフェーズでの計算量を減少させます。

加算と乗算

オンラインフェーズでも述べますが、加算と乗算の方法について説明します。秘密分散方式として、加法的秘密分散を使っています。 $m$ を $m=m _ 1+\dots+m _ n$ を満たすような $m _ i$ に分割します。このことを $m=\Sigma _ i m _ i$ と書き、各 $m _ i$ のことをシェアということにします。

例えば $m=10$ として、 $(m _ 1,m _ 2,m_ 3,m _ 4)=(1,5,2,3)$ とすると、

$m=\Sigma _ i m _ i=1+5+2+3=10$

　が明らかです。更にそのまま加算を行うこともできます。 $P _ 1$ が $m$ に $5$ を足したい場合は、 $m _ 1$ に $5$ を足します。実際、

$m=\Sigma _ i m _ i=(1+5)+5+2+3=15$

　なので加算できています。

乗算の場合はMultiplication Triplesを使います。Multiplication Triplesについては以下のサイトが参考になります。

acompany.tech

ここではMultiplication Triplesのことをトリプルと呼ぶことにします。

MACでの認証

さて、SPDZには二つの値表現が登場します。SPDZではシェアをパーティの持つ秘密鍵やグローバル鍵で認証してあげることで、不正を検出します。この認証に使う認証子をMAC（Message Authentication Code）と呼ぶことにします。

$\langle \mathbf{m} \rangle$ はMACで認証されたシェアです。この値は単一の値を表現しているわけではなく、以下のような状態を表します。

f:id:ATen:20200712130212p:plain — <m>の表す状態

$Private$ は各パーティ $P _ i$ が個人で所持している値です。 $Public$ はすべてのパーティが参照できる値です。

$\delta$ はMACの条件を維持するために利用します。詳しい役割についてはオンラインフェーズで述べます。
$\ \mathbf{m _ 1} ,\mathbf{m _ 2},\dots,\mathbf{m _ n}$ は計算は各パーティ $P _ i$ の所持するシェアです。
$\gamma ( \mathbf{m} ) _ i$ はその計算における不正を検証するためのMACです。

なお、このMACは $\alpha$ がないとチェックできないので計算が全て終わってからでないと誰かが不正したことを検出できません。

$[ \mathbf{m} ]$ は秘密鍵 $\beta _ i$ で認証された値です。この値も単一の値を表現しているわけではなく、以下のような状態を表します。論文や図では〚〛を使用していますが、texで出す方法が分からないので以降は[]で代用しています。

f:id:ATen:20200712130704p:plain — [m]の状態

$\ \mathbf{m _ 1} ,\mathbf{m _ 2},\dots,\mathbf{m _ n}$ は計算は各パーティ $P _ i$ の所持するシェアです。
$(\gamma ( \mathbf{m} ) ^ i _ 1,\dots,\gamma ( \mathbf{m} ) ^ i _ n) _ {i=1,\dots,n}$ はその計算における不正を検証するためのMACです。

この状態では、ブロードキャストしあってシェアを集めることで $\beta _ i$ に認証された $\alpha$ を復元できます。例えば、下の図の赤く囲われた部分をブロードキャストしあって集めることで $\beta _ 1$ に認証された $\alpha$ を復元できます

f:id:ATen:20200712130208p:plain — [m]の表す状態２

$\beta _ 1$ を持っている $P _ 1$ なら値の正しさを検証できます。 $P _ 1$ 以外の $P_ i$ についても同様です。

$\langle \mathbf{m} \rangle$ との違いは $\alpha$ なしに $\mathbf{m}$ を手にいられることです。そのため、オンラインフェーズで $\alpha$ を公開するより前に値が必要な時に利用されています。

この表現はMACの認証に使用するグローバル鍵 $\alpha$ の公開を遅らせるために存在しています。各パーティ $P _ i$ が $\alpha$ がなければMACを確認することができないませんが、 $\alpha$ があると偽造できてしまいます。偽装を防ぐために各パーティの秘密鍵 $\beta _ i$ で認証させて、 $\alpha$ の公開を遅らせます。

サブプロトコル

プリプロセスフェーズでは同じような処理を繰り返し行う部分があるため、それを一般化したものを定義します。 $PBracket(\mathbf{m} _ 1,\dots,\mathbf{m} _ n,e _ \mathbf{m})$ のようになっていますが、 $\mathbf{m} _ 1,\dots,\mathbf{m} _ n$ は各パーティ $P _ i$ のローカルに保持する値であることに注意してください。

平文のゼロ知識証明

任意の平文に対する正しい暗号文を共有するために以下の処理を行います。これを $PoPK(\mathbf{m _ i})$ としましょう。

各パーティ $P _ i$ はメッセージ空間から $\mathbf{m _ i}\in (\mathbb{F _ {p ^ k}}) ^ s$ を選ぶ。各パーティの生成した平文の和は $\mathbf{m}=\Sigma _ i \mathbf{m _ i}$ となる。
各パーティ $P _ i$ が $e _ {\mathbf{m _ i}} \leftarrow Enc _ {pk}(\mathbf{m _ i})$ のように暗号化してブロードキャストする。
各パーティ $P _ i$ は暗号文 $e _ {\mathbf{m _ i}}$ に対応する平文 $\mathbf{m _ i}$ を知っていることを証明する。
各パーティ $P _ i$ は $e _ {\mathbf{m }}\leftarrow e _ {\mathbf{m _ 1}}\boxplus \dots \boxplus e _ {\mathbf{m _ n}}$ を計算する。

暗号文 $e _ {\mathbf{m _ i}}$ に対応する平文 $\mathbf{m _ i}$ を知っていることを証明する。

この処理により $e _ {\mathbf{m _ i}}$ を正しく共有し、 $e _ {\mathbf{m }}$ を入手できます。

PAngle

$PAngle$ は任意の平文に対するシェアを生成するために以下の処理を行います。これを $PAngle(\mathbf{m} _ 1,\dots,\mathbf{m} _ n,e _ \mathbf{m})$ としましょう。

$PAngle(\mathbf{m} _ 1,\dots,\mathbf{m} _ n,e _ \mathbf{m})=\langle \mathbf{m} \rangle$

暗号文 $e _ {\mathbf{m}}$ と、平文 $\mathbf{m}$ のシェアを入力に $\langle \mathbf{m} \rangle$ を生成する。各パーティ $P _i$ はグローバル鍵 $\alpha$ の暗号文 $e _ {\alpha}$ と $e _ {\mathbf{m}}$ の積を計算し、 $e _ {\mathbf{m} \cdot \alpha}$ を計算します。 $e _ {\mathbf{m} \cdot \alpha}$ は $\alpha$ で認証したMACの暗号文であり、これをReshareすればMACを共有できます。暗号文での乗算回数は1回です。

PBracket

$PBracket$ は任意の平文に対するシェアを生成するために以下の処理を行います。これを $PAngle(\mathbf{m} _ 1,\dots,\mathbf{m} _ n,e _ \mathbf{m})$ としましょう。

$PBracket(\mathbf{m} _ 1,\dots,\mathbf{m} _ n,e _ \mathbf{m})=[ \mathbf{m} ]$

　暗号文 $e _ {\mathbf{m}}$ と、平文 $\mathbf{m}$ のシェアを入力に $[\mathbf{m} ]$ を生成します。各パーティ $P _i$ は秘密鍵 $\beta _ i$ の暗号文 $e _ {\beta _ i}$ と $e _ {\mathbf{m}}$ の積を計算し、 $e _ {\gamma _ i}$ を計算します。 $e _ {\gamma _ i}$ は $\beta _ i$ で認証したMACの暗号文であり、これをReshareすればMACを共有できます。暗号文での乗算回数は1回です。

Reshare

$Reshare$ は暗号文からシェアを生成するプロトコルです。

$Reshare(e _ \mathbf{m},enc)=\langle \mathbf{m} \rangle\ and\ e' _ \mathbf{m}$

　暗号文 $e _ {\mathbf{m}}$ に対応する平文 $\mathbf{m}$ のシェアを秘密分散します。第二引数に $NewCiphertext$ のコマンドを入力されると、平文 $\mathbf{m}$ を暗号化しているが暗号文 $e _ {\mathbf{m}}=e' _ {\mathbf{m}}$ のような暗号文 $e' _ {\mathbf{m}}$ も同時に生成します。暗号状態での乗算回数は0回です。

$Reshare$ は乗算を1回も行わないので、 $PAngle$ や $PBracket$ と組み合わせても乗算回数が1回を超えることがありません。

プリプロセス（オフライン）フェーズ

サブプロトコルを活用して平文の情報を一切明かすことなく、プロトコルの初期化やトリプルとペアの共有を行うことができます

具体的にはオンラインフェーズで利用する

$\langle \mathbf{a} \rangle,\langle \mathbf{b} \rangle,\langle \mathbf{c} \rangle,\langle \mathbf{r} \rangle,\langle \mathbf{f} \rangle,\langle \mathbf{g} \rangle,\langle \mathbf{h} \rangle$

$[\mathbf{r}],[Diag(\alpha)],[\mathbf{t}],[\mathbf{e}]$

を生成します。 $Diag(\alpha)$ とは $\alpha$ を $s$ 個を並べた $(\alpha,\dots,\alpha)$ を表します。 $\alpha$ は $s$ 次元ベクトルでないので、 $s$ 次元に拡張しています。

プリプロセスは初期化、ペアの生成、トリプルの生成の3段階に分けることが出来ます。

初期化

まずトリプルやペアの生成のために、鍵を共有します。具体的には各パーティ $P _ i$ が $[Diag(\alpha)$ ]と $\beta _ i$ を持っている状態にします。

暗号化のためにプロトコルは公開鍵 $pk$ をセットする。
各パーティ $P _ i$ はメッセージ空間から $\beta _ i\in \mathbb{F _ {p ^ k}}$ を選ぶ。
$\mathbf{m _ i}:=Diag(\alpha _ i)$ とし、 $PoPK(Diag(\alpha _ i))$ を行う。各パーティ $P _ i$ は $e _ {\alpha _ i}$ と $\alpha _ i$ を所持した状態になる。（ここでだけ $e$ の添え字は $Diag(\alpha _ i)$ とならない）
$e _ {\alpha _ i}$ と $Diag(\alpha _ i)$ を使い、 $PBracket(Diag(\alpha _ 1),\dots,Diag(\alpha _ n),e _ \alpha)$ を行う。プロトコルは $[ Diag(\alpha) ]$ を手に入れる。

トリプル

Multiplication Tripleを共有することを考えます。オンラインフェーズで一回の乗算ごとに2セットのトリプル

$\langle \mathbf{a} \rangle,\langle \mathbf{b} \rangle,\langle \mathbf{c} \rangle\\ \langle \mathbf{f} \rangle,\langle \mathbf{g} \rangle,\langle \mathbf{h} \rangle$

を消費します。消費するだけ生成しておく必要があります。 $\langle \mathbf{f} \rangle,\langle \mathbf{g} \rangle,\langle \mathbf{h} \rangle$ の必要性についてはオンラインフェーズで述べます。

トリプル $\langle \mathbf{a} \rangle,\langle \mathbf{b} \rangle,\langle \mathbf{c } \rangle$ は $\mathbf{c}=\mathbf{ab}$ を満たし、 $\langle \mathbf{f} \rangle,\langle \mathbf{g} \rangle,\langle \mathbf{h} \rangle$ も同様に $\mathbf{h}=\mathbf{fg}$ を満たします。

$\mathbf{m _ i}:=\mathbf{a _ i}$ とし、 $PoPK(\mathbf{a _ i})$ を行う。各パーティ $P _ i$ は $e _ {\mathbf{a _ i}}$ と $\mathbf{a _ i}$ を所持した状態になる。
$e _ {\mathbf{a _ i}}$ と $\mathbf{a _ i}$ を使い、 $PAngle(\mathbf{a} _ 1,\dots,\mathbf{a} _ n,e _ \mathbf{a})$ を行う。 $\langle \mathbf{a} \rangle$ を手に入れる。
ここまでの処理を $\mathbf{m _ i}:=\mathbf{b _ i}$ に対しても行う。（実際には $\mathbf{a}$ と平行に行っている）
$e _ \mathbf{c } = e _ \mathbf{a} \boxtimes e _ \mathbf{b}$ を計算する。
$e _ \mathbf{c}$ を入力に $Reshare(e _ \mathbf{m},NewCiphertext)$ を呼び出す。
$e _ {\mathbf{c }}$ と $\mathbf{c _ i}$ を使い、 $PAngle(\mathbf{c} _ 1,\dots,\mathbf{c} _ n,e _ \mathbf{c})$ を行う。 $\langle \mathbf{c} \rangle$ を手に入れる。

$5$ で $Reshare$ を $NewCiphertext$ としているのは $e _ \mathbf{c}$ が $4$ の時点で1回乗算された暗号文となっているためです。そのまま $6$ で $PAngle$ を使うと $e _ \mathbf{c}$ の乗算回数が2回になってしまいます。よって、 $e' _ {\mathbf{c}}$ に変換して乗算回数をリセットする必要があります。

ペア

ペアというのは以下の乱数の組です。オンラインフェーズで乱数として活用します。

$\langle \mathbf{r} \rangle,[\mathbf{r}]$

$\mathbf{m _ i}:=\mathbf{r _ i}$ とし、 $PoPK(r _i)$ を行う。各パーティ $P _ i$ は $e _ {\mathbf{r _ i}}$ と $\mathbf{r _ i}$ を所持した状態になる。
$e _ {\mathbf{r _ i}}$ と $\mathbf{r _ i}$ を使い、 $PAngle(\mathbf{r} _ 1,\dots,\mathbf{r} _ n,e _ \mathbf{r})$ を行う。プロトコルは $\langle \mathbf{r} \rangle$ を手に入れる。
$e _ {\mathbf{r _ i}}$ と $\mathbf{r _ i}$ を使い、 $PBracket(\mathbf{r} _ 1,\dots,\mathbf{r} _ n,e _ \mathbf{r})$ を行う。プロトコルは $[ \mathbf{r} ]$ を手に入れる。