(57)【特許請求の範囲】
【請求項１】
サーバ（Ｓ）がｎ個のインデックス付きビット（ｘ１，．．．，ｘｎ）を含む２進符号（Ｘ）を有し、クライアント（Ｃ）がｎ個のインデックス付きビット（ｙ１，．．．，ｙｎ）を含む２進符号（Ｙ）を有し、クライアントおよびサーバの各２進符号は、サイズｎをもつ２進マスク符号（Ｍ，Ｍ’）にさらに関連付けられ、この２進マスク符号の１におけるビット（ｍｉ）のインデックスは、ハミング距離の決定のため考慮されるべきクライアントおよびサーバの符号のビット（ｘｉ，ｙｉ）のインデックスを示し、クライアント（Ｃ）もサーバ（Ｓ）も他方の符号に関する情報を得ることなしに、入力としてクライアントの２進符号（Ｘ）およびサーバの２進符号（Ｙ）を用いるハミング距離の評価を備える、２つの２進入力間のハミング距離の評価が実行されるデータを処理するセキュアな方法であって、
サーバがｎ個のインデックス付き値（ｒｉ，ｒ’ｉ）の２つの集合をランダムに生成し、これらのそれぞれの合計（Ｒ，Ｒ’）を計算するステップａ）と、
クライアントの２進符号（Ｙ）の各ビット（ｙｉ）に対して、クライアントが、２個の要素を含む中間データをサーバから取得するために紛失通信の技術を利用し、これらの２個の要素のうち、
−第１の要素が、クライアントの符号のビット（ｙｉ）とサーバの符号のうち同じインデックスをもつビット（ｘｉ）との間の「排他的論理和」演算の結果とマスク符号の対応するビット（ｍｉ，ｍｉ’）の値との間の共通集合の値に加算された、第１の集合からのランダムに生成された値（ｒｉ）を含み、
−クライアントの２進符号の各ビット（ｙｉ）に対する中間データの第２の要素が、マスク符号の対応するビット（ｍｉ，ｍｉ’）の値の共通集合に加算された、第２の集合からのランダムに生成された値（ｒ’ｉ）を含む、
ステップｂ）と、
クライアントは、
−一方で、ランダムに生成された値の第１の合計（Ｒ）に加算された、マスク符号の１であるビットに関するクライアントの符号とサーバの符号との間のハミング距離の値を取得するために中間データの第１の要素と、
−他方で、ランダムに生成された値の第２の合計（Ｒ’）に加算された、マスク符号の共通集合のサイズを取得するために中間データの第２の要素と、
を合計する、ステップｃ）と、
を含む、データを処理するセキュアな方法。
【請求項２】
ステップａ）とステップｂ）との間で、サーバが、各四つ組が２進符号のうちの同じインデックスをもつビット（ｘｉ）と、マスク符号のうちの同じインデックスをもつビットとに対応し、かつ、各四つ組が
−ビットと同じインデックスをもつ、第１の集合からのランダムに生成された値（ｒｉ）と、第２の集合からのランダムに生成された値（ｒ’ｉ）と、
−ビットと同じインデックスをもつ、第１の集合からのランダムに生成された値（ｒｉ）と、第２の集合からのランダムに生成された値（ｒ’ｉ）と、
−第１の集合からのランダムに生成された値（ｒｉ）と前記ビットおよびマスク符号の対応するビットの間の共通集合との合計（ｒｉ＋ｍｉ．ｘｉ）と、第２の集合からのランダムに生成された値（ｒ’ｉ）とマスク符号のビットとの合計（ｒ’ｉ＋ｍｉ）と、
−第１の集合からのランダムに生成された値（ｒｉ）とマスク符号のビットおよび２進符号のビットの反対値の間の共通集合との合計
【数１】
0005865556.tif 000051
と、第２の集合からのランダムに生成された値（ｒ’ｉ）とマスク符号のビットとの合計（ｒ’ｉ＋ｍｉ）と、
をこの順序で含んでいる、符号に関連付けられたインデックス付き四つ組（Ｑｉ）の集合を生成する、
請求項１に記載のセキュアな方法。
【請求項３】
クライアントが、紛失通信によって、クライアントの２進符号の各ビット（ｙｉ）に対して、
−クライアントの符号のビット（ｙｉ）が０に等しく、かつ、マスク符号の対応するビットが０に等しい場合、クライアントが四つ組（Ｑｉ）の第１の要素を取り出し、
−クライアントの符号のビット（ｙｉ）が１に等しく、かつ、マスク符号の対応するビットが０に等しい場合、クライアントが四つ組（Ｑｉ）の第２の要素を取り出し、
−クライアントの符号のビット（ｙｉ）が０に等しく、かつ、マスク符号の対応するビットが１に等しい場合、クライアントが四つ組（Ｑｉ）の第３の要素を取り出し、
−クライアントの符号のビット（ｙｉ）が１に等しく、かつ、マスク符号の対応するビットが１に等しい場合、クライアントが四つ組（Ｑｉ）の第４の要素を取り出すように、
クライアントの符号のビット（ｙｉ）と同じインデックスをもつ四つ組（Ｑｉ）の要素を取り出す、
請求項２に記載のセキュアな方法。
【請求項４】
−クライアントが合計の２つの結果（Ｔ，Ｔ’）をサーバに送信するステップと、
−サーバが、ハミング距離の分子および分母をそれぞれ取得するために、各合計（Ｔ，Ｔ’）から、ランダムに生成された値のそれぞれの合計（Ｒ，Ｒ’）を減算するステップと、
をさらに備える、請求項１ないし３のいずれか一項に記載のセキュアな方法。
【請求項５】
−サーバがランダムに生成された値の合計の２つの結果（Ｒ，Ｒ’）をクライアントに送信するステップと、
−クライアントが、ハミング距離の分子および分母をそれぞれ取得するために、中間データの要素の各合計から、ランダムに生成された値の対応する合計を減算するステップと、
をさらに備える、請求項１ないし３のいずれか一項に記載のセキュアな方法。
【請求項６】
サーバは、ｎ個のインデックス付きビットをもつ少なくとも２個の２進符号（Ｘ１，．．．，ＸＮ）と、等しい数のマスク符号とを有し、
−ステップａ）の間に、サーバは、このサーバが有する２進符号の２倍のランダム値（ｒ１ｉ，．．．，ｒｎｉ）の集合を生成し、各集合の中の値の合計（Ｒ１，．．．，ＲＮ）を計算し、
−サーバは、このサーバが有する２進符号（Ｘ１，．．．，ＸＮ）と同数のインデックス付き四つ組（Ｑｉ）の集合を生成し、前記四つ組の集合を連結し、
−クライアントによって取得された中間データが、サーバのあらゆる２進符号（Ｘ１，．．．，ＸＮ）に対して、クライアントがサーバの各２進符号に対して個別に取得したであろう中間データの連結を含む、
請求項２ないし５のいずれか一項に記載のセキュアな方法。
【請求項７】
少なくとも１回の演算が行われた後、クライアントおよびサーバの各々は、他方が、
−使用された演算がプロトコルに準拠するか否かと、
−演算が改竄データに関して使用されたか否かと、
を検出することができる情報を公開する、請求項１ないし６のいずれか一項に記載のセキュアな方法。
【請求項８】
２進符号は、バイオメトリックデータである、請求項１ないし７のいずれか一項に記載のセキュアな方法。
【請求項９】
２進符号は、符号化された虹彩画像である、請求項８に記載のセキュアな方法。
【請求項１０】
識別対象である個人（Ｉ）の少なくとも１台の制御サーバ（ＳＣ）と、リストに掲載された個人のＮ個の基準データ（ｂ０．．．ｂＮ−１）のベース（ＤＢ）の少なくとも１台の管理サーバ（ＳＧ）と、を備え、
制御サーバ（ＳＣ）が個人（Ｉ）のデータ（ｂ）の獲得を進めるように構成されている、個人（Ｉ）の識別のためのシステムであって、
制御サーバ（ＳＣ）および管理サーバ（ＳＧ）は、個人のデータと各基準データとの間のハミング距離を決定するために個人（Ｉ）のデータ（ｂ）とリストに掲載された個人の少なくとも１つの基準データとの間で請求項１ないし９のいずれか一項に記載されたハミング距離の評価のためのセキュアな方法を実行し、前記基準データ（ｂｉ）の出所であるリストに掲載された個人としてこの個人を識別するために識別対象である個人（Ｉ）のデータ（ｂ）との所定の閾値を超える類似度を有する基準データ（ｂｉ）を決定するように構成されている処理手段を備えることを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クライアントもサーバも他方のデータに関する情報を得ていないタイプであるクライアントおよびサーバによって保持されたデータのセキュアな処理に関する。
【０００２】
本発明は、ハミング距離を計算することにより比較を実施するセキュアなバイオメトリック識別方法と、特に虹彩比較による識別方法に適用される。
【背景技術】
【０００３】
２つの２進符号の間のハミング距離は、２つの符号の間の異なるビットの個数を示す周知の数学的概念である。これは、数学的には、
【０００４】
【数１】
0005865556.tif 000002
として記述され、式中、ＸおよびＹは、２つの２進符号であり、
【０００５】
【数２】
0005865556.tif 000003
は、「排他的論理和」演算子である。
【０００６】
ハミング距離を計算することは、特に、バイオメトリック識別の分野において、たとえば、比較対象である２人の個体の虹彩の間の類似度を評価するため使用される。たとえば、論文Ｈｏｗ  ｉｒｉｓ  ｒｅｃｏｇｎｉｔｉｏｎ  ｗｏｒｋｓ；  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  ｃｉｒｃｕｉｔｓ  ａｎｄ  ｓｙｓｔｅｍｓ  ｆｏｒ  ｖｉｄｅｏ  ｔｅｃｈｎｏｌｏｇｙ，  ｖｏｌ．１４，  Ｎ）．１．，  Ｊａｎｕａｒｙ  ２００４のようなＪｏｈｎ  Ｄａｕｇｍａｎの著作物が知られている。
【０００７】
２つの非常に類似した虹彩は、虹彩を表現する符号の間で異なるビットの個数が少ないので、非常に小さいハミング距離を有する。
【０００８】
このような状況において、バイオメトリックデータの秘密性を守るためにこれらのデータに実行される演算をセキュア化すること、そして、これらの演算のため使用されるデータが第三者によって突き止められること、および、利用されることを防止することが特に重要である。このセキュア化は、ハミング距離の決定を安全にすることを含む。
【０００９】
これに関連して、たとえば、Ｇａｒｂｌｅｄ  Ｃｉｒｃｕｉｔｓ法を実行するセキュアなデータ処理方法が公知である。これは、仏国特許出願第１１６２０５８号明細書に当てはまる。
【００１０】
たとえば、刊行物：Ｍ．  Ｂｌａｎｔｏｎ  ａｎｄ  Ｐ．  Ｇａｓｔｉ，  Ｓｅｃｕｒｅ  ａｎｄ  Ｅｆｆｉｃｉｅｎｔ  Ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  Ｉｒｉｓ  ａｎｄ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ，  ＥＳＯＲＩＣＳ  ２０１１：  １９０−２０９のような準同型暗号化の技術を利用するセキュアなデータ処理方法もまた公知である。
【００１１】
これらの方法は、セキュリティの観点から有効であるが、実行されるために計算時間および計算資源のコストが嵩むという不利点がある。さらに、これらの方法は、いくつかのハミング距離を並列に決定するため最適化されることがなく、個人のバイオメトリック特徴のうちの１つをデータベースに格納された個人のバイオメトリック特徴と比較することにより個人を識別することが目的であるときに起こる事例である。
【００１２】
より一般的には、クライアントもサーバも他方のデータに関する情報を得ないタイプであり、高速に使用でき、かつ、大量の計算能力を必要としない、クライアントおよびサーバによって保持されたデータのセキュアな処理の必要性がある。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Ｊｏｈｎ  Ｄａｕｇｍａｎ著、Ｈｏｗ  ｉｒｉｓ  ｒｅｃｏｇｎｉｔｉｏｎ  ｗｏｒｋｓ；  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  ｃｉｒｃｕｉｔｓ  ａｎｄ  ｓｙｓｔｅｍｓ  ｆｏｒ  ｖｉｄｅｏ  ｔｅｃｈｎｏｌｏｇｙ，  ｖｏｌ．１４，  Ｎ）．１．，  Ｊａｎｕａｒｙ  ２００４
【非特許文献２】Ｍ．  Ｂｌａｎｔｏｎ  ａｎｄ  Ｐ．  Ｇａｓｔｉ，  Ｓｅｃｕｒｅ  ａｎｄ  Ｅｆｆｉｃｉｅｎｔ  Ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  Ｉｒｉｓ  ａｎｄ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ，  ＥＳＯＲＩＣＳ  ２０１１：  １９０−２０９
【発明の概要】
【発明が解決しようとする課題】
【００１４】
本発明の目的は、上記従来技術の不利点のうちの少なくとも１つを取り除くことである。
【００１５】
本発明の目的は、２つの２進入力を有するサブ関数の線形結合のタイプであり、そのうちの１つがハミング距離の計算関数であり、より高速に実行でき、かつ、計算資源にあまり費用が掛からない、関数のセキュアな評価方法を提案することである。
【００１６】
本発明の別の目的は、いくつかのハミング距離を並列に決定する方法を提案することである。
【課題を解決するための手段】
【００１７】
これに関連して、本発明は、クライアントおよびサーバがそれぞれｎ個のインデックス付きビットを含む２進符号およびｎ個のインデックス付きビットを含む２進符号を有し、クライアントもサーバも他方の符号に関する情報を得ることなしに、入力としてクライアントの２進符号およびサーバの２進符号を用いる関数の評価を含み、２つの２進入力を有するサブ関数の線形結合として記述された関数の評価が実施されるセキュアなデータ処理方法であって、
ａ）サーバがｎ個のインデックス付き値をランダムに生成し、関数を取得するためにサブ関数に適用された線形結合と同じ線形結合と共にこれらの値の線形結合を計算するステップと、
ｂ）クライアントの２進符号の各ビットに対して、クライアントが、サーバの符号のうち同じインデックスをもつビットとクライアントの２進符号の前記ビットとにおいて評価された対応するサブ関数の値に加算された、クライアントの符号のビットと同じインデックスをもつランダムに生成された値を含む中間データをサーバから取得するために紛失通信の技術を使用するステップと、
ｃ）２つの２進符号における関数の評価に加算された、ランダムに生成された値の線形結合を含む最終結果を取得するために、クライアントがクライアントの２進符号のあらゆるビットに対して、関数を取得するためにサブ関数に適用された線形結合と同じ線形結合を用いて、中間データの線形結合を行うステップと、
を備えることを特徴とする、セキュアなデータ処理方法を提案する。
【００１８】
有利な点として、任意選択的ではあるが、本発明による方法は、以下の特徴のうちの少なくとも１つを備える可能性もある：
【００１９】
−ステップａ）とステップｂ）との間で、サーバは、各２個組が２進符号のうちの同じインデックスをもつビットに対応し、かつ、各２個組が
○ビットと同じインデックスをもつランダムに生成された値と前記ビットおよびゼロにおいて評価された関数との合計と、
○ビットと同じインデックスをもつランダムに生成された値と前記ビットおよび１において評価された関数との合計と、
をこの順序で含んでいる、符号に関連付けられたインデックス付き２個組の集合を生成する。
【００２０】
−そして、クライアントが紛失通信によって、クライアントの２進符号の各ビットに対して：
○クライアントの符号のビットが０に等しい場合、クライアントが２個組の第１の要素を取り出し、
○クライアントの符号のビットが１に等しい場合、クライアントが２個組の第２の要素を取り出すように、
クライアントの符号のビットと同じインデックスをもつ２個組の要素を取り出す。
【００２１】
−この方法は、以下のステップをさらに備える：
〇クライアントが最終結果をサーバに送信し、
−サーバが２進符号における関数の評価を取得するために最終結果からランダムに生成された値の線形結合を減算する。
【００２２】
−この方法は、以下のステップをさらに備える：
〇サーバがランダムに生成された値の線形結合をクライアントに送信し、
〇クライアントが２進符号における関数の評価を取得するために最終結果からランダムに生成された値の線形結合を減算する。
【００２３】
−サーバは、ｎ個のインデックス付きビットをもつ少なくとも２個の２進符号を有し、
〇ステップａ）の間に、サーバは、このサーバが有する２進符号と同数のランダム値の集合を生成し、各集合の中の値の線形結合を計算し、
〇サーバは、このサーバが有する２進符号と同数のインデックス付き２個組の集合を生成し、前記２個組の集合を連結し、
〇クライアントによって取得された中間データが、サーバのあらゆる２進符号に対して、クライアントがサーバの各２進符号に対して個別に取得したであろう中間データの連結を含む。
【００２４】
−少なくとも１回の演算が行われた後、各クライアントおよびサーバは、情報を公開し、他方は、この情報から：
〇実行された演算がプロトコルに準拠するか否かと、
〇演算が改竄データに関して実行されたか否かと、
を検出する可能性がある。
【００２５】
−評価対象である関数は、クライアントの２進符号とサーバの２進符号との間のハミング距離であり、ハミング距離の決定は、一方の符号ともう一方の符号とで値が異なるが同じインデックスをもつビットの個数の決定を含み、ここで：
〇ステップａ）の間に、ランダムに生成された値の線形結合は、前記値の合計であり、
〇ステップｂ）の間に、クライアントの２進符号の各ビットに対してクライアントによって取り出された中間データは、クライアントの符号のビットと同じインデックスをもつランダムに生成された値と、クライアントの符号のビットとサーバの符号のうち同じインデックスをもつビットとの間の演算「排他的論理和」の結果との合計であり、
〇ステップｃ）の間に、クライアントは、２個の２進符号の間のハミング距離に加算された、ランダムに生成されたデータの合計を取得するために、クライアントの２進符号の全ビットに対する中間データを合計する。
【００２６】
−クライアントおよびサーバの各２進符号は、サイズｎをもつ２進マスク符号にさらに関連付けられ、この２進マスク符号の１におけるビットのインデックスは、ハミング距離の決定のため考慮されるべきクライアントおよびサーバの符号のビットのインデックスを示し：
〇ステップａ）の間に、サーバは、値の２つの集合と、これらのそれぞれの合計とをランダムに生成し、
〇ステップｂ）の間に、クライアントの２進符号の各ビットに対してクライアントによって取り出された中間データは、２個の要素を含み、これらの要素のうち：
●第１の要素は、クライアントの符号のビットとサーバの符号のうち同じインデックスをもつビットとの間の演算「排他的論理和」の結果とマスク符号の対応するビットの値との間の共通集合の値に加算された、第１の集合からのランダムに生成された値を含み、
●クライアントの２進符号の各ビットに対する中間データの第２の要素は、マスク符号の対応するビットの値の共通集合に加算された、第２の集合からのランダムに生成された値を含み、
〇ステップｃ）の間に、クライアントは：
●一方で、ランダムに生成された値の第１の合計に加算された、マスク符号の１であるビットに関するクライアントの符号とサーバの符号との間のハミング距離の値を取得するための中間データの第１の要素と、
●他方で、ランダムに生成された値の第２の合計に加算された、マスク符号の共通集合のサイズを取得するために中間データの第２の要素と、
を合計する。
【００２７】
−２進符号は、バイオメトリックデータである。
【００２８】
−２進符号は、符号化された虹彩画像である。
【００２９】
本発明は、識別対象である個人の少なくとも１台の制御サーバと、リストに掲載された個人のＮ個の基準データのベースの少なくとも１台の管理サーバと、を備え、制御サーバが個人のデータの獲得を進めるように構成されている、個人の識別のためのシステムであって、
制御サーバおよび管理サーバが個人のデータと各基準データとの間のハミング距離を決定するために個人のデータとリストに掲載された個人の少なくとも１つの基準データとの間の前記請求項のいずれか一項に記載された関数のセキュアな評価方法を実行するように、かつ、前記基準データの出所であるリストに掲載された個人としてこの個人を識別するため識別対象である個人のデータとの所定の閾値を超える類似度を有する基準データを決定するように構成されている処理手段を備えることを特徴とするシステムをさらに提案する。
【００３０】
関数を評価するため紛失通信の技術を実行することは、クライアントがサーバによって保持された符号に関する情報を取り出すことがないので、データに関して実行される演算をセキュア化すると共に、クライアントによって取り出される情報の量を制限して計算時間の点でコストを低下させる。
【００３１】
本発明のその他の特徴、目的および利点は、限定されることのない実施例として与えられた添付図面に関連して以下の詳細な説明から現れる。
【図面の簡単な説明】
【００３２】
【図１ａ】本発明によって提案されたデータ比較方法の実施形態を例示する図である。
【図１ｂ】本発明によって提案されたデータ比較方法の実施形態を例示する図である。
【図１ｃ】本発明によって提案されたデータ比較方法の実施形態を例示する図である。
【図２】本発明によって提案された方法の主要ステップを例示する図である。
【図３】虹彩比較によるバイオメトリック識別へのこの方法の適用のための虹彩の符号化を概略的に例示する図である。
【図４ａ】この方法を実行する状況を例示する図である。
【図４ｂ】この方法を実行する状況を例示する図である。
【発明を実施するための形態】
【００３３】
図１ａに関連して、同図は、２進符号ＸおよびＹをそれぞれ有するサーバＳおよびクライアントＣを示す。サーバＳまたはクライアントＣの一方または他方は、２つの２進符号の間のハミング距離の値が分かることを望むが、自分が保持する２進符号に関する情報をもう一方に渡すことがない。
【００３４】
各２進符号ＸおよびＹは、ｎ個のインデックス付きビットｘ１，．．．，ｘｎおよびｙ１，．．．，ｙｎをそれぞれ備える。
【００３５】
ハミング距離のセキュアな決定
図２に関連して、本発明による方法の主要ステップが示される。ステップ１００の間に、サーバは、ｎ個のランダム値ｒ１，．．．，ｒｎを生成する。これらの値は、好ましくは、整数であり、より有利には、
【００３６】
【数３】
0005865556.tif 000004
の要素である。サーバは、これらの値の合計Ｒ
【００３７】
【数４】
0005865556.tif 000005
を計算する。
【００３８】
ステップ２００の間に、サーバＳは、紛失通信によりクライアントに転送される可能性がある要素のインデックス付き集合を生成する。この事例では、これは、２個組（ダブレット）Ｄｉの集合であり、各２個組は、同じインデックスをもつ符号のビットｘｉに関連付けられている。
【００３９】
２個組Ｄｉの第１要素は、同じインデックスをもつランダムに生成された値ｒｉとビットｘｉの値との合計であり、第２要素は、同じインデックスをもつランダムに生成された値ｒｉとビットｘｉの共役との合計である。
【００４０】
各２個組は、その結果、１とｎとの間のｉに対して、
【００４１】
【数５】
0005865556.tif 000006
として記述される。
【００４２】
ステップ３００の間に、クライアントは、クライアントの２進符号の各ビットの紛失通信をサーバと行う。
【００４３】
紛失通信は、２人の当事者Ｐ１とＰ２との間の計算演算である。このタイプの演算では、Ｐ１は、Ｎ個のインデックス付き要素Ｘｉのリストを有し、Ｐ２は、リストの中の要素の個数Ｎが分かり、０とＮ−１との間でインデックスｉを選択する。紛失通信により、Ｐ２は、Ｐ１のｉ番目の要素、すなわち、ｉによってインデックス付けされたＰ１の要素を取り出す。
【００４４】
Ｐ１は、Ｐ２によって取り出された要素のインデックスに関する情報が分からない。
【００４５】
Ｐ２は、Ｐ１によって保持されたリストの他の要素に関する情報を取り出さない。
【００４６】
紛失通信の方法は、ここでは、ハミング距離の決定に適用される。この状況において、クライアントは、自分の２進符号のビットｙｉ毎に、同じインデックスをもつ２個組Ｄｉの要素のうちの一方を紛失通信する。
【００４７】
転送された２個組の要素は、ビットｙｉの値の関数である：ｙｉ＝０である場合、クライアントＣは、紛失通信により、２個組の第１要素、すなわち、ｒｉ＋ｘｉを受信する。ｙｉ＝１である場合、クライアントは、２個組の第２要素、すなわち、
【００４８】
【数６】
0005865556.tif 000007
を受信する。
【００４９】
要素の取り出しは、紛失通信によって行われるため、サーバＳは、どちらの要素が通信されたかに気付くことがないので、サーバは、この要素の取り出しからｙｉの値を推論できない。
【００５０】
同様に、各要素は、ランダム値を含むので、クライアントＣは、自分が取り出したビットｘｉまたは
【００５１】
【数７】
0005865556.tif 000008
の値を各要素から推論できない。
【００５２】
この方法において、クライアントによって取り出された要素に収容された２進符号のビットの値は、ｘｉとｙｉとの間の排他的論理和演算の結果と密接な関係がある。実際に、クライアントが
【００５３】
【数８】
0005865556.tif 000009
に等しいデータｄｉを取得したことは、簡単に検証される可能性がある。
【００５４】
クライアントは、クライアントの２進符号の各ビットに対して、クライアントの符号のビットｙｉとサーバの符号のうち同じインデックスをもつビットｘｉとの間の演算「排他的論理和」の値に加算された、クライアントの２進符号のビットｙｉと同じインデックスをもつランダムに生成された値ｒｉを含む中間データｄｉを受信する。
【００５５】
クライアントは、その後、ステップ４００の間に、クライアントの２進符号のビットに対応する中間データｄｉの集合を合計し、最終結果
【００５６】
【数９】
0005865556.tif 000010
を取得する。最終結果ＲＦは、２つの２進符号ＸとＹとの間のハミング距離に加算された、ランダムに生成された値ｒｉの合計Ｒを含む。
【００５７】
この方法の残りの部分は、データ比較方法の結果の受信側に依存する。ハミング距離を知らなければならないのがサーバである場合、ステップ５００の間に、クライアントは、最終結果ＲＦをサーバに送信し、サーバは、ハミング距離ＨＤ（Ｘ，Ｙ）を取得するためにこの最終結果からランダムに生成された値の合計Ｒを減算する。
【００５８】
ハミング距離を知らなければならないのがクライアントである場合、ステップ５１０の間に、サーバは、ランダムに生成された値の合計Ｒをクライアントに送信する。クライアントは、ハミング距離の値を取得するために最終結果ＲＦからこの合計Ｒを減算することができる。
【００５９】
このデータ処理方法は、「ハミング距離」関数以外の関数、特に、２つの２進入力のサブ関数の線形結合として記述された関数
【００６０】
【数１０】
0005865556.tif 000011
の評価に関して一般化される可能性がある。
【００６１】
この事例では、ステップ１００の間に、サーバＳは、ｎ個のランダム整数ｒ１，．．．，ｒｎをさらに生成し、線形結合
【００６２】
【数１１】
0005865556.tif 000012
を計算し、ここで、関数Ｆを取得するためにサブ関数ｆｉに適用された線形結合と同じ線形結合（すなわち、同じ係数λｉを含んでいる）がＲを計算するため適用される。
【００６３】
ステップ２００の間に、サーバＳによって生成された２個組Ｄｉは、Ｄｉ＝（ｒｉ＋ｆｉ（ｘｉ，０），ｒｉ＋ｆｉ（ｘｉ，１））の形式をしている。
【００６４】
各関数すなわち各ｆｉに対して紛失通信のステップ３００の間にクライアントによって取得された出力は、その結果、ｔｉ＝ｒｉ＋ｆｉ（ｘｉ，ｙｉ）である。
【００６５】
従って、ステップ４００の間に、クライアントＣは、λｉｔｉの集合を合計して、
【００６６】
【数１２】
0005865556.tif 000013
を取得する。ステップ５００および５１０は、前述と同じである：ステップ５００の間に、クライアントは、合計Ｔをサーバに送信し、サーバは、Ｔ−Ｒを計算し、Ｔ−Ｒの値をクライアントに返すことができる。ステップ５１０の間に、サーバは、Ｒをクライアントに送信し、クライアントは、値Ｔ−Ｒを計算し、サーバに返す。
【００６７】
この計算方法は、あらゆるｆｉに対して、
【００６８】
【数１３】
0005865556.tif 000014
を取り、あらゆるλｉを１に等しいと取ることにより、ハミング距離タイプの関数を包含する。
【００６９】
いくつかのハミング距離の並列決定
同じハミング距離のセキュアな決定の原理は、いくつかのハミング距離を同時に決定するために拡張される可能性がある。
【００７０】
図１ｂに関連して、サーバＳは、クライアントＹの２進符号と比較されるべきいくつかの２進符号Ｘ１＝ｘ１１，．．．，ｘ１ｎ，．．．，ＸＮ＝ｘＮ１，．．．，ｘＮｎを有する。
【００７１】
図２に例示されたステップ１００の間に、サーバＳは、各２進符号に対してｎ個のランダム値を生成する。たとえば、２個の２進符号Ｘ１、Ｘ２の事例では、サーバは、第１の２進符号Ｘ１に関連付けられたｎ個の値ｒ１，．．．，ｒｎと、第２の２進符号Ｘ２に関連付けられたｎ個の値ｒ’１，．．．，ｒ’ｎとをランダムに生成する。さらに、サーバは、値（ｒ１，．．．，ｒｎ）および（ｒ’１，．．．，ｒ’ｎ）の各集合の合計ＲおよびＲ’を計算する。
【００７２】
前述と同様に、ステップ２００の間に、サーバは、このとき、紛失通信によってクライアントに転送される可能性があり、各２個組Ｄｉが２進符号Ｘ１およびＸ２のうち同じインデックスをもつビットｘ１ｉ、ｘ２ｉに関連付けられている２個組Ｄｉの集合を作成する。
【００７３】
このため、サーバは、このサーバが有する２進符号Ｘｊと同数であり、各２個組が２進符号のビットに関連付けられ、前述と同様に２進符号のビットおよび同じインデックスをもつランダムに生成された値から構築する２個組のインデックス付き集合を生成する。サーバは、その結果、下記で表される２個組Ｄｉ：
【００７４】
【数１４】
0005865556.tif 000015
を取得するために前記集合を連結する。
【００７５】
クライアントは、その後、ステップ３００の紛失通信を実行し、このクライアントの２進符号のビットｙｉ毎に、クライアントがサーバの２進符号毎に別個に受信したであろう中間データの連結によって構成された中間データｄｉ：
【００７６】
【数１５】
0005865556.tif 000016
を取り出す。
【００７７】
前述と同様に、ステップ４００の間に、クライアントは、クライアントの２進符号のあらゆるビットｙｉに対して、取り出された中間データの集合を合計し、サーバの各２進符号に対して、サーバに知られているランダムに生成された値の合計に加算された、サーバの２進符号とクライアントの２進符号との間のハミング距離を取得する可能性がある。
【００７８】
クライアントは、その後、ステップ５００の間に、サーバの２進符号の全部または一部に対して、これらの合計をサーバに送信する可能性があり、その結果、サーバがこれらの合計から、すなわち、ランダムに生成された値の合計Ｒ、Ｒ’からクライアントの２進符号とサーバ自体の２進符号との間のハミング距離を推論する可能性がある。
【００７９】
逆に、ステップ５１０の間に、サーバは、ランダムに生成された値の合計Ｒ、Ｒ’の全部または一部をクライアントに送信する可能性があり、クライアントは、これらからサーバの対応する２進符号とこのクライアントの２進符号との間のハミング距離を推論する。
【００８０】
重み付きハミング距離の決定
方法変形例は、特に、個人の虹彩比較によるバイオメトリック識別の状況において適用可能である重み付きハミング距離の決定である。
【００８１】
図３に関連して、虹彩比較によるバイオメトリック識別が使用されるとき、虹彩の可視ゾーンは、これらのゾーンを表現する２進符号の間のハミング距離を決定することにより比較される。
【００８２】
さらに、虹彩の可視ゾーンだけを比較するために、１であるビットが眼の可視ゾーンに対応する２進符号の形式をしたマスクが各虹彩符号に関連付けられる。
【００８３】
重み付きハミング距離は、その結果、比較された両方の虹彩に共通である可視ゾーンだけが考慮されたハミング距離である。このハミング距離は、
【００８４】
【数１６】
0005865556.tif 000017
であり、式中、Ｍは、符号Ｘに関連付けられたマスク符号であり、Ｍ’は、符号Ｙに関連付けられたマスク符号である。
【００８５】
今度は、重み付きハミング距離の決定方法を説明する。
【００８６】
図１ｃに関連して、クライアントおよびサーバの各２進符号は、それぞれのマスク符号Ｍ＝（ｍ１，．．．，ｍｎ）、Ｍ’＝（ｍ’１，．．．，ｍ’ｎ）に関連付けられる。
【００８７】
ステップ１００の間に、サーバＳは、ｎ個のデータｒ１，．．．，ｒｎ，ｒ’１，．．．，ｒ’ｎからなる２つの集合をこれらのそれぞれの合計ＲおよびＲ’と共にランダムに生成する。
【００８８】
ステップ２００の間に、サーバＳは、各要素が２進符号のビットおよび同じインデックスをもつマスク符号のビットに対応するインデックス付き集合を生成する。各要素は：
【００８９】
【数１７】
0005865556.tif 000018
である。
【００９０】
ステップ３００の間に、クライアントは、Ｙのビットｙｉの値と対応するマスク符号のビットの値に応じて、各ビットｙｉに対するＱｉの要素のうちの１つを取り出すことにより、紛失通信を使用する。
【００９１】
ｙｉ＝０、ｍ’ｉ＝０ならば、クライアントは、（ｒｉ，ｒ’ｉ）を取り出す。
【００９２】
ｙｉ＝１、ｍ’ｉ＝０ならば、クライアントは、（ｒｉ，ｒ’ｉ）を取り出す。
【００９３】
ｙｉ＝０、ｍ’ｉ＝１ならば、クライアントは、（ｒｉ＋ｍｉ．ｘｉ，ｒ’ｉ＋ｍｉ）を取り出す。
【００９４】
ｙｉ＝１、ｍ’ｉ＝１ならば、クライアントは、
【００９５】
【数１８】
0005865556.tif 000019
を取り出す。
【００９６】
このようにして、クライアントは、実際に：
【００９７】
【数１９】
0005865556.tif 000020
【００９８】
【数２０】
0005865556.tif 000021
のような２個の変数ｔｉ、ｔ’ｉで構成された中間データを取り出す。
【００９９】
ステップ４００の間に、クライアントは、クライアントの符号Ｙのあらゆるビットｙｉに対する中間データを合計する。
【０１００】
【数２１】
0005865556.tif 000022
【０１０１】
【数２２】
0005865556.tif 000023
【０１０２】
クライアントによって取得された最終結果は、第１のランダムに生成された値ｒ１，．．．，ｒｎの合計に加算された、ハミング距離の分子に等しい値Ｔを含む。ハミング距離の分子は、実際には、マスクされていないゾーン、すなわち、マスク符号のビットが１であるゾーンに対応する位置だけに対する２つの虹彩符号のハミング距離である。
【０１０３】
最終結果は、第２のランダムに生成された値ｒ’１，．．．，ｒ’ｎの合計に加算された、ハミング距離の分母に等しいＴ’をさらに含む。ハミング距離の分母は、重み付きハミング距離の決定のため考慮された符号のサイズに対応する。
【０１０４】
前述のとおり、この方法の残りは、ハミング距離を生成しなければならない個人に依存する。ハミング距離を知ることを望むのがサーバである場合、ステップ５００の間に、クライアントは、２つの値ＴおよびＴ’をこのサーバに送信し、サーバは、ハミング距離の分子および分母を取得するためにこれらの値からそれぞれのＲおよびＲ’を減算する。その後に残ることは、一方をもう一方によって除算することである。
【０１０５】
クライアントがハミング距離を知る必要がある場合、ステップ５１０の間に、サーバは、第１および第２のランダムに生成された値の合計ＲおよびＲ’をクライアントに送信する。クライアントは、ハミング距離の分子および分母を取得するためにこれらの合計からそれぞれ値ＴおよびＴ’を減算する。除算がこの距離を生成する。
【０１０６】
この処理変形例は、前述のとおりいくつかのハミング距離の同時決定とも互換性がある。
【０１０７】
悪意のある当事者の事例における方法のセキュア化
前述された比較方法の変形例は、「ほぼ不正行為をしない」当事者、すなわち、もう一方の当事者によって保持されたデータに関する付加情報を取得しようとしながら、方法のステップに従う当事者の事例における計算のセキュア化を可能にする。
【０１０８】
別の実施の事例は、もう一方の当事者によって保持されたデータに関する情報を取得するために、必要に応じて、方法のステップに厳密に従うことなく、何らかのタイプの戦略を使用する「悪意のある」当事者の事例である。
【０１０９】
悪意のある当事者の事例において方法をセキュア化するために、クライアントまたはサーバによって実行された各演算で、後者は、もう一方のため、情報を公開することが保証される可能性があり、もう一方は、この情報から、演算が実行されるべきプロトコルに属するか否かと、この演算が不正データに関して使用されたか否かと、を検出する可能性がある。
【０１１０】
このため、２人の当事者が暗号解読秘密鍵を復号するか、または、知っていることを必要とすることなしに、暗号化されたデータに関する計算を行うことを可能にさせる準同型暗号化ツールが当業者に知られるように使用される可能性がある。より多くの情報のため、刊行物Ｍｅｈｍｅｔ  Ｓ．  Ｋｉｒａｚ，  Ｂｅｒｒｙ  Ｓｃｈｏｅｎｍａｋｅｒｓ，  Ｊｏｓｅ  Ｖｉｌｌｅｇａｓ：  Ｅｆｆｉｃｉｅｎｔ  Ｃｏｍｍｉｔｔｅｄ  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒ  ｏｆ  Ｂｉｔ  Ｓｔｒｉｎｇｓ．  ＩＳＣ  ２００７：  １３０−１４４を参照することができる。
【０１１１】
たとえば、準同型性の性質から恩恵を受ける「コミットメント」または「プレッジング」と呼ばれる演算Ｃｏｍが利用される可能性があり、すなわち、
【０１１２】
【数２３】
0005865556.tif 000024
であるような演算
【０１１３】
【数２４】
0005865556.tif 000025
および
【０１１４】
【数２５】
0005865556.tif 000026
を使用し、ｘ１、ｘ２、ｒ１、ｒ２にかかわらず、
【０１１５】
【数２６】
0005865556.tif 000027
は、たとえば、加算であり、
【０１１６】
【数２７】
0005865556.tif 000028
は、乗算である。
【０１１７】
これらのプレッジング演算は、この方法のステップの集合に適用される。
【０１１８】
第一に、サーバによるランダム値の生成のためのステップ１００の前に、クライアントＣは、クライアントの２進符号のビットｙｉ毎に、Ｃｏｍ（ｙｉ，ｘｉ）を計算し、公開する。ゼロ知識証明を使用することにより、Ｃのビットｙｉが間違いなくビットである、という知識をさらに証明する。
【０１１９】
次に、サーバがステップ２００で２個組
【０１２０】
【数２８】
0005865556.tif 000029
を生成するとき、サーバは、２個組を公開することなく、２個組の両方の要素の間の差が絶対値１であるという知識についてのゼロ知識証明を生成することができる。逆の場合、クライアントは、サーバ側に不正行為があったことを検出する。
【０１２１】
サーバＳは、その後、各２個組の要素がＤｉ＝（ａｉ，ｂｉ）を意味することを保証し、サーバは、（Ａｉ＝Ｃｏｍ（ａｉ，αｉ））ｉ＝１．．．ｎおよび（Ｂｉ＝Ｃｏｍ（ｂｉ，βｉ））ｉ＝１．．．ｎを計算し、公開する。
【０１２２】
紛失通信ステップ３００の間に、クライアントは、サーバから、中間データｔｉの他に、対応するデータτｉを受信し、クライアントは、中間データを保証し、すなわち、クライアントは、何らかのｉに対して、ｔｉおよびτｉの関数であるデータＣｉ＝Ｃｏｍｉ（ｔｉ，τｉ）を計算し、公開するが、このデータは、サーバにｔｉおよびτｉの値を推論させない。
【０１２３】
クライアントが結果Ｔを取得するために中間データｔｉを合計し終えたとき、クライアントは、合計Ｔ’を取得するためにデータτｉも合計する。
【０１２４】
クライアントは、次に、前述のとおり、
【０１２５】
【数２９】
0005865556.tif 000030
を計算し、Ｃｏｍ（Ｔ，Ｔ’）を公開する。
【０１２６】
クライアントは、次に、合計ＴおよびＴ’をサーバに送信する。あらゆるＣｉに事前にアクセスしたサーバは、
【０１２７】
【数３０】
0005865556.tif 000031
を計算する能力があり、その結果、データｔｉと、それ故に、データｙｉとが改竄されていないことを検証するため、Ｃｏｍ（Ｔ，Ｔ’）の値を検証する。
【０１２８】
代替的に、サーバＳは：
【０１２９】
【数３１】
0005865556.tif 000032
を計算する。
【０１３０】
サーバＳは、クライアントにＲと、Ｋ＝Ｃｏｍ（２Ｒ＋ｎ，ρ）という証明とをクライアントに送信し、クライアントＣは、
【０１３１】
【数３２】
0005865556.tif 000033
を計算し、Ｋ＝Ｃｏｍ（２Ｒ＋ｎ，ρ）という証明を検証する。最後に、クライアントは、合計Ｔ−Ｒを計算し、サーバに返す。
【０１３２】
同じタイプのセキュアな方策が計算中で実行される他の演算に適用できる。
【０１３３】
図４ａおよび図４ｂに関連して、これらは、個人のバイオメトリック識別の方法を実行する状況を示す。この識別は、たとえば、セキュアな場所へのアクセス制御である可能性がある。
【０１３４】
データベースＤＢは、ｉが０からＮ−１であって、たとえば、ある場所に入る権限が与えられているとして、または、そうでなければ、この場所に居ることが禁止されている個人としてリストに掲載された個人のＮ個のインデックス付きバイオメトリックデータｂｉの集合を備える。
【０１３５】
このデータベースＤＢは、適当なプログラムによって使用される計算手段を取り付けることができる管理サーバＳＧにリンクされる。管理サーバは、前述された方法のサーバＳを構成する。
【０１３６】
個人Ｉは、制御サーバＳＣによって識別され、適切なプログラムによって使用される計算手段がさらに取り付けられ、個人に特有のデータ、特に、バイオメトリックデータｂの獲得および処理のための手段１１をさらに備える。
【０１３７】
データｂは、知られているように、デジタル化され、特に、個人の虹彩のようなバイオメトリック特徴を用いて符号化された画像を起源とする可能性がある。
【０１３８】
データｂは、個人の識別子文書にデジタル形式で格納される可能性もある。
【０１３９】
基本のデータｂ０からｂＮ−１は、本事例では、符号化された個人の虹彩画像でもある。本事例では、データベースＤＢは、各虹彩データｂｉに対して、対応するマスク符号ｍｉをさらに含む。制御サーバは、虹彩画像ｂに対応するマスク符号ｍをさらに獲得する、または、これを取得するためにデータｂを処理する可能性がある。これらのマスク符号は、可視虹彩のゾーンを示し、その結果、利用可能であり、これらのゾーンは、典型的に、瞼または睫毛によって隠されていない領域である。
【０１４０】
制御サーバが２進虹彩符号の形式で符号化された個人のバイオメトリックデータｂと対応するマスク符号とを取得すると、制御サーバは、図１から図３に関連して前述されたとおりに、データｂとデータベースに格納された虹彩データｂｉの集合との間で比較方法を行う可能性がある。制御サーバは、サーバと対話するクライアントを構成する。
【０１４１】
好ましくは、しかし、限定されることなく、制御サーバは、データｂといくつかのデータｂｉとの間で同時に比較方法を行い、これらの比較の１つずつは、対応するマスク符号による重み付きハミング距離の決定を含む。
【０１４２】
同様に、制御サーバは、好ましくは、ハミング距離の値を取得する管理サーバである。
【０１４３】
データｂがあらゆるデータｂｉと比較されると、管理サーバは、適切な場合、あらゆるデータ群ｂｉの中でデータｂとの最大類似度を有するデータｂｉ、または、データ群ｂｉの中で、所定の閾値を超える２つのデータの間の類似度の比率に対応する、データｂとのハミング距離が所定の閾値より小さいデータｂｉを識別する。
【０１４４】
データｂｉが存在する場合、これは、このデータの出所である個人が識別対象である個人に対応することを意味する。
【０１４５】
管理サーバによって取得された結果に応じて、管理サーバは、次のステップを開始し、または、開始せず、たとえば、管理サーバは、身元確認が行われたセキュアな場所への個人のアクセスを許可する、または、拒絶する可能性がある。
【０１４６】
上記方法は、セキュアであり、かつ、容易に実行できるという利点がある。この方法は、特に、相互に機密性を保持すべき様々な当事者によって保持されたデータから評価されるべき関数のタイプに関して、そして、さらに、ハミング距離からの比較計算の事例では、決定されるべきハミング距離の個数およびアプリケーション状況に応じて、さらに、この方法を実行する当事者の性質にさえ応じて、多くの変形例に変化させられる可能性がある。
【０１４７】
以下は、ハミング距離を計算する方法の実装の実施例である。
【０１４８】
ハミング距離を計算する方法の実装の実施例は、以下のとおりである。
【０１４９】
●入力：
−サーバＳ：ｎ個のビットの系列  Ｘ＝（ｘ１，．．．，ｘｎ）
−クライアントＣｌ：ｎ個のビットの系列  Ｙ＝（ｙ１，．．．，ｙｎ）
【０１５０】
●出力：
−第１の選択肢：Ｓは、ｄＨ（Ｘ，Ｙ）を取得し、Ｃｌは、何も取得しない。
−第２の選択肢：Ｃｌは、ｄＨ（Ｘ，Ｙ）を取得し、Ｓは、何も取得しない。
【０１５１】
●プロトコル：
【０１５２】
１．  Ｓは、ｎ個のランダム値
【０１５３】
【数３３】
0005865556.tif 000034
を生成し、
【０１５４】
【数３４】
0005865556.tif 000035
を計算する。
【０１５５】
２．  ｉ＝１，．．．，ｎに対して、ＳおよびＣｌは、ＯＴ１２を実行し、ここで、
−Ｓが送信側であり、Ｃｌが受信側である。
−Ｃｌの選択ビットは、ｙｉである。
−Ｓの入力は、
【０１５６】
【数３５】
0005865556.tif 000036
である。
−Ｃｌによって取得された出力は、その結果、
【０１５７】
【数３６】
0005865556.tif 000037
である。
【０１５８】
３．  Ｃｌは、
【０１５９】
【数３７】
0005865556.tif 000038
を計算する。
【０１６０】
４．  第１の選択肢：
（ａ）Ｃｌは、ＴをＳに送信する。
（ｂ）Ｓは、Ｔ−Ｒを計算し、返す。
第２の選択肢：
（ａ）Ｓは、ＲをＣｌに送信する。
（ｂ）Ｃｌは、Ｔ−Ｒを計算し、返す。
【０１６１】
ハミング距離の実施例−悪意のある当事者の事例：
【０１６２】
●入力：
−サーバＳ：ｎ個のビットの系列  Ｘ＝（ｘ１，．．．，ｘｎ）
−クライアントＣｌ：ｎ個のビットの系列  Ｙ＝（ｙ１，．．．，ｙｎ）
【０１６３】
●出力：
−第１の選択肢：Ｓは、ｄＨ（Ｘ，Ｙ）を取得し、Ｃｌは、何も取得しない。
−第２の選択肢：Ｃｌは、ｄＨ（Ｘ，Ｙ）を取得し、Ｓは、何も取得しない。
【０１６４】
●プロトコル：
【０１６５】
１．  Ｃｌは、自分のビットｙｉを保証する：Ｃｌは、各ｉ＝１．．．ｎに対して、Ｃｏｍ（ｙｉ，ｘｉ）を計算し、公開する。Ｃｌは、ゼロ知識証明を使用して、ｙｉ＝０またはｙ１＝１であるという保証に関してさらに証明する。
【０１６６】
２．  Ｓは、ｎ個のランダム値
【０１６７】
【数３８】
0005865556.tif 000039
を生成し、
【０１６８】
【数３９】
0005865556.tif 000040
を計算する。
【０１６９】
３．  各ｉ＝１，．．．，ｎに対して、Ｓは、
【０１７０】
【数４０】
0005865556.tif 000041
を計算し、ａｉおよびｂｉを保証する。Ｓは、（Ａｉ＝Ｃｏｍ（ａｉ，αｉ））ｉ＝１，．．．，ｎおよび（Ｂｉ＝Ｃｏｍ（ｂｉ，βｉ））ｉ＝１，．．．，ｎを計算し、公開する。
【０１７１】
４．  Ｓは、ゼロ知識証明を使用して、各ｉ＝１，．．．，ｎに対して、｜ｂｉ−ａｉ｜＝１であるという保証をＣｌに対して証明する。
【０１７２】
５．  各ｉ＝１，．．．，ｎに対して、ＳおよびＣｌは、ＣＯＴを実行し、ここで、
−Ｓが送信側であり、Ｃｌが受信側である。
−Ｃｌの選択ビットは、ｙｉである。
−Ｓの入力は、（ａｉ，ｂｉ）である。
−Ｃｌによって取得された出力は、
【０１７３】
【数４１】
0005865556.tif 000042
かつ、τｉである。
−両方の当事者は、Ｃｉ＝Ｃｏｍ（ｔｉ，τｉ）を取得する。
【０１７４】
６．  Ｃｌは、
【０１７５】
【数４２】
0005865556.tif 000043
を計算する。
【０１７６】
７．  第１の選択肢：
（ａ）Ｃｌは、
【０１７７】
【数４３】
0005865556.tif 000044
を計算する。
（ｂ）Ｃｌは、Ｓに対してＴを送信し、Ｃ＝Ｃｏｍ（Ｔ，τ）であることを証明する。
（ｃ）Ｓは、
【０１７８】
【数４４】
0005865556.tif 000045
を計算し、Ｃ＝Ｃｏｍ（Ｔ，τ）という証明を検証する。
（ｄ）Ｓは、Ｔ−Ｒを計算し、返す。
第２の選択肢：
（ａ）Ｓは、
【０１７９】
【数４５】
0005865556.tif 000046
を計算する。
（ｂ）Ｓは、Ｃｌに対してＲを送信し、Ｋ＝Ｃｏｍ（２Ｒ＋ｎ，ρ）であることを証明する。
（ｃ）Ｃｌは、
【０１８０】
【数４６】
0005865556.tif 000047
を計算し、Ｋ＝Ｃｏｍ（２Ｒ＋ｎ，ρ）であるという証明を検証する。
（ｄ）Ｓは、ＲをＣｌに送信する。
（ｅ）Ｃｌは、Ｔ−Ｒを計算し、返す。
【０１８１】
２個の２進入力を有する関数群の線形結合関数のセキュアな評価：
【０１８２】
●入力：
−サーバＳ：ｎ個のビットの系列  Ｘ＝（ｘ１，．．．，ｘｎ）
−クライアントＣｌ：ｎ個のビットの系列  Ｙ＝（ｙ１，．．．，ｙｎ）
【０１８３】
●出力：
−第１の選択肢：Ｓは、ｆ（Ｘ，Ｙ）＝Σλｉｆｉ（ｘｉ，ｙｉ）を取得し、Ｃｌは、何も取得しない。
−第２の選択肢：Ｃｌは、ｆ（Ｘ，Ｙ）＝Σλｉｆｉ（ｘｉ，ｙｉ）を取得し、Ｓは、何も取得しない。
【０１８４】
●プロトコル：
１．  Ｓは、ｎ個のランダム値
【０１８５】
【数４７】
0005865556.tif 000048
を生成し、
【０１８６】
【数４８】
0005865556.tif 000049
を計算する。
【０１８７】
２．  ｉ＝１，．．．，ｎに対して、ＳおよびＣｌは、、ＯＴ１２を実行し、ここで、
−Ｓが送信側であり、Ｃｌが受信側である。
−Ｃｌの選択ビットは、ｙｉである。
−Ｓの入力は、（ｒｉ＋ｆｉ（ｘｉ，０），ｒｉ＋ｆｉ（ｘｉ，１））である。
−Ｃｌによって取得された出力は、その結果、ｔｉ＝ｒｉ＋ｆｉ（ｘｉ，ｙｉ）である。
【０１８８】
３．  Ｃｌは、
【０１８９】
【数４９】
0005865556.tif 000050
を計算する。
【０１９０】
４．  第１の選択肢：
（ａ）Ｃｌは、ＴをＳに送信する。
（ｂ）Ｓは、Ｔ−Ｒを計算し、返す。
第２の選択肢：
（ａ）Ｓは、ＲをＣｌに送信する。
（ｂ）Ｃｌは、Ｔ−Ｒを計算し、返す。
【図１ａ】
0005865556.tif 000052
【図１ｂ】
0005865556.tif 000053
【図１ｃ】
0005865556.tif 000054
【図２】
0005865556.tif 000055
【図３】
0005865556.tif 000056
【図４ａ】
0005865556.tif 000057
【図４ｂ】
0005865556.tif 000058