Acompany 技術ブログ/技術ブログ記事一覧/📝【技術】比較演算プロトコル(Nishide プロトコル)について
📝

【技術】比較演算プロトコル(Nishide プロトコル)について

はじめに

この記事では、MPCによる秘密計算の代表的な比較演算プロトコルを紹介します。原論文は以下のリンクから閲覧できます。また以下の論文で提案されている手法をこの記事ではNishideプロトコルと呼ぶことにします。
https://www.iacr.org/archive/pkc2007/44500343/44500343.pdf
 
秘密計算において、秘密情報 の大小関係を、 を明らかにせず求めたい場面は多く存在します。
であるか、 であるか、公開されている定数 に対して であるかどうかのチェックは、データを分析する上でよく用いられます。一般に、これらの演算は比較・等価の演算と呼ばれ、秘密計算では特別に専用のプロトコルを用意する必要があります。
Nishideプロトコルは、そのような専用プロトコルの一つであり、多くの論文で引用されています。このプロトコルにより、 の比較・等価演算をMPCで実行できます。

記法の説明

本記事で出てくる記法を説明します。
  • はプロトコルに参加している主体を表します（今後はパーティと呼びます）。各パーティは互いにセキュアなチャネルで結ばれているとします。
  • は素体を表します( は奇素数)。また、 を のビット長とします。
  • と書いた場合、を意味します。
  • 秘密情報 のシャミア秘密分散法によるシェアを と表します。
  • を真偽値とします。 が真ならば と表し、 が偽ならば とします。
    • 例えば秘密情報 に対して、 が真である場合、 とし、反対に が偽である場合、 とします。
  • 真偽値のシェアをと表します。例えば、 のシェアは、 と表記します。
  • 秘密情報 が二進展開により、 と書けるとします()。このとき、シェアの組 をビットシェア（bitwise sharing）と呼び、と表記します。

Nishideプロトコルの内容

Nishideプロトコルは、比較演算プロトコル本体と、そのプロトコル内で使用されている7つのサブプロトコルから構成されています。まず、サブプロトコルについて説明し、その後本体のプロトコルについて説明します。

サブプロトコル

比較演算プロトコルを実装するにあたり、以下の7つのサブプロトコルが必要となります。
 
  • Joint Random Number Sharing (RNS)
  • Joint Random Bit Sharing (RBS)
  • Unbounded Fan-In Or
  • Unbounded Fan-In And
  • Prefix-Or
  • Bitwise Less-Than
  • Joint Random Number Bitwise-Sharing (RBVS)
 
以下、それぞれのサブプロトコルについて順に説明します。

Joint Random Number Sharing(RNS)

ランダムな値 のシェア を生成するサブプロトコルです。このサブプロトコルはよく使われるため、以後RNSと略記します。
プロトコル
  1. 各 はランダムに を選択する。
  1. シャミア秘密分散法により、 は他のパーティに をシェアする。
  1. 各パーティはを計算する。
 

Joint Random Bit Sharing(RBS)

ランダムなビット値 のシェア を生成するサブプロトコルです。このサブプロトコルもよく使われるため、以後RBSと略記します。
 
プロトコル
  1. 各パーティはRNSにより を取得し、さらに を計算する。
  1. から を復号する（以下シェアを復号することをオープンすると書く）。
  1. もし ならば、1. からやり直す。
  1. ならば、 を計算する()
      • より、小さい方を とおく。
  1. を計算する。
      • であるため、 となる。
 

Unbounded Fan-In Or

ビットシェア が与えられたときに()、多入力論理和のシェア を生成するサブプロトコルです。
 
プロトコル
  1. を計算する()。
  1. を満たす次多項式 を定義する。
      • はラグランジュの補間多項式を使用して求める。
      • この時、 である。
        • なぜなら、 の時 は全て であり、 の時 は少なくとも一つは であるため。
      • である。したがって、 を計算できれば、 が生成できる(3~7でこの計算を行う)。
  1. パーティ はRNSにより、 を生成する()。
  1. パーティ は、 を計算し、 をオープンする。
  1. パーティ は、 を計算する。
  1. 各パーティは、以下のように を計算し、 をオープンする。
      • を計算
      • 各 の計算は並列に行えるため高速化可能である。
  1. を計算する。
  1. を計算する。
 

Unbounded Fan-In And

ビットシェア が与えられたときに()、多入力論理積 を生成するサブプロトコルです。
Unbounded Fan-in Or の 2. において、 とし、その他は同じように計算すれば実現できます。
なぜなら、 の時 は全て であり、 の時 は少なくとも一つは であるためです。
 

Prefix-Or

ビットシェア が与えられたときに()、 を満たすPrefix-Or を生成するサブプロトコルです。
注意1: とし、 とします()。
注意2: Prefix-Orのサブプロトコルにおいては、ビットシェアのインデックスの付け方が他とは異なることに注意してください。MSBのインデックスは1、LSBのインデックスは となります。
 
プロトコル
  1. 各パーティは、 を計算する()。
  1. 各パーティは、 を計算する()。
      • iff に が含まれている。
  1. 各パーティは、 を計算する。
      • iff が、 を含む最初のブロックである。
      • そのような を とする。
  1. 各パーティは、 を計算する()。
  1. 各パーティは、 を計算する()。
  1. 各パーティは を計算する。
      • iff
  1. を計算する。
      • の場合、 が成立するため、。
      • の場合、初めて となるところ(そのような を とする)で、 となる。また である。
      • の場合、 より、。
       
 

Bitwise Less-Than

が与えられたときに、 を生成するサブプロトコルです。
比較演算子 は、左辺と右辺が両方ともビットシェアの場合に利用します。
 
プロトコル
  1. 各パーティは、 を計算する。
  1. Prefix-Orを用いて を計算する。
  1. を計算する(ただし、)。
      • を上位ビットから比較したときに、番目のビット位置が初めて異なる値の場合、 となり、それ以外は となる。
  1. 最後に、 を計算する。
 

Joint Random Number Bitwise-Sharing (RBVS)

ランダム値 のビットシェア を生成するサブプロトコルです。よく使うサブプロトコルなので、以後RBVSと略記します。
前提として、 のビットシェアを各パーティに配布していることを想定しています。
 
プロトコル
  1. 各 について、RBSにより を生成。
  1. を生成。
  1. ならば を出力。
 

本体プロトコル

ここからは、本体の比較演算プロトコルについて説明します。
Nishideプロトコルは、以下の4つの比較演算プロトコルを提案しています。
なお は、 の計算を効率化させるために必要なものであり、実質サブプロトコルと考えても問題ありません。
 

の生成

定数 において()、値 が であるかチェックするため、シェア を生成する手法を紹介します。
 
アイデア
RNSにより乱数のシェア を生成し、 を計算し、 をオープンします。
この時、 と表現できます。
が成立するかどうかで場合分けし、比較を行います。
以下は、全てのパターンを列挙しています。
  • が成立しない場合
    • の場合
      • iff
    • の場合
      • iff
  • が成立する場合
    • iff
 
プロトコル
  1. 各パーティは を生成し、 を得る。
  1. 各パーティは を計算し、 をオープンする。
  1. が成立しない場合
    1. の場合
      1. とする。
    2. の場合
      1. とする。
    3. を出力する。
  1. が成立する場合
    1. とする。
    2. を出力する。
      3.  

の生成

をチェックするためのシェア を生成する手法を紹介します。
このシェアを生成する目的は、以降の比較演算プロトコルで使用するためです。
 
アイデア
  • のとき
    • は偶数となります。つまり、 となります(LSBが0)。
    • したがって、 の1ビット目が0 のとき、 が言えます。
  • のとき
    • は奇数となります。つまり、 となります(LSBが1である)。
    • したがって、 の1ビット目が1 のとき、 が言えます。
 
上記の事実から、 が与えられた時に を生成するプロトコルを利用することによって、 を生成できます。手法のアイデアを以下に示します。
 
アイデア
  • 乱数 のシェア に対して、 を計算し、 をオープンします。
  • の計算の際に、reduction(実際にモジュラ演算を行うことの意。つまり、) が発生しなかった場合、 が成立します。reductionが発生した場合、 が成立します。
  • reductionが発生したかどうかは、 をチェックすることでわかります。
    • のときは、reductionは発生していない。
    • のときは、reductionが発生した。
 
プロトコル
  1. RBVSにより を生成し、 を得る。
  1. を計算し、 をオープンする。
  1. を計算する。
      • の計算は
          1. の場合
              • を返す
          1. の場合
              • を返す
 

の生成

続いて、 をチェックするためのシェア を生成する手法を紹介します。
 
アイデア
以下の真偽値表は、 という3つの変数を利用して、 の値を計算しているものです。以下の真偽値表を利用すると、
という等式が成り立ちます。
 
プロトコル
  1. を生成する。
  1. とし、 を計算する。
 
 

の生成

最後に、 をチェックするためのシェア を生成する手法を紹介します。
 
アイデア
を計算するには、 を計算すれば良い。
 
プロトコル
  1. を生成し、 を得る。
  1. を計算し、 を計算してオープンする。
  1. 以下のように、 を計算する。
    1. ならば、
    2. ならば、
      • ならば(つまり、 ならば)、 は1 になる。
 

まとめ

本記事のまとめは以下の通りです。
  • 代表的な比較演算プロトコルであるNishideプロトコルについて説明しました。
  • Nishideプロトコルを使用すると、秘密情報, 定数 に対して、 の生成が可能となる。
 

参考文献

https://www.iacr.org/archive/pkc2007/44500343/44500343.pdf

補足資料

Prefix-OrとBitwise Less Thanの簡単な例を図示します。
 
Xでポスト