(57)【要約】  正確且つ高速に所定の処理を秘密演算にて実行する情報処理装置を提供する。情報処理装置は、秘密分散された第１及び第２のシェアの差分値の絶対値が自然数ｔ以下の場合、第１及び第２のシェアの差分値を計算する。さらに、情報処理装置は、第１及び第２のシェアに関する大小比較を、当該差分値に関する最下位ビットから第ｍビット（ｍは自然数）のビット分解を用いて行う。
2020075273.tif 000002
【特許請求の範囲】
【請求項１】
秘密分散された第１及び第２のシェアの差分値の絶対値が自然数ｔ以下の場合、
前記第１及び第２のシェアの差分値を計算し、前記第１及び第２のシェアに関する大小比較を、前記差分値に関する最下位ビットから第ｍビット（ｍは自然数）のビット分解を用いて行う、情報処理装置。
【請求項２】
前記ビット分解された差分値の第ｍビットの値に応じて前記第１及び第２のシェアの大小を判定する、請求項１に記載の情報処理装置。
【請求項３】
前記第１及び第２のシェアは２ｎを法とする剰余類環に含まれ（ｎは自然数）、前記自然数ｍは、２ｍ−１≦ｔ＜２ｍ≦２ｎ−１
により定まる、請求項１又は２に記載の情報処理装置。
【請求項４】
前記第ｍビットまでのビット分解を使用する制限付き大小比較を用いて、２つの文字列の編集距離を計算する、請求項１乃至３のいずれか一項に記載の情報処理装置。
【請求項５】
前記編集距離の算出に使用するＤＰ（Dynamic Programming）マトリクスにおけるスコア算出対象の要素の上と左に位置する要素それぞれのスコアに関する対角線上の大小比較を前記制限付き大小比較により行う、請求項４に記載の情報処理装置。
【請求項６】
前記対角線上の大小比較により小さいと判定された要素のスコアと、前記スコア算出対象の要素の左上に位置する要素のスコアと、に関する第１の大小比較を前記制限付き大小比較により行う、請求項５に記載の情報処理装置。
【請求項７】
前記対角線上の大小比較に用いるビット分解を最下位ビットから順に第２ビットまで行い、
前記第１の大小比較に用いるビット分解を最下位ビットから第１ビットまで行う、請求項６に記載の情報処理装置。
【請求項８】
前記対角線上の大小比較に要する通信コストは１２ビットの通信量、２回の通信ラウンド数であり、前記第１の大小比較に要する通信コストは６ビットの通信量、１回の通信ラウンド数である、請求項６又は７に記載の情報処理装置。
【請求項９】
前記編集距離の算出に使用するＤＰ（Dynamic Programming）マトリクスにおけるスコア算出対象の要素の上と左上に位置する要素それぞれのスコアに関する水平方向の大小比較と、前記スコア算出対象の要素の左上と左に位置する要素それぞれのスコアに関する垂直方向の大小比較と、を前記制限付き大小比較により行う、請求項４に記載の情報処理装置。
【請求項１０】
前記水平方向の大小比較により小さいと判定された要素のスコアと、前記垂直方向の大小比較により小さいと判定された要素のスコアと、に関する第２の大小比較を前記制限付き大小比較により行う、請求項９に記載の情報処理装置。
【請求項１１】
前記水平方向、前記垂直方向及び前記第２の大小比較に用いるビット分解を最下位ビットから第１ビットまで行う、請求項１０に記載の情報処理装置。
【請求項１２】
前記水平方向、前記垂直方向及び前記第２の大小比較に要する通信コストはそれぞれ６ビットの通信量、１回の通信ラウンド数である、請求項１０又は１１に記載の情報処理装置。
【請求項１３】
情報処理装置において、
秘密分散された第１及び第２のシェアの差分値の絶対値が自然数ｔ以下の場合、
前記第１及び第２のシェアの差分値を計算するステップと、
前記第１及び第２のシェアに関する大小比較を、前記差分値に関する最下位ビットから第ｍビット（ｍは自然数）のビット分解を用いて行うステップと、
を含む、秘密計算方法。
【請求項１４】
コンピュータに、
秘密分散された第１及び第２のシェアの差分値の絶対値が自然数ｔ以下の場合、
前記第１及び第２のシェアの差分値を計算する処理と、
前記第１及び第２のシェアに関する大小比較を、前記差分値に関する最下位ビットから第ｍビット（ｍは自然数）のビット分解を用いて行う処理と、
を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、秘密計算方法及びプログラムに関する。
【背景技術】
【０００２】
近年、秘密計算（マルチパーティ計算；ＭＰＣ（Multi Party Computation））に関する研究開発が盛んに行われている。秘密計算では、入力データを秘匿したまま所定の処理を実行し、結果を得ることができる。【０００３】
秘密計算プロトコルは大きく２つの種類に大別される。第１の方式は、特定の計算に限って実行可能な秘密計算プロトコルである。第２の方式は、任意の計算が実行可能な秘密計算プロトコルである。また、第２の方式には種々の方式が存在し、方式間で通信量（データ量）と通信ラウンド数に関してそのコストにおけるトレードオフが成立する。つまり、通信量が少ない代わりに通信回数が多い方式や通信量は多いが通信回数が少ない方式が存在する。【０００４】
上述のように、秘密計算では、入力データを秘密にしたまま任意の処理を実行できるため、個人情報の保護が強く求められる分野への秘密計算の適用が検討されている。例えば、秘密計算の適用分野として医療分野が挙げられる。具体的には、ゲノム情報を秘匿にしつつ、ゲノム医療に関する計算を行うことが検討されている。例えば、ゲノム医療に関する計算として、２つのＤＮＡ（Deoxyribo Nucleic Acid）の編集距離の計算がある。【０００５】
非特許文献１には、ＧＣ（Garbled Circuit）と称される技術が開示されている。ＧＣとは、２者間秘密計算の代表的な方式であり、暗号化された回路を生成することで任意の論理回路計算を実現する。当該秘密計算の方式は、実行時の通信ラウンド数が定数回に抑制される一方で、通信量は大きいという性質を有する。【０００６】
非特許文献２〜４には、上記ＧＣ（Garbled Circuit）を用いた編集距離の計算方法が開示されている。また、非特許文献５には、ＤＰ（Dynamic Programming）マトリクスを用いた編集距離のアルゴリズムが開示されている。なお、後述するように、ＤＰマトリクスとは、編集距離の計算過程で使用される行列（テーブル）である。また、非特許文献６には、編集距離の計算において、挿入、削除、置換コストを「１」とした際に、隣り合うマス同士のスコアの差は１、０、−１のいずれかとなることが開示されている。【０００７】
非特許文献２では、編集距離計算時に必要なスコアの計算を全てＧＣを用いて行う方式と、ＤＰマトリクスを分割して計算する方式と、が提案されている。非特許文献２には、後者のＤＰマトリクス分割方式により、５００文字同士の距離計算を１時間以内に実行可能であると記載されている。【０００８】
非特許文献３には、編集距離計算回路の最適化とＧＣの効率を向上する技術が開示されている。非特許文献３には、１文字８ビットで１００文字同士の編集距離計算を行った際、非特許文献２における全ての計算をＧＣにより行う場合には９２．４秒必要であったものが、非特許文献３が提案する方式では４．１秒で完了した旨が記載されている。【０００９】
非特許文献４は、ＧＣを用いつつ、特定のパーティ（秘密計算サーバ）に対して計算する関数を隠すことができる技術を開示している。つまり、非特許文献４に開示された技術を用いることで、特定のパーティが編集距離を計算しているのか他の計算を行っているかを隠蔽することができる。当該文献による技術では、１文字２ビットの１００文字同士の編集距離計算にて、事前計算を除いた実行時間として６．９７秒要する。【００１０】
非特許文献７には、ＦＨＥ（Fully Homomorphic Encryption）と称される技術が開示されている。ＦＨＥとは、暗号文をEnc(m)とするとき、平文空間内の任意の平文m0、m1に対して、Enc(m0)*Enc(m1) = Enc(m0*m1)、Enc(m0)+Enc(m1) = Enc(m0+m1)が成り立つ暗号方式である。なお、「*」、「+」はそれぞれ、乗算演算子及び加算演算子を示す。ＦＨＥでは、上記暗号文同士の演算を１台のサーバ上で実行可能なため、当該計算には通信コストが発生しない。しかし、ＦＨＥの方式には暗号文長が非常に大きいという性質がある。【００１１】
非特許文献８には、上記ＦＨＥを用いた編集距離の計算方法が開示されている。非特許文献８では、１文字をビット列と捉え、各ビットごとに暗号文を生成する。なお、非特許文献８では編集距離の対象としてＤＮＡ配列を想定しているので、１文字は２ビット列となる。非特許文献８の技術では、８文字同士の編集距離計算を６８２配列分行うと５時間１３分必要となる。【００１２】
非特許文献９及び非特許文献１０は、秘密分散ベース３者間秘密計算を開示する。秘密分散ベース秘密計算とは、各入力を参加者（パーティ；秘密計算サーバ）に分散した状態で回路の各ゲートを計算していく方式である。また、非特許文献１１及び非特許文献１２によれば、算術回路、論理回路ともに秘密分散ベース計算として計算できる。秘密分散ベース秘密計算には、通信量は小さいが乗算ゲートや論理積ゲートを通過する回路の深さに比例して通信ラウンド数が増加するという性質がある。【００１３】
非特許文献９では、非特許文献１２に開示された技術を用いて、編集距離の計算を行っている。非特許文献９における当該編集距離の計算では、１文字２ビットの１００文字同士の編集距離計算に対し秒間１４５回の実行を実現している。なお、非特許文献１２の回路には不正検知機能が備わっており、上述の非特許文献２や非特許文献３、後述する非特許文献１０〜１２に開示された技術よりも高い安全性を有する。【００１４】
非特許文献１３〜１５は、編集距離の近似値を計算する技術を開示する。非特許文献１３〜１５では、ＤＮＡ塩基配列に関する編集距離計算に限定することで、精度を落とした計算（Ａｐｐｒｏｘｉｍａｔｅな計算）を実現している。その結果、秘密計算の性能向上が達成されている。【００１５】
非特許文献１３は、ヒトゲノムを対象とした編集距離の近似値計算を提案している。非特許文献１３では、編集距離の計算対象をヒトゲノムに限定することで、リファレンスゲノムという既知の配列を使用する。具体的には、リファレンスゲノムと編集距離を計算する対象である２配列とで、それぞれ１文字ごとに挿入、削除、置換の操作を要素とする集合が生成される。ここで、リファレンスゲノムをＲ、編集距離を計算する対象である２配列をＡ、Ｂとするとき、ＲとＡから生成された集合をＡ’、ＲとＢから生成された集合をＢ’と表記する。非特許文献１３では、
2020075273.tif 000003
を編集距離として計算している。より具体的には、非特許文献１３では、
2020075273.tif 000004
をＧＣにより計算している。
なお、非特許文献１３では、テストケースにおける９０％において計算した編集距離について相対誤差が１％に抑えられるよう正確に編集距離を計算した場合、配列のペア１０個分に対して１９６．１秒要する。【００１６】
非特許文献１４は、非特許文献１６に開示されたＰＳＩ（Private Set Intersection）を用いた編集距離の計算と、当該計算にさらにＧＣを用いて編集距離を計算する方式を提案している。なお、ＰＳＩとは、２つの集合を入力とし、入力を隠したまま共通する要素に関する情報だけを得るプロトコルである。【００１７】
非特許文献１４に開示されたＰＳＩを用いる方式では、「ｓｈｉｎｇｌｉｎｇ」という文字列を固定長の文字に分割し、当該分割された文字の集合をクエリ文字列とデータベース側の文字列とで生成する。非特許文献１４では、それぞれの集合の共通部分を編集距離の近似値として計算する。その際、ＰＳＩが用いられている。【００１８】
非特許文献１４に開示されたＰＳＩとＧＣを用いる方式では、非特許文献１７に開示されたBanded Alignmentという編集距離の計算方法をＧＣで計算している。Banded Alignmentとは、ＤＮＡ配列のような配列同士の長さや文字列が非常に近いものとして扱える場合に使用できる編集距離の近似値計算の１つである。非特許文献１４では、クライアントがクエリした配列に対し、上述の方式（ＰＳＩを用いる方式）によりデータベース中の配列について編集距離を求めている。その後、値が小さい上位ｔ（＝ｃｋ、Ｃ≧１）個の配列が選択される。さらに、ｔ個の配列からＧＣによりBanded Alignmentを行い、ｋ個の配列を選択し、レスポンスとしてクライアントに送られる。当該方式では、配列の長さが９０００〜１００００である２０００レコードのデータベースに５０回クエリし、上記１０個の配列を返答するという実証実験を行ったところ、事前計算に１８１秒、クエリ発行からの計算時間に７３０秒要した。【００１９】
非特許文献１５は、ＧＣを基礎とした編集距離の近似値計算を開示する。非特許文献１５は、文字列を分割し、各ブロックごとに編集距離を計算する。さらに、非特許文献１５では、上記計算された編集距離の総和を文字列全体の編集距離として捉えることで、編集距離のコストを削減している。より詳細には、編集距離の計算コストが、0(|x|・|y|)から0(|x|+|y|) に削減される。なお、|x|、|y| は文字列x、yそれぞれの文字列長を示す。また、非特許文献１５では、編集距離の計算対象をヒトゲノムとすることで、リファレンスゲノムを用いて計算対象の配列を各ブロックに分割し、ブロックごとの編集距離の計算をより効率化している。なお、非特許文献１５では、ＺＮＦ７１７というレコード数５００、各レコードの長さ３４７０のデータセットに対し、クエリした配列との編集距離が小さい上位５つのレコードを応答として返すという実験を１００回繰り返し行っている。当該実験では、サーバの事前計算に１１．８６秒、クエリ時のサーバ側の実行時間に１．２２秒、クライアント側の実行時間に０．４８秒を要している。また、アルゴリズムが返した配列数の内、正しい出力だったものの数をｐ、誤った出力だった出力の数をｎとしたときｐ／（ｐ＋ｎ）が精度として扱われる。この場合、非特許文献１５では、実験結果としての精度は９８．８５％であると記載されている。
【先行技術文献】
【非特許文献】
【００２０】
【非特許文献１】Andrew C. Yao、"Protocols for secure computations."、1982、In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science(SFCS '82). IEEE Computer Society, Washington, DC, USA, 160-164.
【非特許文献２】Jha, S., Kruger, L., & Shmatikov, V、"Towards practical privacy for genomic computation"、2008、In Security and Privacy, 2008. SP 2008. IEEE Symposium on (pp. 216-230). IEEE.
【非特許文献３】Huang, Y., Evans, D., Katz, J., & Malka, L、"Faster Secure Two-Party Computation Using Garbled Circuits."、2011、In USENIX Security Symposium (Vol.201, No. 1).
【非特許文献４】Naveed, M., Agrawal, S., Prabhakaran, M., Wang, X., Ayday, E., Hubaux, J., Gunter, C.A.、"Controlled functional encryption."、2014、In: ACM CCS, pp. 1280-1291 (2014)
【非特許文献５】Wagner, R. A., & Fischer, M. J.、"The string-to-string correction problem"、1974、Journal of the ACM (JACM)、21(1)、168-173
【非特許文献６】Myers, G.、"A fast bit-vector algorithm for approximate string matching based on dynamic programming"、1999、Journal of the ACM (JACM)、46(3)、395-415.
【非特許文献７】Gentry C., Halevi S., Smart N.P.、"Homomorphic Evaluation of the AES Circuit."、2012、In: Safavi-Naini R., Canetti R. (eds) Advances in Cryptology - CRYPTO 2012. CRYPTO 2012. Lecture Notes in Computer Science, vol 7417. Springer, Berlin, Heidelberg
【非特許文献８】Cheon, J. H., Kim, M., & Lauter, K.、"Homomorphic computation of edit distance."、2015、In International Conference on Financial Cryptography and Data Security (pp. 194-212). Springer Berlin Heidelberg.
【非特許文献９】Hikaru Tsuchida, Toshinori Araki, Kazuma Ohara and Furukawa Jun、"不正検知可能なマルチパーティ計算による生体情報と遺伝子情報の保護"、2018 Symposium on Cryptography and Information Security, Niigata, Japan, 2018, 2A1-5.
【非特許文献１０】Kazuma Ohara, Toshinori Araki, Hikaru Tsuchida and Furukawa Jun、"異なるサイズの環が混在する不正検知可能なマルチパーティ計算"、2018 Symposium on Cryptography and Information Security, Niigata, Japan, 2018, 2A1-4.
【非特許文献１１】Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara、"High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority."、2016、In  Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security  (CCS '16). ACM, New York, NY, USA, 805-817.
【非特許文献１２】T. Araki  et al.、"Optimized Honest-Majority MPC for Malicious Adversaries − Breaking the 1 Billion-Gate Per Second Barrier"、2017、IEEE Symposium on Security and Privacy (SP), San Jose, California, USA, 2017, pp. 843-862.
【非特許文献１３】Xiao Shaun Wang, Yan Huang, Yongan Zhao, Haixu Tang, XiaoFeng Wang, and Diyue Bu.、"Efficient Genome-Wide, Privacy-Preserving Similar Patient Query based on Private Edit Distance."、2015、In  Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security  (CCS '15). ACM, New York, NY, USA, 492-503.
【非特許文献１４】Aziz, Md Momin Al, Dima Alhadidi and Noman Mohammed、"Secure approximation of edit distance on genomic data."、2017、BMC Medical Genomics  (2017).
【非特許文献１５】Asharov, Gilad, Shai Halevi, Yehuda Lindell and Tal Rabin.、"Privacy-Preserving Search of Similar Patients in Genomic Data."、2017、IACR Cryptology ePrint Archive  2017 (2017): 144.
【非特許文献１６】Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner.、"Phasing: private set intersection using permutation-based hashing."、2015、In  Proceedings of the 24th USENIX Conference on Security Symposium  (SEC'15), Jaeyeon Jung (Ed.). USENIX Association, Berkeley, CA, USA, 515-530.
【非特許文献１７】Fickett JW、"Fast optimal alignment."、Nucleic Acids Research、1984;12(1 Pt 1):175-179.
【発明の概要】
【発明が解決しようとする課題】
【００２１】
上述のように、秘密計算には入力データを秘密にしつつ、所定の演算結果を得ることができるという利点がある。一方で、秘密分散された入力データ（シェア情報）の乗算にはサーバ間の通信が必要となり演算結果を得るまでの時間が比較的長いという性質がある。このような秘密計算の性質により、許容できない程の長い処理時間が必要であったり、演算精度を落とす必要あったりする。上記例示した編集距離の計算では、処理性能（処理速度）向上のため精度を落として計算するといった対応がなされている。【００２２】
しかし、ＤＮＡ配列の編集距離を計算といったアプリケーションでは、精度を落として計算した結果の価値は低いものと扱われる可能性がある。即ち、精度を落とした演算結果（精度の低い編集距離）は、ユーザ（例えば、医療関係者）にとって不適切なデータとなる可能性がある。一方で、正確な演算結果（精度の高い編集距離）を得るまでの時間があまりに長すぎてもユーザの業務に支障をきたすことになる。この点、上記説明した非特許文献２等の技術では、処理性能が低い、又は、処理性能を向上させるため演算の精度を犠牲にしているといった問題がある。このように、既存技術の多くは、かなりの計算時間を要するか、正確な距離計算を犠牲にすることで計算時間を短縮している。【００２３】
本発明は、正確且つ高速に所定の処理を秘密演算にて実行することに寄与する、情報処理装置、秘密計算方法及びプログラムを提供することを主たる目的とする。
【課題を解決するための手段】
【００２４】
本発明乃至開示の第１の視点によれば、秘密分散された第１及び第２のシェアの差分値の絶対値が自然数ｔ以下の場合、前記第１及び第２のシェアの差分値を計算し、前記第１及び第２のシェアに関する大小比較を、前記差分値に関する最下位ビットから第ｍビット（ｍは自然数）のビット分解を用いて行う、情報処理装置が提供される。【００２５】
本発明乃至開示の第２の視点によれば、情報処理装置において、秘密分散された第１及び第２のシェアの差分値の絶対値が自然数ｔ以下の場合、前記第１及び第２のシェアの差分値を計算するステップと、前記第１及び第２のシェアに関する大小比較を、前記差分値に関する最下位ビットから第ｍビット（ｍは自然数）のビット分解を用いて行うステップと、を含む、秘密計算方法が提供される。【００２６】
本発明乃至開示の第３の視点によれば、コンピュータに、秘密分散された第１及び第２のシェアの差分値の絶対値が自然数ｔ以下の場合、前記第１及び第２のシェアの差分値を計算する処理と、前記第１及び第２のシェアに関する大小比較を、前記差分値に関する最下位ビットから第ｍビット（ｍは自然数）のビット分解を用いて行う処理と、を実行させるプログラムが提供される。
なお、このプログラムは、コンピュータが読み取り可能な記憶媒体に記録することができる。記憶媒体は、半導体メモリ、ハードディスク、磁気記録媒体、光記録媒体等の非トランジェント（non-transient）なものとすることができる。本発明は、コンピュータプログラム製品として具現することも可能である。
【発明の効果】
【００２７】
本発明乃至開示の各視点によれば、正確且つ高速に所定の処理を秘密演算にて実行することに寄与する、情報処理装置、秘密計算方法及びプログラムが、提供される。
【図面の簡単な説明】
【００２８】
【図１】一実施形態の概要を説明するための図である。
【図２】第１の実施形態に係る秘密計算システムの概略構成の一例を示す図である。
【図３】編集距離の算出を説明するための図である。
【図４】第１の実施形態に係る制御装置の処理構成の一例を示す図である。
【図５】第１の実施形態に係る秘密計算サーバの処理構成の一例を示す図である。
【図６】秘密計算実行部の動作の一例を示すフローチャートである。
【図７】秘密計算実行部によるスコア算出動作の一例を示すフローチャートである。
【図８】秘密計算実行部の動作を説明するための図である。
【図９】秘密計算サーバのハードウェア構成の一例を示す図である。
【図１０】第２の実施形態に係る秘密計算実行部によるスコア算出動作の一例を示すフローチャートである。
【図１１】種々の方式による編集距離算出に要する通信コストの一例を示す図である。
【図１２】秘密計算システムの別の構成の一例を示す図である。
【発明を実施するための形態】
【００２９】
初めに、一実施形態の概要について説明する。なお、この概要に付記した図面参照符号は、理解を助けるための一例として各要素に便宜上付記したものであり、この概要の記載はなんらの限定を意図するものではない。また、各図におけるブロック間の接続線は、双方向及び単方向の双方を含む。一方向矢印については、主たる信号（データ）の流れを模式的に示すものであり、双方向性を排除するものではない。さらに、本願開示に示す回路図、ブロック図、内部構成図、接続図などにおいて、明示は省略するが、入力ポート及び出力ポートが各接続線の入力端及び出力端のそれぞれに存在する。入出力インターフェイスも同様である。
【００３０】
図１に示す一実施形態に係る情報処理装置１００は、秘密分散された第１及び第２のシェアの差分値の絶対値が自然数ｔ以下の場合、第１及び第２のシェアの差分値を計算する。さらに、情報処理装置１００は、第１及び第２のシェアに関する大小比較を、当該差分値に関する最下位ビットから第ｍビット（ｍは自然数）のビット分解を用いて行う。
【００３１】
詳細については後述するが、秘密分散されたシェアの大小比較は数値演算よりも論理演算による処理の方が容易に結果が得られる。そのため、上記情報処理装置１００は、秘密分散されたシェアに関する大小比較を行う際、２つのシェアの差分値を２進数にて変換する。但し、大小比較の対象となる情報は秘密分散された情報（数値）であるので、当該秘密分散された数値を２進数に変換するには、非特許文献１０等に開示された「ビット分解」と称される技術が必要となる。当該ビット分解は、秘密分散された値のビット値（２進数表記における各桁の値）を最下位ビットから順に最上位ビットまで行う。ビット分解について、本願の発明者らが鋭意検討した結果、所定の条件が成立する場合に、全てのビットに関して値を算出しなくとも、２つのシェアの大小比較（差分値の正負）が判定できるという知見を得た。具体的には、２つのシェアの差分値の絶対値が所定の数（上記自然数ｔ）以下であることが予め判明しているのであれば、当該差分値に関するビット分解を最上位ビットまで実行する必要がないことが明らかとなった。詳細については後述するが、例えば、２つの文字列の編集距離において上記条件が成立する。情報処理装置１００は、２つのシェアに関する大小比較を行う際、通信コストが比較的大きいビット分解を必要最低限のビット（上記第ｍビット）までの分解に制限することで、秘密計算による処理の高速化を実現する。また、上記ビット分解を途中のビットまでに制限したとしても大小比較の結果に影響は与えないので、当該大小比較を含む処理結果の精度が低下することもない。
【００３２】
以下に具体的な実施の形態について、図面を参照してさらに詳しく説明する。なお、各実施形態において同一構成要素には同一の符号を付し、その説明を省略する。
【００３３】
［第１の実施形態］
第１の実施形態について、図面を用いてより詳細に説明する。
【００３４】
上述のように、秘密計算の適用領域として医療分野がある。例えば、編集距離計算がサブルーチンとして用いられる処理として、データベースのあいまい検索が挙げられる。この場合、医療機関の限られた人間だけがデータベースにアクセスすると仮定すると、スループットよりもレイテンシが重視される。またゲノム医療の場合は、人種や地域の違いに起因し世界各国にて管理されているゲノム情報を用いることが想定される。しかし、欧州にて施行が始まった一般データ保護規則等を考慮すると、ゲノム情報のような個人情報を国外に移転させることはより一層困難な状況になると想定される。このため、各国のサーバ間でゲノム情報を用いた秘密計算を行うことが考えられる。この場合、各国に配置されたサーバ間で通信を行うため、通信遅延が増大する可能性が高い。
【００３５】
多くの秘密計算プロトコルでは実装上、ＴＣＰ（Transmission Control Protocol）通信を必要とする。ＴＣＰ通信では、通信相手からの応答が得られないと次のパケットを送ることができないという性質がある。このため通信帯域を大きくしても、通信遅延が大きい場合には、期待ほどの性能向上が得られないことがあり得る。従って、特に通信ラウンド数を削減する方法が必要となる。
【００３６】
第１の実施形態では、秘密計算を用いた正確な編集距離計算を高速に行うために、通信ラウンド数に着目し当該通信ラウンド数の改善を実現する秘密計算システムを提供する。第１の実施形態に係る秘密計算システムにより、秘密計算を用いた正確な編集距離計算と、編集距離計算をサブルーチンとして用いる上位の処理に関する性能改善効果が期待される。
【００３７】
［システム構成］
図２は、第１の実施形態に係る秘密計算システムの概略構成の一例を示す図である。図２を参照すると、秘密計算システムは、制御装置１０と、複数の秘密計算サーバ２０−１〜２０−３と、を含んで構成される。図２に示す各装置は相互に接続され、互いにデータの送受信が可能に構成されている。なお、以降の説明において、秘密計算サーバ２０−１〜２０−３を区別する特段の理由がない場合には、単に「秘密計算サーバ２０」と表記する。また、図２に示すシステム構成は例示であって、秘密計算サーバ２０等の数を限定する趣旨ではないことは勿論である。
【００３８】
制御装置１０は、秘密計算サーバ２０を制御する装置である。具体的には、制御装置１０は、各秘密計算サーバ２０に対するデータの入出力を制御する。
【００３９】
秘密計算サーバ２０は、秘密計算を実行するサーバである。秘密計算サーバ２０は、制御装置１０から入力データ（秘密分散するデータ）を受け取る。各秘密計算サーバ２０は、他のサーバと協働し上記入力データを用いた所定の処理を実行する。秘密計算サーバ２０は、計算結果を制御装置１０に送信する。あるいは、秘密計算サーバ２０は、計算結果を制御装置１０とは異なる外部装置に送信してもよい。
【００４０】
図２に示す秘密計算システムは、２つのＤＮＡ配列を対象とした編集距離を計算する。制御装置１０は、編集距離の計算対象となる２つのＤＮＡ配列を秘密分散し、秘密分散されたデータを各秘密計算サーバ２０に送信する。
【００４１】
各秘密計算サーバ２０は、入力データ（シェア情報；秘密分散されたＤＮＡ配列）を取得し、編集距離の算出に関する秘密計算を実行する。各秘密計算サーバ２０における秘密計算の実行が終了すると、制御装置１０は、各秘密計算サーバ２０から計算結果を収集し、計算結果の復号を行う。なお、第１の実施形態では、ＤＮＡ配列を編集距離の計算対象とするが、他の文字列を編集距離の計算対象としても良いことは勿論である。
【００４２】
［編集距離の計算］
初めに、編集距離の算出について概説する。
【００４３】
編集距離の算出には、非特許文献５に記載されたＷＦ（Ｗａｇｎｅｒ−Ｆｉｓｃｈｅｒ）法を用いることができる。以下、Ｗａｇｎｅｒ−Ｆｉｓｃｈｅｒ法による編集距離の算出を具体的に説明する。その際、対象とする文字列は、ｐ＝（ｐ１、ｐ２、ｐ３）とｓ＝（ｓ１、ｓ２、ｓ３）とする。
【００４４】
初めに、ＤＰマトリクスが生成される。上記の例では、図３（ａ）に示すようなＤＰマトリクスが生成される。図３（ａ）に示すように、比較対象の文字列に含まれる文字数がｋ（ｋは自然数、以下同じ）であれば、ｋ＋１行ｋ＋１列のＤＰマトリクスが生成される。上記の例では、２つの文字列に含まれる文字数が「３」であるので、４行４列のＤＰマトリクスが生成される。
【００４５】
次に、ＤＰマトリクスのスコアが初期化される。ＤＰマトリクスの各要素に対応する値（スコア）をＤｉ、ｊと表記する。ここで、ｉはＤＰマトリクスの行方向のインデックスであり、ｊはＤＰマトリクスの列方向のインデックスである。ＤＰマトリクスのスコア初期化は、Ｄｉ、０＝ｉ、Ｄ０、ｊ＝ｊと設定することで行われる（図３（ｂ）参照）。
【００４６】
次に、ＤＰマトリクスにおける各要素のスコアが計算される。スコア算出にはスコア算出対象の要素を基準とする３つの要素に対応した値が計算される。当該３つの計算値のうち、最小値が計算対象のスコアとなる。
【００４７】
第１の計算値は、スコア算出対象となっている要素の１つ上の要素（列方向のインデックスが１小さい要素）のスコアに「１」を加算した値である。
【００４８】
第２の計算値は、スコア算出対象となっている要素の１つ左の要素（行方向のインデックスが１小さい要素）のスコアに「１」を加算した値である。
【００４９】
第３の計算値は、スコア算出対象となっている要素の左上の要素（列方向、行方向それぞれのインデックスが１小さい要素）のスコアに「Ｃ」を加算した値である。ここで、スコア算出対象の要素に対応する文字（行方向と縦方向の文字）が一致する場合には、Ｃ＝０とする。スコア算出対象の要素に対応する文字（行方向と縦方向の文字）が不一致の場合には、Ｃ＝１とする。
【００５０】
例えば、比較対象の文字列を「ＡＧＣ」と「ＡＴＣ」とすれば、初期化後のＤＰマトリクスは図３（ｃ）のようになる。これらの文字列に対して、上記３つの計算値における最小値をスコアに設定する計算を繰り返すと、図３（ｄ）の結果が得られる。編集距離は、ＤＰマトリクスの右下（Ｄ３、３）のスコアである。図３（ｃ）及び（ｄ）の例では、編集距離は「１」となる。
【００５１】
第１の実施形態に係る秘密計算システムでは、上記のような編集距離の計算を秘密計算にて行う。
【００５２】
［記法］
次に、記法の定義を行う。
【００５３】
２を法とする剰余類環を
2020075273.tif 000005
と表記する。
【００５４】
２ｎを法とする剰余類環を
2020075273.tif 000006
と表記する（ｎは自然数、以下同じ）。
【００５５】
２を法とする剰余類環に属するシェア
2020075273.tif 000007
を［ｗ］と表記する。
【００５６】
２ｎを法とする剰余類環に属するシェア
2020075273.tif 000008
を［ν］ｎと表記する。
【００５７】
なお、［ｗ］はビットのシェアとも称され、［ν］ｎはリングのシェアとも称される。
【００５８】
以下の４つの式を満たすようなビットのシェア、リングのシェアに対する加算演算子を「＋」、乗算演算子を「・」と表記する。
【００５９】
2020075273.tif 000009
【００６０】
上記４つの等式のうち、１番目、３番目及び４番目の等式に関しては各秘密計算サーバ２０が単独で計算可能である（ローカルで計算可能；他のサーバとの通信が不要）。一方、２番目の等式に関しては、その計算のために他の秘密計算サーバ２０と通信が必要となる。例えば、非特許文献１１に開示された秘密計算方法では、３ｎビットの通信量、１回の通信ラウンド数を要する。
【００６１】
上記４つの等式における左辺は、それぞれのシェアを入力とする演算子に対応する秘密計算を意味する。以降の説明では、理解の容易のために、加法と乗法に関する秘密計算は上述の演算子（＋、・）による表記を用いる。
【００６２】
［ビット分解］
第１の実施形態に係る秘密計算システムでは、非特許文献１０に開示された「ビット分解」と称される計算を編集距離算出に用いる。以下、上記非特許文献１０に開示されたビット分解の概略を説明する。
【００６３】
ビット分解とは、数値計算向けの分散情報を論理演算向けの分散情報に変換するための処理である。即ち、ビット分解とは、秘密計算プロトコルにおいて、秘密分散された値を１０進数のシェアから２進数のシェアに変換する処理である。例えば、法を８（２３）として整数「５」が３台の秘密計算サーバ２０に分散されている場合を考える。この場合、例えば、「５」はｒ１＝１、ｒ２＝２、ｒ３＝２のように分散され、秘密計算サーバ２０−１が（ｒ１、ｒ２）を記憶し、秘密計算サーバ２０−２が（ｒ２、ｒ３）を記憶し、秘密計算サーバ２０−３が（ｒ３、ｒ１）を記憶する。ビット分解を用いると、これらの分散情報から数値「５」の２進数表記である、「０１０１」の各ビットに対する分散情報が得られる。
【００６４】
具体的には、整数「５」に対してビット分解が実行されると、各秘密計算サーバ２０は、例えば、以下のような情報を所有することになる。
＜秘密計算サーバ２０−１＞
第０ビット：（ｒ１、ｒ２）＝（１、１）
第１ビット：（ｒ１、ｒ２）＝（０、１）
第２ビット：（ｒ１、ｒ２）＝（１、０）
第３ビット：（ｒ１、ｒ２）＝（０、０）
＜秘密計算サーバ２０−２＞
第０ビット：（ｒ２、ｒ３）＝（１、１）
第１ビット：（ｒ２、ｒ３）＝（１、１）
第２ビット：（ｒ２、ｒ３）＝（０、０）
第３ビット：（ｒ２、ｒ３）＝（０、０）
＜秘密計算サーバ２０−３＞
第０ビット：（ｒ３、ｒ１）＝（１、１）
第１ビット：（ｒ３、ｒ１）＝（１、０）
第２ビット：（ｒ３、ｒ１）＝（０、０）
第３ビット：（ｒ３、ｒ１）＝（０、０）
【００６５】
上記ビット分解の結果に関し、第０ビット（最下位ビット）に着目すると、ｒ１＝ｒ２＝ｒ３＝１であるので、ｒ１＋ｒ２＋ｒ３  ｍｏｄ  ２＝１となり、５の２進数表記の最下位ビットの値に一致する。同様に、第１ビットに着目とすると、ｒ１＝０、ｒ２＝１、ｒ３＝１であるので、ｒ１＋ｒ２＋ｒ３  ｍｏｄ  ２＝０となり、５の進数表記の第１ビットの値に一致する。なお、「ａ ｍｏｄ ｂ」は整数ａを整数ｂで除算した際の余りを示す。
【００６６】
本願開示において、リングのシェア［ν］ｎをｍ個（ｍはｎ−１以下の整数、以下同じ）のビットのシェアに分解する処理を下記の式（１）のように表記する。
【００６７】
［式（１）］
2020075273.tif 000010
【００６８】
なお、
2020075273.tif 000011
を２進数で表記した際、ｊ（＝０、１、・・・、ｎ−１）番目のビットを
2020075273.tif 000012
と表記する。
【００６９】
ビット分解の手法には種々存在するが、本願開示では非特許文献１０に開示されたビット分解を用いる。非特許文献１０に開示されたビット分解の計算手法（アルゴリズム）に関する詳細は省略するが、当該文献によるビット分解では、最下位ビットから順に各秘密計算サーバ２０に分散する情報を計算していく。
【００７０】
ビット分解の計算に要する通信コストに関し、ビット分解を非特許文献１０に開示された方式を非特許文献１１の開示を用いて実行した場合には、６（ｎ−１）ビットの通信量、ｎ−１回の通信ラウンド数が必要となる。
【００７１】
［ビット埋込］
第１の実施形態に係る秘密計算システムでは、非特許文献１０に開示された「ビット埋込」と称される計算を編集距離算出に用いる。
【００７２】
ビット埋込とは、ビットのシェア［ｂ］をリングのシェア［ｂ］ｎに変換する処理である。本願開示において、ビット埋込を以下の式（２）のように表記する。
【００７３】
［式（２）］
2020075273.tif 000013
【００７４】
ビット埋込に関してもその計算手法は種々存在するが、本願開示では非特許文献１０に開示されたビット埋込処理を用いる。当業者にとって、ビット埋込に関する処理は非特許文献１０から明らかであるので、当該文献に開示されたビット埋込の計算手法（アルゴリズム）に関する詳細は省略する。
【００７５】
ビット埋込の計算に要する通信コストに関し、ビット埋込を非特許文献１０に開示された方式を非特許文献１１の開示を用いて実行した場合には、６ｎビットの通信量、２回の通信ラウンド数が必要となる。
【００７６】
続いて、秘密計算システムをなす各装置について説明する。
【００７７】
［制御装置］
図４は、第１の実施形態に係る制御装置１０の処理構成の一例を示す図である。図４を参照すると、制御装置１０は、通信制御部２０１と、秘密分散データ生成部２０２と、秘密分散データ復号部２０３と、を含んで構成される。
【００７８】
通信制御部２０１は、他の装置（秘密計算サーバ２０）との間の通信を制御する手段である。
【００７９】
秘密分散データ生成部２０２は、各秘密計算サーバ２０に配付するシェアを生成する手段である。具体的には、秘密分散データ生成部２０２は、秘密情報Ｓ（ＤＮＡ配列）について、Ｓ＝ｓ１＋ｓ２＋ｓ３  ｍｏｄ  Ｎを満たすｓ１、ｓ２、ｓ３をランダムに生成する。なお、Ｎは２の冪乗（Ｎ＝２ｎ）である。生成されたシェアは、通信制御部２０１を介して各秘密計算サーバ２０に配付される。その際、秘密分散データ生成部２０２は、例えば、１台の秘密計算サーバ２０に対し、２つのシェアを送信する。
【００８０】
秘密分散データ復号部２０３は、各秘密計算サーバ２０による秘密計算の結果を収集し、復元する手段である。
【００８１】
［秘密計算サーバ］
図５は、第１の実施形態に係る秘密計算サーバ２０の処理構成の一例を示す図である。図５を参照すると、秘密計算サーバ２０は、通信制御部３０１と、秘密計算実行部３０２と、を含んで構成される。
【００８２】
通信制御部３０１は、他の装置（制御装置１０、他の秘密計算サーバ２０）との間の通信を制御する手段である。
【００８３】
秘密計算実行部３０２は、所定の秘密計算を実行する手段である。具体的には、秘密計算実行部３０２は、２つのＤＮＡ配列に関する編集距離の計算を実行する。秘密計算実行部３０２は、外部装置（例えば、制御装置１０）から提供される秘密計算実行コードに従い秘密計算を実行する。
【００８４】
なお、以降の説明は、１台の秘密計算サーバ２０における秘密計算実行部３０２の動作を基準とするが、実際には、３台の秘密計算サーバ２０の秘密計算実行部３０２が協働して上記編集距離の算出を行う。
【００８５】
図６は、秘密計算実行部３０２の動作の一例を示すフローチャートである。
【００８６】
秘密計算実行部３０２は、通信制御部３０１を介して秘密分散された入力データ（２つのＤＮＡ配列）を取得する（ステップＳ０１）。
【００８７】
秘密計算実行部３０２は、取得した２つのＤＮＡ配列に含まれる文字数に応じたＤＰマトリクス（例えば、図３参照）を生成する（ステップＳ０２）。その際、秘密計算実行部３０２は、ＤＰマトリクスの初期化を行う。
【００８８】
ＤＰマトリクスの初期化が終了すると、秘密計算実行部３０２は、ＤＰマトリクスの各要素におけるスコアを算出する（ステップＳ０３）。ＤＰマトリクスの各要素におけるスコア算出処理の詳細は後述する。
【００８９】
秘密計算実行部３０２は、全ての要素におけるスコア算出が終了したか否かを確認する（ステップＳ０４）。全ての要素におけるスコアの算出が終了していれば（ステップＳ０４、Ｙｅｓ分岐）、秘密計算実行部３０２は、ステップＳ０５の処理を実行する。全ての要素におけるスコアの算出が終了していなければ（ステップＳ０４、Ｎｏ分岐）、秘密計算実行部３０２は、ステップＳ０３の処理を繰り返す。
【００９０】
秘密計算実行部３０２は、制御装置１０に対して秘密分散された演算結果を送信する（ステップＳ０５）。
【００９１】
続いて、図７を参照しつつ、秘密計算実行部３０２におけるＤＰマトリクスの各要素におけるスコア算出の動作について説明する。なお、秘密計算実行部３０２によるスコア算出動作を説明するにあたり、図８に示すＤＰマトリクスの一部を参照する。図８において、右下のマス目（スコアがＤｉ、ｊ）をスコア算出対象とする。
【００９２】
秘密計算実行部３０２は、スコア算出対象の要素（図８の右下のマス）の行方向（横方向）と列方向（縦方向）に割り当てられた文字が一致するか否かを判定する（ステップＳ１０１）。
【００９３】
文字が一致すれば（ステップＳ１０１、Ｙｅｓ分岐）、秘密計算実行部３０２は、左上の要素のスコアＤｉ−１、ｊ−１に「１」を加算する（ステップＳ１０２）。文字が一致しなければ（ステップＳ１０１、Ｎｏ分岐）、秘密計算実行部３０２は、特段の処理を行わず、ステップＳ１０３以降の処理を実行する。
【００９４】
秘密計算実行部３０２は、スコア算出対象の要素の左と上の要素のスコアＤｉ、ｊ−１とＤｉ−１、ｊに「１」を加算する（ステップＳ１０３）。
【００９５】
秘密計算実行部３０２は、スコア算出対象の要素の左と上の要素（対角線上の要素）に関するスコアの大小比較を行う（ステップＳ１０４）。
【００９６】
その際、秘密計算実行部３０２は、上記説明したビット分解を用いて２つのスコアの大小比較を行う。２つのスコアが秘密分散された状態で大小比較を行う場合には、数値演算で行うよりも論理演算で行う方が容易に結果を得ることができるためである。具体的には、２つの数値の差分値を２進数表記すれば、最上位ビットの値に応じて差分値の正負（比較対象の大小）が容易に得られる。
【００９７】
秘密計算実行部３０２は、上記のような理由からビット分解を用いて、２つのスコアの大小比較を行う。
【００９８】
［制限付き大小比較］
秘密計算実行部３０２は、上記ビット分解の処理を実行するにあたり、２つのスコアの差分値に関して全ビットの分解は行わず、所定の桁（所定のビット数）までのビット分解が完了した時点で処理を終了する。
【００９９】
例えば、差分値が４ビットで表現できる数値（例えば、５；２進数表記は０１０１）であれば、通常のビット分解では、最下位ビット（第０ビット）から順にビット分解が行われ、最上位ビット（第３ビット）のビット分解が完了した時点で処理が終了する。秘密計算実行部３０２は、上記のような通常のビット分解に替えて、例えば、第１ビットまでのビット分解が終了した時点で上記４ビットで表現できる数値のビット分解を終了するような処理を実行する。
【０１００】
秘密計算実行部３０２は、このように途中のビットまで実行したビット分解の結果を用いて２つのスコアの大小比較を行う。なお、以降の説明では、２つのスコアそれぞれについて、所定のビットまでビット分解を実行し、途中までビット分解された結果を用いて大小比較する処理を「制限付き大小比較」と表記する。
【０１０１】
制限付き大小比較を編集距離の算出に適用できる理由は以下のとおりである。
【０１０２】
非特許文献６によれば、置換コスト、挿入コスト、削除コストがそれぞれ「１」であれば、ＤＰマトリクスにおける、スコア算出対象の上と左の要素間を除く隣接する要素同士のスコアの差は、「１」、「０」、「−１」のいずれかである。当該事実を図８のＤＰマトリクスに適用すると、下記の５つの式により表現される関係が得られる。
【０１０３】
2020075273.tif 000014
2020075273.tif 000015
2020075273.tif 000016
2020075273.tif 000017
2020075273.tif 000018
【０１０４】
これらの関係は秘密計算により２つのスコアの大小比較［ν＜？ν’］ｎを行う際、入力の差ν−ν’について、｜ν−ν’｜≦１となることを意味する。なお、上記「＜？」は秘密分散されたシェアの大小比較を示す。
【０１０５】
また、スコア算出対象の上と左の対角線上の要素に着目すると、これらの差分値が取り得る値は、「−２」、「−１」、「０」、「１」、「２」であるので、入力の差ν−ν’について、｜ν−ν’｜≦２となる。当該事実を図８のＤＰマトリクスに適用すると、下記の式により表現される関係が得られる。
【０１０６】
2020075273.tif 000019
【０１０７】
上述のように、｜ν−ν’｜≦１が成立すると、大小比較の対象ν、ν’の値によらず以下の関係が成り立つ。
2020075273.tif 000020
なお、上記３つの式における添え字（２）は、数字が２進数により表現されていることを示す。また、大小比較の対象は３２ビットの数値を想定している。
【０１０８】
上記３つの式により、｜ν−ν’｜≦１の関係が成り立つのであれば、２つの入力値ν、ν’の大小比較を秘密計算で行う際、第１ビット（右から２ビット目）までの情報が得られれば十分であることが分かる。即ち、２つの入力値ν、ν’の大小比較を秘密計算で行う場合、｜ν−ν’｜≦１の関係が成り立つ場合には、差分値に関する第１ビットまでのビット分解の結果を用いて大小比較すれば十分である。
【０１０９】
大小比較の対象が対角線上の要素（スコア算出対象の上と左の２つの要素）のスコアである場合には、｜ν−ν’｜≦２の関係が成り立つので、２つのシェアの差分値に関する第２ビットまでのビット分解が必要となる。
【０１１０】
上記説明した制限付き大小比較をまとめると以下のとおりとなる。
【０１１１】
比較対象のシェア（秘密分散された入力）を［ν］ｎ、［ν’］ｎとする。つまり、２つのシェアそれぞれは、２ｎを法とする剰余類環に属するシェアである。
【０１１２】
２つの比較対象のシェアの間には、下記の式（３）の関係が成り立つ。
【０１１３】
［式（３）］
2020075273.tif 000021
但し、０≦ν、ν’＜２ｎ、ｔ＜２ｎ−１の関係が成り立つ。
【０１１４】
上記条件が成り立つ前提において、制限付き大小比較は下記の式（４）のとおり表現される。
【０１１５】
［式（４）］
2020075273.tif 000022
なお、上記式（４）において、「＜ｒ」は制限付き大小比較を示す。
【０１１６】
上記式（４）に示すように、制限付き大小比較の出力結果は、不等号が成立するならば「１」、不成立であれば「０」である。
【０１１７】
なお、どのビットまでのビット分解を実行すれば良いかは、上述の式（３）におけるｔから求めることができる。具体的には、以下の式（５）の関係を満たす、ｍが制限付き大小比較に必要なビット分解のビット位置である。つまり、制限付き大小比較では、式（５）から算出される第ｍビットまでのビット分解が必要となる（ビット分解する桁数はｍ＋１となる）。
【０１１８】
［式（５）］
２ｍ−１≦ｔ＜２ｍ≦２ｎ−１
【０１１９】
秘密計算実行部３０２は、下記の式（６）によるビット分解を実行する。
【０１２０】
［式（６）］
2020075273.tif 000023
【０１２１】
秘密計算実行部３０２は、上記式（６）による結果［（ν−ν’）｜ｍ］を判定結果のシュアとして出力する。なお、制限付き大小比較に要する通信コストは、６ｍビットの通信量、ｍ回の通信ラウンド数である。
【０１２２】
既存のビット分解と本願開示におけるビット分解の違いは以下のとおり纏めることができる。
【０１２３】
既存のビット分解では、０≦ν、ν’＜２ｎかつ｜ν−ν’｜＜２ｎの条件下で、ｎビットまでビット分解が行われる。この場合、通信コストは、６（ｎ−１）ビットの通信量、ｎ−１回の通信ラウンド数となる。
【０１２４】
本願開示のビット分解では、０≦ν、ν’＜２ｎかつ｜ν−ν’｜≦ｔ（２ｍ−１≦ｔ＜２ｍ≦２ｎ−１）の条件下で、第ｍビットまでビット分解が行われる。この場合、通信コストは、６ｍビットの通信量、ｍ回の通信ラウンド数となる。ここで、上記ｔやｍは、ビット分解を用いる処理（適用するアプリケーション；例えば、編集距離の計算）により予め定まる値（ｐｕｂｌｉｃ  ｖａｌｕｅ）であるため、ビット分解の通信コストはｎ（リングのサイズ）に依存しない定数となる。
【０１２５】
図７に示す編集距離の算出に説明を戻すと、上述のように、秘密計算実行部３０２は、スコア算出対象の要素の左と上の要素（対角線上の要素）に関するスコアの大小比較を行う（ステップＳ１０４）。具体的には、秘密計算実行部３０２は、下記の式（７）で表される制限付き大小比較を行い、判定結果［ｉ＿ｏｒ＿ｄ］を得る。
【０１２６】
［式（７）］
2020075273.tif 000024
【０１２７】
なお、上述のように、対角線上の要素におけるスコアの差分の絶対値は２以下であるので、式（５）におけるｔは「２」である。式（５）によれば、ｔ＝２とした場合のｍは「２」となる。従って、対角線上のスコアに関する大小比較を行う場合には、秘密計算実行部３０２は、２つのスコアの差分値に関する第２ビットまでのビット分解を行い大小比較を行う。
【０１２８】
具体的には、秘密計算実行部３０２は、１が加算された２つのスコアの差分値を計算する。秘密計算実行部３０２は、当該差分値に関し、第２ビットまでのビット分解を実行する。その後、秘密計算実行部３０２は、ビット分解された第２ビットの値に応じて、スコアの大小を決定する。より具体的には、第２ビットが「１」であれば、２つのスコアの差分値は負の値を示すので、上記式（７）では、スコアＤｉ、ｊ−１＋１の方がスコアＤｉ−１、ｊ＋１よりも大きいと判定される。従って、最下位ビットから順にビット分解され最後に得られる第ｍビットの値が「１」であれば、少なくともスコアＤｉ、ｊ−１＋１の方がスコアＤｉ−１、ｊ＋１より大きいことが確定する。上記第ｍビットの値が「０」であれば、スコアＤｉ、ｊ−１＋１の方がスコアＤｉ−１、ｊ＋１より小さいか、２つのスコアの値は同値であることが確定する。このように、秘密計算実行部３０２は、ビット分解された差分値の第ｍビットの値に応じて２つのシェアの大小を判定する。
【０１２９】
この場合、対角線上のスコアに関する大小比較に要する通信コストは、１２ビットの通信量、２回の通信ラウンド数である。このように、秘密計算実行部３０２は、編集距離の算出に使用するＤＰマトリクスにおけるスコア算出対象の要素の上と左に位置する要素それぞれのスコアに関する対角線上の大小比較を「制限付き大小比較」により行う。
【０１３０】
次に、秘密計算実行部３０２は、ＤＰマトリクスにおける対角線上のスコアの最小値［ＩｏｒＤ］ｎを計算する（ステップＳ１０５）。具体的には、秘密計算実行部３０２は、以下の式（８）に従い、最小値［ＩｏｒＤ］ｎを計算する。
【０１３１】
［式（８）］
2020075273.tif 000025
【０１３２】
なお、上記式（８）にはビット埋込が用いられている。当該ビット埋込を用いた最小値の計算は、非特許文献９の「３．数値演算例」に記載された「最小と最大の選択」に従って行うことができるので、その詳細な説明は省略する。この場合、最小値計算に要する通信コストは、不正検知を行わない場合、１８ｎビットの通信量、３回の通信ラウンド数である。
【０１３３】
秘密計算実行部３０２は、対角線上の最小値［ＩｏｒＤ］ｎと左上の要素のスコアに関する大小比較を行う（ステップＳ１０６）。当該大小比較においても、秘密計算実行部３０２は、制限付き大小比較を用いて２つの入力に関する大小比較を行う。
【０１３４】
この場合、上述のように、隣接する要素同士のスコアの差分の絶対値は「１」以下であるので、上記式（３）におけるｔは「１」となる。ｔが「１」であるので、式（５）によれば、ｍ＝１となる。従って、秘密計算実行部３０２は、第１ビットまでのビット分解を伴う制限付き大小比較により判定結果を得る。この場合の通信コストは、６ビットの通信量、１回の通信ラウンド数となる。このように、秘密計算実行部３０２は、対角線上の大小比較により小さいと判定された要素のスコアと、スコア算出対象の要素の左上に位置する要素のスコアと、に関する大小比較についても「制限付き大小比較」により行う。
【０１３５】
秘密計算実行部３０２は、対角線上の最小値［ＩｏｒＤ］ｎと左上の要素のスコアに関する最小値を算出する（ステップＳ１０７）。具体的には、秘密計算実行部３０２は、式（８）と同様に最小値を算出する。ステップＳ１０７にて算出された最小値が、スコア算出対象の要素（図８の右下のマス）におけるスコアとなる。この場合の最小値計算に要する通信コストも、１８ｎビットの通信量、３回の通信ラウンド数である。
【０１３６】
上記制限付き大小比較を含むスコアの算出に要する通信コストをまとめると、通信量は３６ｎ＋１８ビット、通信ラウンド数は９ラウンド（９回）となる。
【０１３７】
上記説明したように、各秘密計算サーバ２０は、式（３）に示す条件（秘密分散された２つのシェアの差分値の絶対値が自然数ｔ以下）が成立する場合、当該２つのシェアの差分値を計算する。さらに、各秘密計算サーバ２０は、当該２つのシェアの大小比較を上記差分値に関する最下位ビットから第ｍビットのビット分解を用いて行う。
【０１３８】
［ハードウェア構成］
続いて、秘密計算システムをなす各装置のハードウェア構成について説明する。
【０１３９】
図９は、秘密計算サーバ２０のハードウェア構成の一例を示す図である。秘密計算サーバ２０は、所謂、情報処理装置（コンピュータ）により実現され、図９に例示する構成を備える。例えば、秘密計算サーバ２０は、内部バスにより相互に接続される、ＣＰＵ（Central Processing Unit）２１、メモリ２２、入出力インターフェイス２３、通信手段であるＮＩＣ（Network Interface Card）２４等を備える。
【０１４０】
但し、図９に示す構成は、秘密計算サーバ２０のハードウェア構成を限定する趣旨ではない。秘密計算サーバ２０は、図示しないハードウェアを含んでもよい。秘密計算サーバ２０に含まれるＣＰＵ等の数も図９の例示に限定する趣旨ではなく、例えば、複数のＣＰＵ２１が秘密計算サーバ２０に含まれていてもよい。
【０１４１】
メモリ２２は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、補助記憶装置（ハードディスク等）等である。
【０１４２】
入出力インターフェイス２３は、図示しない入出力装置のインターフェイスである。入出力装置には、例えば、表示装置、操作デバイス等が含まれる。表示装置は、例えば、液晶ディスプレイ等である。操作デバイスは、例えば、キーボードやマウス等である。
【０１４３】
秘密計算サーバ２０の機能は、上述の処理モジュールにより実現される。当該処理モジュールは、例えば、メモリ２２に格納されたプログラムをＣＰＵ２１が実行することで実現される。また、そのプログラムは、ネットワークを介してダウンロードするか、あるいは、プログラムを記憶した記憶媒体を用いて、更新することができる。さらに、上記処理モジュールは、半導体チップにより実現されてもよい。即ち、上記処理モジュールが行う機能は、何らかのハードウェア、或いはハードウェアを利用して実行されるソフトウェアにより実現できればよい。
【０１４４】
なお、制御装置１０も情報処理装置（コンピュータ）により実現可能であり、そのハードウェア構成は当業者にとって明らかであるため詳細な説明を省略する。
【０１４５】
以上のように、第１の実施形態に係る秘密計算システムでは、編集距離の計算に必要な大小比較を制限付き大小比較にて実行している。より具体的には、秘密計算サーバ２０は、２つのスコアの大小比較を行う際に必要なビット分解の計算において、全ての桁に関する分解を行うのではなく、所定の条件（式（３）の条件）により定まる桁（第ｍビット）までのビット分解を行い大小比較を行う。その結果、編集距離の計算を秘密計算にて行う際のコストが削減できる。
【０１４６】
具体的には、上記説明したように、ビット分解を非特許文献１０に開示された方式を非特許文献１１の開示を用いて実行した場合には、６（ｎ−１）ビットの通信量、ｎ−１回の通信ラウンド数が必要となる。つまり、既存のビット分解を用いた秘密計算では、ＤＰマトリクスにおけるスコアの環のサイズを２ｎとしたとき、大小比較のコスト（通信量、通信ラウンド数）はｎに比例する。
【０１４７】
対して、第１の実施形態にて説明した「制限付き大小比較」を用いて、編集距離の秘密計算を行うと、大小比較に要するコストは、以下のとおりｎに比例しない定数サイズとなる。
対角線上の大小比較（ｔ＝２）：通信量は１２ビット、通信ラウンド数は２。
隣接する要素同士の大小比較（ｔ＝１）：通信量は６ビット、通信ラウンド数は１。
【０１４８】
このように、第１の実施形態に係る秘密計算システムでは、編集距離計算を秘密計算にて行う上で必要な大小比較に要するコストを環のサイズを決める「ｎ」に依存しない定数サイズに削減できる。その結果、第１の実施形態に係る秘密計算システムは、編集距離計算の対象となるＤＮＡ配列の文字数が多くなった場合（環のサイズ２ｎが大きくなった場合）であっても、少ないコストで編集距離を得ることができる。換言するならば、比較対象のＤＮＡ配列の文字数が多くなるほど、上記制限付き大小比較による通信コスト削減の効果がより顕著となる。
【０１４９】
［第２の実施形態］
続いて、第２の実施形態について図面を参照して詳細に説明する。
【０１５０】
第１の実施形態では、編集距離の算出にあたり対角線上のスコア間の大小比較を行っている。ここで、対角線上のスコアの差分の絶対値は２以下となるので、当該大小比較には第２ビットまでのビット分解が必要となる。上記の例のように、ビット分解する桁数が上昇すると、大小比較に要するコスト（通信量、通信ラウンド数）が増加する。
【０１５１】
第２の実施形態では、編集距離の算出アルゴリズムを変更することで、大小比較に要するコストを削減する秘密計算システムについて説明する。第２の実施形態に係る秘密計算システムは、大小比較の対象を変更することで対角線上の大小比較を不実施とし、通信ラウンド数の削減を実現する。
【０１５２】
なお、第１及び第２の実施形態に係る秘密計算システム、制御装置１０、秘密計算サーバ２０は同一とすることができるので図２等に相当する説明を省略する。第２の実施形態では、第１の実施形態との相違点を中心に説明する。
【０１５３】
図１０は、第２の実施形態に係る秘密計算実行部３０２におけるスコア算出動作の一例を示すフローチャートである。図７と図１０のステップＳ１０１〜Ｓ１０３の処理は同一とすることができるので同じ符号を与え、その詳細な説明を省略する。
【０１５４】
ステップＳ１１４において、秘密計算実行部３０２は、水平方向のスコア間の大小比較と、垂直方向のスコア間の大小比較を並列に実行する。具体的には、秘密計算実行部３０２は、図８においてスコア算出対象の要素（右下のマス）を基準として、左上と上のスコアに関する大小比較を行う（水平方向の大小比較）。また、秘密計算実行部３０２は、当該水平方向の大小比較と並行して、スコア算出対象の要素を基準として左上と左のスコアに関する大小比較を行う（垂直方向の大小比較）。秘密計算実行部３０２は、これらの大小比較を上記説明した制限付き大小比較により行う。具体的には、秘密計算実行部３０２は、第１ビットまでのビット分解を伴う制限付き大小比較を水平方向、垂直方向それぞれに関して行う。
【０１５５】
秘密計算実行部３０２は、上記水平方向の大小比較結果［ｈ］と垂直方向の大小比較結果［ｖ］を下記の式（９）により計算する。
【０１５６】
［式（９）］
2020075273.tif 000026
【０１５７】
なお、秘密計算実行部３０２が上記２つの大小比較を並列に計算（同時に計算）する理由は、当該計算に要する通信コストを抑制するためである。上記大小比較には、秘密計算サーバ２０間の通信が必要となる。その際、２つの大小比較にて発生する通信を同じタイミングとすることで、通信コストの上昇が抑制される。水平方向及び垂直方向の大小比較に要する通信コストは、１２ビットの通信量、１回の通信ラウンド数である。
【０１５８】
ステップＳ１１５において、秘密計算実行部３０２は、水平方向の最小値［Ｈ］ｎと垂直方向の最小値［Ｖ］ｎの計算を並行して実行する。具体的には、秘密計算実行部３０２は、下記の式（１０）により上記２つの最小値を計算する。
【０１５９】
［式（１０）］
2020075273.tif 000027
【０１６０】
秘密計算実行部３０２は、通信コストの抑制のため、２つの最小値に関しても並列に計算する。水平方向及び垂直方向の最小値算出に要する通信コストは、３６ｎビットの通信量、３回の通信ラウンド数である。
【０１６１】
秘密計算実行部３０２は、水平方向の最小値［Ｈ］ｎと垂直方向の最小値［Ｖ］ｎの大小比較を行う（ステップＳ１１６）。この場合も、秘密計算実行部３０２は、第１ビットまでのビット分解による制限付き大小比較により、２つの最小値のより小さい方を特定する。当該処理に要する通信コストは、１８ｎ＋６ビットの通信量、４回の通信ラウンド数である。このように、水平方向の大小比較により小さいと判定された要素のスコアと、垂直方向の大小比較により小さいと判定された要素のスコアと、に関する大小比較も制限付き大小比較により行われる。
【０１６２】
秘密計算実行部３０２は、ステップＳ１１６における大小比較の結果、小さいと判断された方の値をスコア算出対象のスコアとして採用する。
【０１６３】
第２の実施形態における最小値計算に要する通信コストをまとめると、通信量は５４ｎ＋１８ビット、通信ラウンド数は８となる。
【０１６４】
以上のように、第２の実施形態に係る秘密計算システムでは、大小比較の対象を第１の実施形態から変えることで最小値計算の通信ラウンド数を削減する。具体的には、第１の実施形態では９ラウンド必要であったが、第２の実施形態では８ラウンドの通信回数に減少している。但し、第２の実施形態では、制限付き大小比較の回数が増加しているので、編集距離の計算に必要な通信量が増加する。
【０１６５】
第２の実施形態では、第１の実施形態と比較して、通信ラウンド数に関するコストは減少するが通信量に関するコストは増加する。第１及び第２の実施形態に係る編集距離算出方法のいずれかを採用するかは、秘密計算システムの置かれた環境に応じて決定すればよい。例えば、各秘密計算サーバ２０を接続する通信経路の帯域が狭い場合には、通信量のコストが低い第１の実施形態に係る編集距離算出方法が有利である。対して、各秘密計算サーバ２０を接続する通信経路の帯域が広い場合には、１回の通信で多くのデータを送受信できるので通信ラウンド数が少ない第２の実施形態に係る編集距離算出方法が有利である。
【０１６６】
［他の方式との比較］
続いて、第１及び第２の実施形態にて説明した制限付き大小比較を用いた編集距離の算出に要する通信コスト（最終的な編集距離を得るまでのコスト）と、既存の大小比較を用いた編集距離の算出に要する通信コストの比較結果を開示する。
【０１６７】
ここでは、非特許文献５に開示されたＷＦ法に既存のビット分解を用いた大小比較による通信コストと、非特許文献６に開示されたビット並列法に既存のビット分解を用いた大小比較による通信コストを比較例として示す。なお、本願開示の方法を含む上記４つの方式による通信コストは、非特許文献１０及び１１の方式により編集距離を算出した場合のコストである。
【０１６８】
上記通信コストの比較は、文字長を１００文字、各文字のビット長を２ビット、スコアのビット長を３２ビット、比較対象の文字列に含まれるアルファベットの種類を４種類という条件で行った。図１１は、上記条件の下で編集距離を得るまでに要した通信コスト（非特許文献１０及び１１の秘密計算方式により編集距離を算出するために必要な通信量、通信ラウンド数）をまとめた図である。図１１を参照すると、既存の方法（非特許文献５に開示されたＷＦ法、非特許文献６に開示されたビット並列法）による編集距離の算出に比べ、第１及び第２の実施形態による編集距離算出の方法では通信コストが大きく減少しているのが理解される。とりわけ、通信ラウンド数に関しては、２０％以下にまで減少している。なお、上記４つの方式により算出される編集距離は同一である（算出結果の精度は同一である）。即ち、本願開示の編集距離算出方法を用いることで、正確な編集距離を高速に算出できる。
【０１６９】
［変形例］
第１及び第２の実施形態にて説明した秘密計算システムの構成、動作等は例示であって、システムの構成等を限定する趣旨ではない。例えば、図２に示す制御装置１０が秘密計算サーバ２０を集中制御するような形式ではなく、図１２に示す複数の秘密計算サーバ２０の中から１台の秘密計算サーバ２０を「代表サーバ」として選択する構成であってもよい。この場合、代表サーバとして選択された秘密計算サーバ２０が、他の秘密計算サーバ２０に対して制御装置１０と同等の制御を行えばよい。具体的には、代表サーバが入力データを秘密分散し、他の秘密計算サーバ２０に当該秘密分散されたデータを配付すると共に、他の秘密計算サーバ２０から秘密計算の結果を取得して復号してもよい。
【０１７０】
上記実施形態では、非特許文献５に記載されたＤＰマトリクスを用いた編集距離の算出を例にとり説明したが、非特許文献１７に開示された編集距離の算出に本願開示の制限付き大小比較を適用してもよい。
【０１７１】
上述の説明で用いた複数のフローチャートでは、複数の工程（処理）が順番に記載されているが、各実施形態で実行される工程の実行順序は、その記載の順番に制限されない。各実施形態では、例えば各処理を並行して実行する等、図示される工程の順番を内容的に支障のない範囲で変更することができる。
【０１７２】
情報処理装置（コンピュータ）の記憶部に秘密計算プログラムをインストールすることにより、コンピュータを秘密計算サーバとして機能させることができる。また、秘密計算プログラムをコンピュータに実行させることにより、コンピュータにより秘密計算方法を実行することができる。
【０１７３】
上記実施形態では、「制限付き大小比較」を適用するアプリケーションとして２つのＤＮＡ配列における編集距離の計算を例示したが、当該制限付き大小比較の処理は編集距離の計算以外の処理にも適用できることは勿論である。即ち、式（２）に示す条件が成立する場合には、２つのシェア（［ν］ｎ、［ν’］ｎ）の大小を上記制限付き大小比較にて判定することができる。換言すれば、２つのシェアの差分（ν−ν’）の取り得る範囲が予め制限されている場合には、一部のビット（桁）までのビット分解により大小の比較結果を得ることができる。
【０１７４】
なお、引用した上記の特許文献等の各開示は、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の全開示の枠内において種々の開示要素（各請求項の各要素、各実施形態ないし実施例の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択（部分的削除を含む）が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【０１７５】
１０  制御装置
２０、２０−１〜２０−３  秘密計算サーバ
２１  ＣＰＵ（Central Processing Unit）
２２  メモリ
２３  入出力インターフェイス
２４  ＮＩＣ（Network Interface Card）
１００  情報処理装置
２０１、３０１  通信制御部
２０２  秘密分散データ生成部
２０３  秘密分散データ復号部
３０２  秘密計算実行部
【図１】
2020075273.tif 000028
【図２】
2020075273.tif 000029
【図３】
2020075273.tif 000030
【図４】
2020075273.tif 000031
【図５】
2020075273.tif 000032
【図６】
2020075273.tif 000033
【図７】
2020075273.tif 000034
【図８】
2020075273.tif 000035
【図９】
2020075273.tif 000036
【図１０】
2020075273.tif 000037
【図１１】
2020075273.tif 000038
【図１２】
2020075273.tif 000039
【国際調査報告】
2020075273.tif 000040
2020075273.tif 000041
2020075273.tif 000042
2020075273.tif 000043