JP6467063B2 - 秘密認証符号付加装置、秘密認証符号付加方法、およびプログラム - Google Patents

Description

この発明は、暗号応用技術に関し、特に、入力データを明かすことなく認証符号を付加する技術に関する。

暗号化された数値を復元することなく特定の演算結果を得る方法として、秘密計算と呼ばれる方法がある（例えば、非特許文献１参照）。非特許文献１の方法では、３つの秘密計算装置に数値の断片を分散させるという暗号化を行い、３つの秘密計算装置が協調計算を行うことにより、数値を復元することなく、加減算、定数加算、乗算、定数倍、論理演算（否定、論理積、論理和、排他的論理和）、データ形式変換（整数、二進数）の結果を３つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。

秘密計算を行う場合に、認証符号を付加しておくことで改ざんへの耐性を持たせる方法として、非特許文献２の方法がある。

千田浩司、濱田浩気、五十嵐大、高橋克巳、"軽量検証可能3パーティ秘匿関数計算の再考"、CSS、2010年 Ivan Damgard, Marcel Keller, Enrique Larraia, Valerio Pastro, Peter Scholl, and Nigel P. Smart, "Practical covertly secure MPC for dishonest majority - or: Breaking the SPDZ limits", Computer Security - ESORICS 2013, vol. 8134 of Lecture Notes in Computer Science, pp. 1-18, 2013.

しかしながら、非特許文献２に記載された従来技術では、ランダムな認証符号付きの秘匿文を作るために非常に計算コストの大きいsomewhat準同型暗号を用いており、効率が悪かった。

この発明の目的は、このような点に鑑みて、ランダムな認証符号付きの秘匿文を効率よく作成する技術を提供することである。

上記の課題を解決するために、この発明の秘密認証符号付加装置は、Nを1以上の整数とし、xα=βを満たす値x, α, βの秘匿文([x], [α], [β])を生成する鍵生成部と、i=1, …, Nについて、ランダムな値a_iの秘匿文[a_i]を生成する秘匿文生成部と、i=1, …, Nについて、秘匿文[a_i]へ秘匿文[α]を乗じて認証符号[γ(a_i)]を生成する認証符号生成部と、次式を計算して検証値wの秘匿文[w]を生成する検証値生成部と、

検証値wが0と等しいか否かを判定する検証値判定部と、を含む。

この発明の秘密認証符号付加技術によれば、ランダムな認証符号付きの秘匿文を効率よく作成することができる。

図１は、秘密認証符号付加システムの機能構成を例示する図である。 図２は、第一実施形態に係る秘密認証符号付加装置の機能構成を例示する図である。 図３は、第一実施形態に係る秘密認証符号付加方法の処理フローを例示する図である。 図４は、第二実施形態に係る秘密認証符号付加装置の機能構成を例示する図である。 図５は、第二実施形態に係る秘密認証符号付加方法の処理フローを例示する図である。

実施形態の説明に先立ち、この明細書における表記方法および用語の定義について説明する。

＜表記方法＞
ある値aを暗号化や秘密分散などにより秘匿化した値をaの秘匿文と呼び、[a]と表記する。また、aを[a]の平文と呼ぶ。秘匿化が秘密分散である場合は、[a]により各パーティが持つ秘密分散の断片の集合を参照する。秘匿文[a]のうちi番目のパーティP_iが持つシェアを[a]_iで参照する。なお、シェアとは秘密分散された断片のことであり、パーティとは秘密計算を協調して行う各参加者のことである。

＜復元＞
秘匿文[a]から平文aを計算する処理を復元と呼び、次式のように記述する。

＜加算、減算、乗算、定数倍＞
秘匿文に対する加算、減算、乗算の各演算は、二つの値a, bの秘匿文[a], [b]を入力とし、それぞれa+b, a-b, abの計算結果d₁, d₂, d₃の秘匿文[d₁], [d₂], [d₃]を計算する。秘匿文に対する定数倍の演算は、値aの秘匿文[a]と平文cとを入力とし、caの計算結果d₄の秘匿文[d₄]を計算する。これらの演算の実行をそれぞれ次式のように記述する。

なお、誤解を招く恐れのない場合は、Add([a], [b]), Sub([a], [b]), Mul([a], [b]), CMul(c, [a])をそれぞれ[a]+[b], [a]-[b], [a][b], c[a]と略記する。

＜ランダムな秘匿文の生成＞
誰も知らないランダムな値rの秘匿文[r]を生成する処理を次式のように記述する。

＜コミットメント＞
コミットメントはコミットとオープンとの二つの処理からなる。コミットは送信者であるパーティがある値を他のパーティに秘密に提出する処理である。オープンはコミットした値をすべてのパーティに明らかにする処理である。送信者以外のパーティは値がオープンされるまでコミットされた値を知ることはできない。また、送信者がコミットした値は送信者も含めて誰も改ざんすることができない。

あるパーティP_iがある値vをコミットする処理を次式のように記述する。

τ_vはコミットした値vに紐づいたタグであり、すべてのパーティに送られる。

パーティP_iがタグτ_vに紐づいたコミットされた値vをオープンする処理を次式のように記述する。

この処理により、すべてのパーティがタグτ_vに紐づいたコミットされた値vを得る。

以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。

［第一実施形態］
第一実施形態の秘密認証符号付加システムは、図１に例示するように、n（≧2）台の秘密認証符号付加装置１₁, …, １_nを含む。この実施形態では、秘密認証符号付加装置１₁, …, １_nはそれぞれ通信網２へ接続される。通信網２は、秘密認証符号付加装置１₁, …, １_nそれぞれと通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットやLAN（Local Area Network）、WAN（Wide Area Network）などを用いることができる。なお、各装置は必ずしも通信網２を介してオンラインで通信可能である必要はない。例えば、秘密認証符号付加装置１_i（i∈{1, …, n}）へ入力する情報を磁気テープやUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体からオフラインで入力するように構成してもよい。

秘密認証符号付加装置１は、図２に示すように、例えば、入力部１１、鍵生成部１２、秘匿文生成部１３、認証符号生成部１４、検証値生成部１５、検証値判定部１６、および出力部１７を含む。検証値判定部１６は、例えば、復元部１６１および判定部１６２を含む。この秘密認証符号付加装置１が、図３に例示する各ステップの処理を行うことにより第一実施形態の秘密認証符号付加方法が実現される。

秘密認証符号付加装置１は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。秘密認証符号付加装置１は、例えば、中央演算処理装置の制御のもとで各処理を実行する。秘密認証符号付加装置１に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。秘密認証符号付加装置１の各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。

図３を参照して、第一実施形態の秘密認証符号付加方法の処理手続きを説明する。

ステップＳ１１において、入力部１１へ値Nが入力される。Nは1以上の整数であり、生成しようとする認証符号付き秘匿文の数を指定するパラメータである。

ステップＳ１２において、鍵生成部１２は、xα=βを満たす値x, α, βの秘匿文である認証符号鍵([x], [α], [β])を生成する。このような関係を満たす秘匿文の組を生成する方法は、例えば、非特許文献２に記載されている。もしくは、ランダムな値x, αの秘匿文[x], [α]を生成し、例えば、非特許文献１に記載されている秘密計算方法により、[β]←Mul([x], [α])を計算して、([x], [α], [β])の組を生成してもよい。認証符号鍵([x], [α], [β])は認証符号生成部１４へ送られる。

ステップＳ１３において、秘匿文生成部１３は、i=1, …, Nについて、式（１）を計算してランダムな値a_iの秘匿文[a_i]を生成する。N個の秘匿文[a₁], …, [a_N]は認証符号生成部１４へ送られる。

ステップＳ１４において、認証符号生成部１４は、i=1, …, Nについて、式（２）を計算して、秘匿文[a_i]へ秘匿文[α]を乗じた認証符号[γ(a_i)]を生成する。N個の認証符号[γ(a₁)], …, [γ(a_N)]は検証値生成部１５へ送られる。

ステップＳ１５において、検証値生成部１５は、秘匿文[a₁], …, [a_N], 認証符号[γ(a₁)], …, [γ(a_N)], 認証符号鍵[α], [β]を用いて、式（３）（４）を計算し、検証値wの秘匿文[w]を生成する。秘匿文[w]は検証値判定部１６へ送られる。秘匿文[a₁], …, [a_N], 認証符号[γ(a₁)], …, [γ(a_N)]は出力部１７へ送られる。

ステップＳ１６１〜１６２において、検証値判定部１６は、検証値wが0と等しいか否かを判定する。以下、具体的に、検証値判定部１６の処理を説明する。

ステップＳ１６１において、復元部１６１は、他のn-1台の秘密認証符号付加装置から秘匿文[w]のシェアを受信し、式（５）を計算して秘匿文[w]を復元し、検証値wを生成する。

ステップＳ１６２において、判定部１６２は、検証値wが0と等しいか否かを判定する。検証値wが0でなければ処理を終了する。検証値wが0であればステップＳ１７へ処理を進める。

ステップＳ１７において、出力部１７は、N個の認証符号付きの秘匿文([a₁], [γ(a₁)]), …, ([a_N], [γ(a_N)])を出力する。

この実施形態では、検証値生成部１５において、式（４）でランダムな値の秘匿文を乗じた秘匿文[w]を検証値として生成したが、式（３）で得られる秘匿文[z]を検証値として生成してもよい。ただし、秘匿文[z]を検証値とした場合、秘匿文[z]が0以外の値であった場合には、その値によって秘匿文[a_i]や認証符号鍵([x], [α], [β])を推測することが可能な場合がある。そのため、この実施形態では、式（４）においてランダムな値の秘匿文を乗ずることで、より安全性を高めている。

［第二実施形態］
第二実施形態の秘密認証符号付加方法は、コミットメントを利用して認証符号の検証を行う。これにより、検証値の改ざんを防止することができ、より確実に認証符号の正当性を確認することができる。この実施形態では、各秘匿文はnパーティの秘密分散により秘匿化されているものとする。そのような秘密分散としては、例えば、非特許文献１に記載されたしきい値秘密分散や、非特許文献２に記載された加法的秘密分散がある。

第二実施形態の検証値判定部１８は、図４に示すように、復元部１６１および判定部１６２に加えて、例えば、コミット部１６３およびオープン部１６４を含む。この検証値判定部１８を含む秘密認証符号付加装置が、図５に例示する各ステップの処理を行うことにより第二実施形態の秘密認証符号付加方法が実現される。

図５を参照して、第二実施形態の秘密認証符号付加方法の処理手続きを説明する。以下では、上述の第一実施形態との相違点を中心に説明する。以下では、i（∈{1, …, n}）番目の秘密認証符号付加装置１_iの処理を中心に説明する。

ステップＳ１６３において、秘密認証符号付加装置１_iのコミット部１６３は、式（６）を計算して、検証値wの秘匿文[w]のうち自身が保有するシェア[w]_iをコミットし、タグτ_iを生成する。これにより、他のn-1台の秘密認証符号付加装置１_j（j=1, …, n、j≠i）それぞれへタグτ_iが送られる。

同時に、他の秘密認証符号付加装置１_j（j=1, …, n、j≠i）それぞれが検証値[w]のシェア[w]_jをコミットし、タグτ_jを生成する。これにより、すべての秘密認証符号付加装置１₁, …, １_nが、自身のコミットしたタグと併せて、検証値[w]のすべてのシェア[w]₁, …, [w]_nに紐づいたタグτ₁, …, τ_nを持つことになる。

ステップＳ１６４において、秘密認証符号付加装置１_iのオープン部１６４は、式（７）を計算して、タグτ_iをオープンする。これにより、他のn-1台の秘密認証符号付加装置１_j（j=1, …, n、j≠i）すべてが検証値[w]のシェア[w]_iを得る。

同時に、他の秘密認証符号付加装置１_j（j=1, …, n、j≠i）それぞれがタグτ_jをオープンする。これにより、すべての秘密認証符号付加装置１₁, …, １_nが、自身の持つシェアと併せて、検証値[w]のすべてのシェア[w]₁,…,[w]_nを得ることができる。

ステップＳ１６１において、秘密認証符号付加装置１_iの復元部１６１は、式（８）を計算してシェア[w]₁, …, [w]_nを復元し、検証値wを生成する。

ステップＳ１６２において、秘密認証符号付加装置１_iの判定部１６２は、検証値wが0と等しいか否かを判定する。検証値wが0でなければ処理を終了する。検証値wが0であればステップＳ１７へ処理を進める。

第二実施形態では、検証値を判定する際にコミットメントを用いてシェアの送受信を行うため、検証値のシェアが漏洩したり、改ざんされたりすることを防止することができ、安全性を高めることができる。

上記のように構成することにより、この発明の秘密認証符号付加技術によれば、認証符号鍵([x], [α], [β])とN個の認証符号付き秘匿文([a_i], [γ(a_i)])とを生成することができる。生成した認証符号付き秘匿文を用いれば、例えば、非特許文献２に記載されたマルチパーティ計算で必要となる認証符号が付加された乱数の３つ組を生成することができる。

この発明では、ランダムな秘匿文に対して改ざんが行われるかもしれない乗算を使って認証符号の付加を行う。改ざんを想定しない乗算方式の多くでは乗算の入力に任意の値を加える改ざんが可能である。この発明の秘密認証符号付加技術は、乗算において各入力の平文に任意の値を加算させる改ざんに対して耐性がある。そのため、多くの改ざんを想定しない乗算を用いるマルチパーティ計算方式に対してこの発明を適用することにより、改ざん耐性を加えることができる。

この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。

［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。

この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。

また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。

このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。

また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

Claims (5)

1. Nを1以上の整数とし、
   xα=βを満たす値x, α, βの秘匿文([x], [α], [β])を生成する鍵生成部と、
   i=1, …, Nについて、ランダムな値a_iの秘匿文[a_i]を生成する秘匿文生成部と、
   i=1, …, Nについて、上記秘匿文[a_i]へ上記秘匿文[α]を乗じて認証符号[γ(a_i)]を生成する認証符号生成部と、
   次式を計算して検証値wの秘匿文[w]を生成する検証値生成部と、
   

   

   上記秘匿文[w]を復元して得た検証値wが0と等しいか否かを判定する検証値判定部と、
   を含む秘密認証符号付加装置。
2. 請求項１に記載の秘密認証符号付加装置であって、
   上記検証値生成部は、上記秘匿文[w]にランダム値の秘匿文を乗算したものにより上記秘匿文[w]を更新するものである、
   秘密認証符号付加装置。
3. 請求項１または２に記載の秘密認証符号付加装置であって、
   nは2以上の整数であり、秘匿文[x], [α], [β], [a_i]はnパーティの秘密分散による秘匿文であり、iは1以上n以下の任意の整数であり、
   上記検証値判定部は、
   上記秘匿文[w]のシェア[w]_iをコミットしたタグτ_iを生成するコミット部と、
   上記タグτ_iをオープンするオープン部と、
   他の秘密認証符号付加装置によりオープンされたシェア[w]_j（j=1, …, n、i≠j）を得、シェア[w]₁, …, [w]_nを復元して上記検証値wを得る復元部と、
   上記検証値wが0と等しいか否かを判定する判定部と、
   を含むものである、
   秘密認証符号付加装置。
4. Nを1以上の整数とし、
   鍵生成部が、xα=βを満たす値x, α, βの秘匿文([x], [α], [β])を生成する鍵生成ステップと、
   秘匿文生成部が、i=1, …, Nについて、ランダムな値a_iの秘匿文[a_i]を生成する秘匿文生成ステップと、
   認証符号生成部が、i=1, …, Nについて、上記秘匿文[a_i]へ上記秘匿文[α]を乗じて認証符号[γ(a_i)]を生成する認証符号生成ステップと、
   検証値生成部が、次式を計算して検証値wの秘匿文[w]を生成する検証値生成ステップと、
   

   

   検証値判定部が、上記秘匿文[w]を復元して得た検証値wが0と等しいか否かを判定する検証値判定ステップと、
   を含む秘密認証符号付加方法。
5. 請求項１から３のいずれかに記載の秘密認証符号付加装置の各部としてコンピュータを機能させるためのプログラム。

Images