Two-Sided Malicious Security for Private Intersection-Sum with Cardinality(CRYPTO2020)を読んだ
どういう論文か
Private Intersection-Sum with Cardinalityに関する研究である。
Private Intersection-Sum with Cardinality(以下PI-SCA)
共通集合の濃度と同時に、共通集合に属する要素に関連づけられた値の和を算出するPSIのバリアントである。例えば、集合と集合
であれば
である。ここで
が
に関連づけられていることを
と書くことにすると、
のように対応していればそのIntersection-Sumはである。このIntersection-Sumはpaillier暗号のような加法準同型性を持つ暗号で実現できる。
関連技術
Σプロトコル
3-move honest-verifier zero-knowledge プロトコルである。Proverがコミットして、Verifierがチャレンジして、Proverがレスポンスを返す。この流れを３-moveという。つまり以下の流れになる
- ProverがVerifierにコミットメントtを送る
- VerifierがProverにランダムなチャレンジcを送る
- VerifierがProverにレスポンスsをおくる
OPRF(Oblivious Psuedo-Randomness Function)
OPRFとはが鍵
を持っており、
が入力
を持っているとき擬似ランダム関数
を評価するプロトコルのことである。数式で表すと以下のようになる。
つまり擬似ランダム関数をの情報を漏らさずに評価し、その出力は
のみが得られる。
PSI-CA(Private Set Intersection CArdinality)
PSI-CAとはPSIのバリアントで共通集合の要素の情報を漏らさず、その濃度だけを出力するプロトコルのこと。
共有鍵(key share)
共有鍵とは秘密鍵を秘密分散したシェアのこと。例えばを共有鍵にすると
のように秘密分散し、
を
が、
を
が持つ。
新規性
以前はPI-SCAのMalicious Securityなモデルでは、受信者と送信者のうちで片方向、例えば受信者のみが出力を得るような方法しか存在しなかった。
この研究でTwo-Sided Malicious Security、つまり両方向出力をしつつもをMalicious Securityを保証するプロトコルを提案する。これにより両方が出力得たいようなシナリオに対応することができる。
PI-SCAで初めてMalicious Securityと同時に線形の通信量と計算量を達成している。
手法
まずこのPI-SCAプロトコルが何をやろうとしているのかの概要図を紹介する。（なお、コミットメントや証明などはまだよくわかっていないため省略）
まず、両方向出力にするためには、まず受信者が得た出力が正確なものであることを証明しなければならない。そのため、プロトコルを役割を入れ替えて並行実行する手法をとる。（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（二つの値の内部で使われている値
が一致していること）
を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とそれに関連づけられた値に対してシャッフルを行うとき、
をre-randomizeしつつシャッフルするが、その
が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)
