TOP > 国内特許検索 > 生成装置、復元装置、送信装置、受信装置、生成プログラム、復元プログラム、送信プログラム、及び受信プログラム > 明細書

明細書 :生成装置、復元装置、送信装置、受信装置、生成プログラム、復元プログラム、送信プログラム、及び受信プログラム

発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2020-046558 (P2020-046558A)
公開日 令和2年3月26日(2020.3.26)
発明の名称または考案の名称 生成装置、復元装置、送信装置、受信装置、生成プログラム、復元プログラム、送信プログラム、及び受信プログラム
国際特許分類 G09C   1/00        (2006.01)
G06F  21/60        (2013.01)
FI G09C 1/00 650Z
G06F 21/60 320
請求項の数または発明の数 14
出願形態 OL
全頁数 27
出願番号 特願2018-175393 (P2018-175393)
出願日 平成30年9月19日(2018.9.19)
発明者または考案者 【氏名】岩村 惠市
出願人 【識別番号】000125370
【氏名又は名称】学校法人東京理科大学
個別代理人の代理人 【識別番号】100079049、【弁理士】、【氏名又は名称】中島 淳
【識別番号】100084995、【弁理士】、【氏名又は名称】加藤 和詳
【識別番号】100099025、【弁理士】、【氏名又は名称】福田 浩志
審査請求 未請求
テーマコード 5J104
Fターム 5J104AA16
5J104EA02
5J104EA13
5J104PA07
5J104PA14
要約 【課題】秘密情報のオーナが知らない間に、秘密情報が漏洩することを抑制することができる秘密分散システムを提供する。
【解決手段】nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の分散値によって秘密情報を復元でき、k個未満では秘密情報を復元できないシステムにおいて、生成装置12は、秘密情報を識別する識別情報を、1つの秘密鍵を用いて変換することによって、少なくともk-1個以下の分散値の各々に対応する値を生成する。
【選択図】図1
特許請求の範囲 【請求項1】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、
前記秘密情報を識別する識別情報を、1つの秘密鍵を用いて変換することによって、少なくともk-1個以下の前記分散値の各々に対応する値を生成する生成部
を備えた生成装置。
【請求項2】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、
前記秘密情報を識別する識別情報を、1つの秘密鍵を用いて変換することによって、k-1個以下の前記分散値を生成する生成部
を備えた生成装置。
【請求項3】
前記生成部は、生成した値及び前記秘密情報を用いて前記k-1個以下の前記分散値以外の分散値を求めるための係数を算出する
請求項2に記載の生成装置。
【請求項4】
請求項1又は請求項2に記載の生成装置により生成された値を受信する受信部と、
前記受信部により受信された値を用いて前記秘密情報を復元する復元部と、
を備えた復元装置。
【請求項5】
請求項3に記載の生成装置により生成された係数を用いて同一の秘密情報から生成された異なる分散値の組み合わせによって2回以上前記秘密情報を復元する復元部
を備えた復元装置。
【請求項6】
秘密情報に対して、第1の乱数及び第2の乱数を作用させて第1の送信データを生成し、
前記秘密情報に対して、前記第1の乱数に代えた第3の乱数及び前記第2の乱数に代えた第4の乱数を同様に作用させて第2の送信データを生成する生成部と、
前記第1の送信データ及び前記第2の送信データを同一の受信装置に送信する送信部と、
を備えた送信装置。
【請求項7】
請求項6に記載の送信装置により送信された第1の送信データ及び第2の送信データを受信する受信部と、
前記第1の送信データから前記第2の乱数を排除した結果と、前記第2の送信データから前記第4の乱数を排除した結果との差分が、前記第1の乱数と前記第3の乱数との差分に等しいか否かを検証する検証部と、
を備えた受信装置。
【請求項8】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、
前記秘密情報を識別する識別情報を、1つの秘密鍵を用いて変換することによって、少なくともk-1個以下の前記分散値の各々に対応する値を生成する
処理をコンピュータに実行させるための生成プログラム。
【請求項9】
nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、
前記秘密情報を識別する識別情報を、1つの秘密鍵を用いて変換することによって、k-1個以下の前記分散値を生成する
処理をコンピュータに実行させるための生成プログラム。
【請求項10】
生成した値及び前記秘密情報を用いて前記k-1個以下の前記分散値以外の分散値を求めるための係数を算出する
処理を更に前記コンピュータに実行させるための請求項9に記載の生成プログラム。
【請求項11】
請求項8又は請求項9に記載の生成プログラムが実行されることにより生成された値を受信し、
受信した値を用いて前記秘密情報を復元する
処理をコンピュータに実行させるための復元プログラム。
【請求項12】
請求項10に記載の生成プログラムが実行されることにより生成された係数を用いて同一の秘密情報から生成された異なる分散値の組み合わせによって2回以上前記秘密情報を復元する
処理をコンピュータに実行させるための復元プログラム。
【請求項13】
秘密情報に対して、第1の乱数及び第2の乱数を作用させて第1の送信データを生成し、
前記秘密情報に対して、前記第1の乱数に代えた第3の乱数及び前記第2の乱数に代えた第4の乱数を同様に作用させて第2の送信データを生成し、
前記第1の送信データ及び前記第2の送信データを同一の受信装置に送信する
処理をコンピュータに実行させるための送信プログラム。
【請求項14】
請求項13に記載の送信プログラムが実行されることにより送信された第1の送信データ及び第2の送信データを受信し、
前記第1の送信データから前記第2の乱数を排除した結果と、前記第2の送信データから前記第4の乱数を排除した結果との差分が、前記第1の乱数と前記第3の乱数との差分に等しいか否かを検証する
処理をコンピュータに実行させるための受信プログラム。
発明の詳細な説明 【技術分野】
【0001】
本開示は、生成装置、復元装置、送信装置、受信装置、生成プログラム、復元プログラム、送信プログラム、及び受信プログラムに関する。
【背景技術】
【0002】
近年、新たなネットワーク技術としてクラウドコンピューティングが注目されている。クラウドコンピューティングとは、ユーザの持つデータをクラウドと呼ばれるネットワーク上の複数のサーバにより構成される仮想の大容量ストレージに分散して保管する技術である。クラウドコンピューティングでは、分散して保管されたデータに対し、ユーザがどこからでもネットワーク経由で必要に応じてアクセスすることを可能にする。さらに、データを暗号化して秘匿計算を実現することで単にデータを保管するだけでなく、クラウド上に分散して保管されたデータを用いて、個々のデータを秘匿しながら任意の処理を行うことが求められている。
【0003】
このような秘匿計算を実現するために秘密分散法の利用が注目されている。秘密分散法とは1個の秘密情報をn個に分散し、n個に分散した分散値のうち、k個(k≦n)の分散値を集めることで元の秘密情報が復元できるという技術である。また、秘密分散法では、n個に分散した分散値のうち、k個未満の分散値からは秘密情報に関する情報を得ることができない。この秘密分散法として、Shamirによる(k、n)閾値秘密分散法(以下、「Shamir法」ともいう)が知られている。
【0004】
また、分散値全体のデータサイズの小型化を実現するためのランプ型秘密分散法も知られている。また、非特許文献1では、非対称秘密分散法と呼ばれる秘密分散法が提案されている。
【0005】
また、特許文献1には、秘密分散のデータ復元処理の計算量を抑制する秘密分散システムが開示されている。
【先行技術文献】
【0006】

【特許文献1】特開2013-243441号公報
【0007】

【非特許文献1】高橋慧、岩村惠市、“クラウドコンピューティングに適した計算量的安全性を持つ秘密分散法”、CSS2012(2012)
【発明の概要】
【発明が解決しようとする課題】
【0008】
しかしながら、Shamir法をはじめとする秘密分散法では、正当な復元者ではない攻撃者が、分散値が保管されているサーバを攻撃し、k個以上の分散値を得ることができれば、そのk個以上の分散値から秘密情報を復元できてしまう。また、非対称秘密分散法でも、攻撃者が鍵サーバ及びデータサーバにアクセスできる状態にあり、鍵を用いて生成した分散値を含めk個の分散値を得ることができれば、秘密情報を復元することができてしまう。
【0009】
すなわち、前述した各種の秘密分散法では、秘密情報のオーナが知らない間に、秘密情報が漏洩してしまう場合があった。
【0010】
本開示は、以上の事情を鑑みて成されたものであり、秘密情報のオーナが知らない間に、秘密情報が漏洩することを抑制することができる生成装置、復元装置、送信装置、受信装置、生成プログラム、復元プログラム、送信プログラム、及び受信プログラムを提供することを目的とする。
【課題を解決するための手段】
【0011】
開示の技術は、一つの態様として、nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の前記分散値によって前記秘密情報を復元でき、k個未満では前記秘密情報を復元できないシステムにおいて、生成装置が、前記秘密情報を識別する識別情報を、1つの秘密鍵を用いて変換することによって、少なくともk-1個以下の前記分散値の各々に対応する値を生成する生成部を備える。
【発明の効果】
【0012】
本開示によれば、秘密情報のオーナが知らない間に、秘密情報が漏洩することを抑制することができる。
【図面の簡単な説明】
【0013】
【図1】第1~第4実施形態に係る秘密分散システムの構成の一例を示すブロック図である。
【図2】第1~第4実施形態に係る生成装置のハードウェア構成の一例を示すブロック図である。
【図3】第1~第4実施形態に係る復元装置のハードウェア構成の一例を示すブロック図である。
【図4】第1実施形態に係る分散処理の一例を示すフローチャートである。
【図5】第1実施形態に係る復元処理の一例を示すフローチャートである。
【図6】第2実施形態に係る分散処理の一例を示すフローチャートである。
【図7】第2実施形態に係る復元処理の一例を示すフローチャートである。
【図8】第3実施形態に係る分散処理の一例を示すフローチャートである。
【図9】第3実施形態に係る復元処理の一例を示すフローチャートである。
【図10】第4実施形態に係る分散処理の一例を示すフローチャートである。
【図11】第4実施形態に係る復元処理の一例を示すフローチャートである。
【図12】第5実施形態に係る通信システムの構成の一例を示すブロック図である。
【図13】第5実施形態に係る送信装置のハードウェア構成の一例を示すブロック図である。
【図14】第5実施形態に係る受信装置のハードウェア構成の一例を示すブロック図である。
【図15】第5実施形態に係る送信処理の一例を示すフローチャートである。
【図16】第5実施形態に係る受信処理の一例を示すフローチャートである。
【発明を実施するための形態】
【0014】
以下、図面を参照して、本開示の技術を実施するための形態例を詳細に説明する。

【0015】
まず、実施形態の詳細を説明する前に、Shamir法及び非対称秘密分散法の詳細と問題点とを説明する。

【0016】
<Shamir法>
Shamir法による秘密分散システムでは、n台のサーバに秘密情報が分散される。秘密情報のオーナは、秘密分散時にのみ存在するディーラに秘密情報の分散を依頼し、ディーラは、秘密分散演算を行うことによりn個の分散値を計算し、分散値をn台のサーバに分散して保管する。もしくは、秘密情報のオーナは、秘密分散時に自らディーラとなって秘密情報を分散する。一方、復元者は、n台のサーバに分散されたn個の分散値のうち、k個の分散値を集めることによって、秘密情報を復元することができる。Shamir法での秘密情報の分散及び復元は、以下に示すように行われる。

【0017】
<分散>
1.ディーラは、s<pで、かつn<pである任意の素数pを選ぶ。なお、sは秘密情報を表す。
2.ディーラは、Z/pZから、異なるn個のx(i=1、2、…、n)を選び、選んだxをn台のサーバそれぞれのサーバIDとする。
3.ディーラは、Z/pZから、k-1個の乱数a(l=1、2、…、k-1)を選び、以下の(1)式(以下、「分散式」ともいう)を生成する。

【0018】
【数1】
JP2020046558A_000003t.gif

【0019】
4.ディーラは、上記(1)式のxに各サーバIDを代入して分散値Wを計算し、各サーバに(x、W)を配布する。

【0020】
<復元>
1.復元に用いる分散値をW(i=1、2、…、k)とする。また、その分散値に対応するサーバIDをx(i=1、2、…、k)とする。
2.復元者は、k個の(x、W)を集め、集めたk個の(x、W)を上記(1)式に代入し、k個の連立方程式を解くことによって秘密情報であるsを復元する。なお、sを復元する際には、例えば、Lagrangeの補間公式を用いることができる。

【0021】
<非対称秘密分散法>
クラウドシステムを構成するn台のサーバからt台(t<k)のサーバを選択し、選択したt台のサーバを鍵サーバとする。鍵サーバは、分散値を保管せず、擬似乱数を生成するための鍵情報を保管する。n台のサーバのうち、鍵サーバ以外のサーバをデータサーバと呼び、データサーバは、分散値を生成するユーザから送られた分散値を保管する。また、秘密情報を管理する各ユーザyには、ユーザを識別する情報であるID[y](y=1、…、r)が割り当てられているものとする。また、それぞれのユーザyが管理するm個の秘密情報s1j、…、smj(j=1、…、r)にも、それぞれ秘密情報を識別する情報であるdID[sij](i=1、…、m)が割り当てられているものとする。また、以下では、Enc(a、b)は、aをbという鍵を用いて暗号化する処理を表すものとする。

【0022】
<分散>
ここでは、ユーザyがディーラとなる場合を説明する。また、ここでは、説明を分かり易くするために、r=1とし、sijをsと表す。
1.ユーザyは、自身のID[y]を鍵サーバx、…、xに送る。
2.ID[y]を受け取った鍵サーバは、自身が有する暗号装置と鍵key(j=1、…、t)とを用いて、以下の(2)式により、Eid(y、j)を生成し、生成したEid(y、j)をユーザyに送る。
Eid(y,j)=Enc(ID[y],keyj) (j=1,…,t) …(2)
3.Eid(y、j)を受け取ったユーザyは、自身が管理する秘密情報sを識別するdID[s](i=1、…、m)を用いて、以下の(3)式により、擬似乱数qijを生成する。
qij=Enc(dID[si],Eid(y,j)) …(3)
4.まず、ユーザyは、式(1)のk-1次の分散式の係数ベクトルA(i)=[s、ai1、…、aik-1におけるk-1-t次の部分ベクトルAk-1-t=[ait+1、…、aik-1を、真性乱数を用いてiごとに定める。次に、ユーザyは、(3)式により生成したt次の擬似乱数系列Q=[qi1、…、qit及び鍵サーバのID系列を用いて、以下の(4)式により、残りの部分ベクトルA(i)=[ai1、…、aitをiごとに算出する。

【0023】
【数2】
JP2020046558A_000004t.gif

【0024】
ここで、上記(4)式においてS=[s、…、sとすると、以下の(5)式で表される。
A(i)k-1=X'-1(Q-S) …(5)
これにより、ユーザyは、k-1次の分散式の係数ベクトルA(i)=[s、ai1、…、aik-1におけるk-1次の部分ベクトルA(i)k-1=[ai1、…、aik-1を全て求めることができる。
5.また、ユーザyは、データサーバxt+1、…、xに関する分散値Wit+1、…、Winを、4.の手順で生成した係数行列を用いて、(k、n)閾値秘密分散法と同様の手順により算出する。
6.ユーザyは、各データサーバに、生成した分散値W1j、…、Wmj(j=t+1、…、n)を送る。

【0025】
<復元>
1.復元者は、n個のサーバx、…、xから任意のk個のサーバを選択し、選択したサーバに対して、ユーザyのID[y]及び秘密情報sのdID[s]を送る。
2.鍵サーバのうち、(ID[y]、dID[s])を受け取ったサーバは、自身の持つ鍵key及び暗号装置を利用して、(2)式によりEid(y、j)を生成し、(3)式により擬似乱数qijを生成する。そして、サーバは、生成した擬似乱数qijを復元者に送る。
3.データサーバのうち、(ID[y]、dID[s])を受け取ったサーバは、自身のサーバIDに対応する分散値Wijを復元者に送る。
4.復元者は、受け取った擬似乱数qij及び分散値Wijを用いて、(k、n)閾値秘密分散法と同様の手順により、秘密情報sを復元する。

【0026】
しかしながら、Shamir法をはじめとする秘密分散法では、正当な復元者ではない攻撃者が、分散値が保管されているサーバを攻撃し、k個以上の分散値を得ることができれば、そのk個以上の分散値から秘密情報を復元できてしまう。また、非対称秘密分散法でも、攻撃者が鍵サーバ及びデータサーバにアクセスできる状態にあり、鍵を用いて生成した分散値を含め、k個の分散値を得ることができれば、秘密情報を復元することができてしまう。従って、Shamir法及び非対称秘密分散法を含む秘密分散法では、秘密情報のオーナが知らない間に、秘密情報が漏洩してしまう場合がある。

【0027】
また、Shamir法及び非対称秘密分散法を含む秘密分散法では、攻撃者がサーバを乗っ取り、復元時に偽の分散値を出力した場合、復元者は、正しい秘密情報を復元できず、更に、復元した秘密情報の正当性を検証することもできない。

【0028】
そこで、以下の実施形態では、以下の3つの問題点を解決する手法を説明する。
(A)秘密情報のオーナが知らない間に、秘密情報が漏洩する。
(B)偽の分散値が出力されても、それを検証することができない。
一方、一般に暗号技術では暗号文に相当するものは1つであるため、n=k=1と解釈できる。また、鍵を用いて暗号化しているために、k=1個の分散値に相当する暗号文が漏洩しても、鍵が安全に管理されていれば秘密情報は漏洩しない。従って、暗号技術では(A)は解決されているが、偽の暗号文が出力されると正しく復号できず、復号結果が乱数等である場合、それが正しいか検証できないのが一般的である。よって、暗号技術では(B)は解決されていない。一般に、秘密分散法及び暗号技術では、秘密情報、分散値、及び暗号文に対してMAC(Message Authentication Code)等の仕組みの異なる技術を用いて復号結果の正当性を検証できるが、秘密分散法又は暗号技術のみでは復号結果の正当性を検証することはできない。よって、(B)と同様の原理によって以下の(C)も解決する。
(C)暗号技術において偽の暗号文が出力されても、それを検証することができない。

【0029】
[第1実施形態]
まず、図1を参照して、本実施形態に係る秘密分散システム10の構成を説明する。図1に示すように、秘密分散システム10は、生成装置12、復元装置14、及び複数台のサーバ16を含む。生成装置12、復元装置14、及び複数台のサーバ16は、ネットワークNに接続され、互いに通信可能とされる。本実施形態に係る秘密分散システム10は、nを2以上の整数、kを2以上n以下の整数とし、秘密情報をn個の分散値に分散し、k個の分散値によって秘密情報を復元でき、k個未満では秘密情報を復元できないシステムである。

【0030】
生成装置12は、秘密情報のオーナ(以下、単に「オーナ」という)によって操作される装置であり、生成装置12の例としては、パーソナルコンピュータ等の情報処理装置が挙げられる。復元装置14は、秘密情報を復元する復元者(以下、単に「復元者」という)によって操作される装置であり、復元装置14の例としては、パーソナルコンピュータ等の情報処理装置が挙げられる。

【0031】
前述したShamir法において(1)式を用いて分散値Wを生成する場合、(1)式にサーバIDであるxを代入し、xに対応する分散値Wを得る。従って、xは、分散値Wを識別する値であると言える。一般に、xが分からなければ、分散値Wをk個集めても秘密情報を復元することはできない。そこで、本実施形態では、以下に示す処理によって、攻撃者がk個の分散値Wを集めたとしても、秘密情報を復元できないようにする。

【0032】
以下では、生成装置12は、1つの秘密鍵key、及びm(mは1以上の整数)個の秘密情報s、…、sを保管し、各秘密情報s(j=1、…、m)には、秘密情報sを識別する識別情報の一例としてのdID[s]が割り振られているものとする。また、前述したxを秘密情報毎に区別するためにxij(i=1、…、n、j=1、…、m)と表記する。また、分散値を保管するサーバ16(以下、「データサーバ16」ともいう)はn台準備されている。また、2≦t≦k-1とし、n-t(<k)台のサーバ16のxijは、予め定められているものとする。また、以下では、Enc(a、b)は、aをbという鍵を用いて暗号化することを意味し、a|bは、aの後にbを連結することを意味する。

【0033】
次に、図2を参照して、本実施形態に係る生成装置12のハードウェア構成を説明する。図2に示すように、生成装置12は、CPU(Central Processing Unit)20、一時記憶領域としてのメモリ21、不揮発性の記憶部22を含む。また、生成装置12は、液晶ディスプレイ等の表示装置23、キーボード等の入力装置24、及びネットワークNに接続されるネットワークI/F25(InterFace)を含む。CPU20、メモリ21、記憶部22、表示装置23、入力装置24、及びネットワークI/F25は、バス26に接続される。

【0034】
記憶部22は、HDD(Hard Disk Drive)、SSD(Solid State Drive)、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部22には、生成プログラム28が記憶される。CPU20は、記憶部22から生成プログラム28を読み出してからメモリ21に展開し、展開した生成プログラム28を実行する。CPU20が生成プログラム28を実行することで、開示の技術の生成部として動作する。また、記憶部22には、前述した秘密鍵key及び秘密情報sが記憶される。

【0035】
次に、図3を参照して、本実施形態に係る復元装置14のハードウェア構成を説明する。図3に示すように、復元装置14は、CPU30、一時記憶領域としてのメモリ31、不揮発性の記憶部32を含む。また、復元装置14は、液晶ディスプレイ等の表示装置33、キーボード等の入力装置34、及びネットワークNに接続されるネットワークI/F35を含む。CPU30、メモリ31、記憶部32、表示装置33、入力装置34、及びネットワークI/F35は、バス36に接続される。

【0036】
記憶部32は、HDD、SSD、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部32には、復元プログラム38が記憶される。CPU30は、記憶部32から復元プログラム38を読み出してからメモリ31に展開し、展開した復元プログラム38を実行する。CPU30が復元プログラム38を実行することで、開示の技術の受信部及び復元部として動作する。

【0037】
次に、図4及び図5を参照して、本実施形態に係る秘密分散システム10の作用を説明する。まず、図4を参照して、秘密情報を分散する分散処理を説明する。生成装置12のCPU20が生成プログラム28を実行することで、図4に示す分散処理を実行する。

【0038】
図4のステップS10で、CPU20は、以下に示す(6)式に従って、秘密情報sを識別する識別情報dID[s]を、1つの秘密鍵keyを用いて変換することによって、t台のサーバ16に対応するt個のxijを生成する。このxijが分散値Wijの各々に対応する値の一例である。
xij=Enc(dID[sj]|i,key0) (i=1,…,t,j=1,…,m) …(6)

【0039】
ステップS12で、CPU20は、k-1個の乱数a(l=1、…、k-1)を生成し、分散式(上記(1)式)を決定する。

【0040】
ステップS14で、CPU20は、ステップS10で生成したt個のxijと、予め定められたn-t個のxijとを用いて、ステップS12で決定した分散式に従って、各xijに対応する分散値Wijを算出する。ステップS16で、CPU20は、ステップS14で算出した分散値Wijを、対応するサーバ16に送信する。各サーバ16は、受信した分散値Wijを保管する。ステップS16の処理が終了すると、本分散処理が終了する。

【0041】
次に、図5を参照して、図4に示す分散処理によって分散された分散値から、秘密情報を復元する復元処理を説明する。復元装置14のCPU30が復元プログラム38を実行することで、図5に示す復元処理を実行する。

【0042】
図5のステップS20で、CPU30は、dID[s]に対応する分散値Wijをk台のサーバ16から取得する。ステップS22で、CPU30は、xijが予め定められているn-t台のサーバ16以外のサーバ16に対応するxijの送信を要求する要求情報を生成装置12に送信する。

【0043】
オーナは、生成装置12が要求情報を受信した後、秘密情報の復元を許可する場合は、入力装置24を介して復元を許可する操作を行い、秘密情報の復元を許可しない場合は、入力装置24を介して復元を禁止する操作を行う。生成装置12のCPU20は、オーナにより復元を許可する操作が行われた場合に、ステップS10と同様の処理によりxijを生成し、生成したxijを復元装置14に送信する。また、CPU20は、オーナにより復元を禁止する操作が行われた場合は、xijを生成しない。すなわち、この場合、CPU20は、xijを復元装置14に送信しない。ただし、この送信処理はオーナによる入力装置24を介した操作がなくても、オーナが予め許可する条件を設定しておき、要求情報がその条件を満たす場合に自動的に送信を行い、満たさない場合に送信しないよう予めプログラム等により設定しておいても良い。これは、以降も同様である。

【0044】
ステップS24で、CPU30は、ステップS22での要求に対応して生成装置12から送信されたxijを受信したか否かを判定する。この判定が肯定判定となった場合は、処理はステップS26に移行する。

【0045】
ステップS26で、CPU30は、ステップS20で取得した分散値Wij及びステップS24で受信したxijを用いて、(k、n)閾値秘密分散法と同様の手順により、秘密情報sを復元する。ステップS26の処理が終了すると、本復元処理が終了する。

【0046】
一方、例えば、オーナが秘密情報の復元を禁止する操作を行ったことにより、ステップS22でxijの送信を要求してから所定期間を経過してもxijが受信されなかった場合、または拒絶信号が送付された場合、ステップS24の判定が否定判定となる。ステップS24の判定が否定判定となった場合は、ステップS26の処理は実行されずに本復元処理が終了する。

【0047】
ところで、Lagrangeの補間公式では、x座標が異なるk個の点(x、y)、…、(x、y)から、それらの点を通るk-1次以下の多項式W(x)を求めることができる。前述した非対称秘密分散法の分散の4.の処理は、Lagrangeの補間公式によって多項式を求めることを意味するが、xとyとの関係は入れ替えてもよい。このため、y座標が異なるk個の点(x、y)、…、(x、y)から、それらの点を通るk-1次以下の多項式F(y)を求めることもでき、求めた曲線はW(x)=F(y)となる。すなわち、本実施形態は、x座標を公開し、y座標を分散値として生成・秘匿していた従来の秘密分散法に対して、生成した分散値を公開し、その基となるx座標を生成・秘匿することに対応する。また、オーナは、ステップS22で送信された要求情報に対して復元を許可しない場合、復元を禁止する操作を行うことによってxijを復元装置14に送信しないことにより、秘密情報の復元を制御することができる。この結果、秘密情報のオーナが知らない間に、秘密情報が漏洩することを抑制することができる。また、非対称秘密分散法と同等以上の安全性を確保することができる。

【0048】
なお、本実施形態では、分散処理のステップS10で、dID[s]とiとを連結して得られた情報を、keyを用いて暗号化することによってxijを生成する場合について説明したが、これに限定されない。例えば、iを、keyを用いて暗号化することによってkeyを生成し、dID[s]を、keyを用いて暗号化することによってxijを生成してもよい。また、例えば、dID[s]を、keyを用いて暗号化することによってkeyを生成し、iを、keyを用いて暗号化することによってxijを生成してもよい。

【0049】
また、本実施形態では、t個のxijを生成し、残りのn-t個のxijが予め定められている場合について説明したが、これに限定されない。分散処理のステップS10で、n個全てのxij(i=1、…、n)を生成してもよい。この場合、復元処理のステップS22で、復元に必要な全てのxijの送信を要求する要求情報を生成装置12に送信する形態が例示される。

【0050】
[第2実施形態]
開示の技術の第2実施形態を説明する。なお、秘密分散システム10の構成(図1参照)、生成装置12のハードウェア構成(図2参照)、及び復元装置14のハードウェア構成(図3参照)は、第1実施形態と同様であるため説明を省略する。

【0051】
前述した非対称秘密分散法は、復元時に秘密情報のオーナによる復元の許諾処理を導入していないため、鍵サーバを含めてk個の分散値を得ることができたユーザは、攻撃者であっても秘密情報を復元できる。また、ユーザが複数人いることを想定した場合、特定のオーナが鍵サーバを管理することができない。また、ユーザを1人とし、そのユーザ(すなわち、秘密情報のオーナ)が全ての鍵サーバを管理する、すなわち、非対称秘密分散法の<分散>の1.及び2.の処理をオーナが行えば、k-1個までの分散値をオーナが生成できるが、<復元>においてオーナによる復元の許諾処理を含んでいない。また、非対称秘密分散法では、鍵サーバがあることを前提とするため、鍵サーバが保管する鍵を用いて分散値を生成する手順に固定されている。本実施形態では、より汎用的な形とした手法を説明する。この手法により、上記(A)の問題点が汎用的に解決される。

【0052】
なお、本実施形態では、全てのサーバ16のサーバID(xij)は予め定められており、公開されているものとする。また、本実施形態では、サーバ16のうち、鍵サーバとして機能するサーバ16を「鍵サーバ16」といい、データサーバとして機能するサーバ16を「データサーバ16」という。ただし、鍵サーバ16は生成装置12内に存在するため、図において明示されているサーバ16はデータサーバ16であり、n-t台準備されている。それ以外の前提は第1実施形態と同様である。

【0053】
図6及び図7を参照して、本実施形態に係る秘密分散システム10の作用を説明する。まず、図6を参照して、本実施形態に係る秘密情報を分散する分散処理を説明する。生成装置12のCPU20が生成プログラム28を実行することで、図6に示す分散処理を実行する。

【0054】
図6のステップS30で、CPU20は、以下に示す(7)式に従って、秘密情報sを識別する識別情報dID[s]を、1つの秘密鍵keyを用いて変換することによって、t個のxij(i=1、…、t)に対応する分散値qijを生成する。
qij=Enc(dID[sj]|i,key0) (i=1,…,t,j=1,…,m) …(7)

【0055】
ステップS32で、CPU20は、上記(1)式のk-1次の分散式の係数ベクトルA(i)=[s、ai1、…、aik-1におけるk-1-t次の部分ベクトルAk-1-t=[ait+1、…、aik-1を、真性乱数を用いてiごとに定める。その後、CPU20は、ステップS30で生成したt個の擬似乱数であるqijからなるQ=[qi1、…、qit及び鍵サーバ16のID系列を用いて、以下の(8)式に従って、分散式のk-1次の部分ベクトルA(i)k-1=[ai1、…、aik-1における残りの部分ベクトルA(i)=[ai1、…、aitをiごとに算出する。

【0056】
【数3】
JP2020046558A_000005t.gif

【0057】
ステップS34で、CPU20は、サーバIDがxit+1、…、xinであるデータサーバ16に関する分散値Wit+1、…、Winを、ステップS32で生成した係数行列を用いて、(k、n)閾値秘密分散法と同様の手順により算出する。

【0058】
ステップS36で、CPU20は、ステップS34で算出した分散値Wij(j=t+1、…、n)を、対応するデータサーバ16に送信する。各データサーバ16は、受信した分散値Wijを保管する。ステップS36の処理が終了すると、本分散処理が終了する。

【0059】
次に、図7を参照して、図6に示す分散処理によって分散された分散値から、秘密情報を復元する復元処理を説明する。復元装置14のCPU30が復元プログラム38を実行することで、図7に示す復元処理を実行する。

【0060】
図7のステップS40で、CPU30は、dID[s]に対応する分散値の送信を要求する要求情報を生成装置12に送信する。オーナは、生成装置12が要求情報を受信した後、秘密情報の復元を許可する場合は、入力装置24を介して復元を許可する操作を行い、秘密情報の復元を許可しない場合は、入力装置24を介して復元を禁止する操作を行う。生成装置12のCPU20は、オーナにより復元を許可する操作が行われた場合に、ステップS30と同様の処理により分散値qijを生成し、生成した分散値qijを復元装置14に送信する。また、CPU20は、オーナにより復元を禁止する操作が行われた場合は、分散値qijを生成しない。すなわち、この場合、CPU20は、分散値qijを復元装置14に送信しない。

【0061】
ステップS42で、CPU30は、ステップS40での要求に対応して生成装置12から送信された分散値qijを受信したか否かを判定する。この判定が肯定判定となった場合は、処理はステップS44に移行する。

【0062】
ステップS44で、CPU30は、データサーバ16のWijと合わせて得られたk個の分散値を用いて、秘密情報sを復元する。ステップS44の処理が終了すると、本復元処理が終了する。

【0063】
一方、例えば、ステップS40で分散値qijの送信を要求してから所定期間を経過しても分散値qijが受信されなかった場合等では、ステップS42の判定が否定判定となる。ステップS42の判定が否定判定となった場合は、ステップS44の処理は実行されずに本復元処理が終了する。

【0064】
なお、本実施形態では、分散処理のステップS30で、dID[s]とiとを連結して得られた情報を、keyを用いて暗号化することによってqijを生成する場合について説明したが、これに限定されない。例えば、iを、keyを用いて暗号化することによってkeyを生成し、dID[s]を、keyを用いて暗号化することによってqijを生成してもよい。また、例えば、dID[s]を、keyを用いて暗号化することによってkeyを生成し、iを、keyを用いて暗号化することによってqijを生成してもよい。

【0065】
[第3実施形態]
開示の技術の第3実施形態を説明する。なお、秘密分散システム10の構成(図1参照)、生成装置12のハードウェア構成(図2参照)、及び復元装置14のハードウェア構成(図3参照)は、第1実施形態と同様であるため説明を省略する。

【0066】
第1実施形態では分散値を識別するxijを1つの秘密鍵keyを用いて生成し、第2実施形態では分散値qijを1つの秘密鍵keyを用いて生成する形態例を説明したが、本実施形態では、これらの形態例を組み合わせた形態例を説明する。この組み合わせによって、上記(A)の問題点に加え、上記(B)の問題点も解決することができる。

【0067】
一般に、秘密情報sは、k個の分散値yと、分散値yを識別するk個の値xとを用いて、Lagrangeの補間公式から以下に示すように求められる。x座標が異なるk個の点(x、y)、(x、y)、…、(x、y)を通るk-1次以下の多項式W(x)は以下の(9)式で表される。

【0068】
【数4】
JP2020046558A_000006t.gif

【0069】
ただし、

【0070】
【数5】
JP2020046558A_000007t.gif

【0071】
とする。従って、秘密情報sはW(0)の値となる。ここで、サーバ16が攻撃者に乗っ取られ、乗っ取られたサーバ16が偽の値y+Δyを出力した場合、偽のW(0)は以下に示す(10)式で表される。

【0072】
【数6】
JP2020046558A_000008t.gif

【0073】
例えば、1回目の復元で偽の分散値y+Δyがサーバ16から出力されてW(0)が復元され、2回目の復元で1回目とは異なる偽のy+Δyがサーバ16から出力されてW’’(0)が復元された場合、その差分は以下に示す(11)式で表される。

【0074】
【数7】
JP2020046558A_000009t.gif

【0075】
従って、ΔyとΔyとに以下に示す(12)式の関係があれば、W(0)とW’’(0)との差分は0となる、すなわち、1回目と2回目とにそれぞれ復元された秘密情報が一致する。このため、この場合、復元された秘密情報が偽りの値であることは判定できない。

【0076】
【数8】
JP2020046558A_000010t.gif

【0077】
しかしながら、

【0078】
【数9】
JP2020046558A_000011t.gif

【0079】
は、全てのxが特定できなければ定まらない。従って、攻撃者にとって未知のxが存在する場合、攻撃者は乗っ取ったサーバ16に対して、W(0)とW’’(0)との差分が0となるΔy及びΔyを設定することができない。

【0080】
そこで、本実施形態では、以下に示す処理を行うことによって、秘密情報の漏洩に関する上記(A)の問題点、及び秘密情報の改ざんに関する上記(B)の問題点の双方を解決する。なお、以下では、第2実施形態と同様にサーバ16はデータサーバ16のみでn-t台準備され、そのデータサーバ16のサーバIDであるxijは予め定められ、かつ公開されているものとする。また、n>kであり、これら以外の前提は第1実施形態と同様とする。

【0081】
図8及び図9を参照して、本実施形態に係る秘密分散システム10の作用を説明する。まず、図8を参照して、本実施形態に係る秘密情報を分散する分散処理を説明する。生成装置12のCPU20が生成プログラム28を実行することで、図8に示す分散処理を実行する。

【0082】
図8のステップS50で、CPU20は、以下に示す(13)式に従って、秘密情報sを識別する識別情報dID[s]を、1つの秘密鍵keyを用いて変換することによって、t台のサーバ16に対応するt個のxijを生成する。
xij=Enc(dID[sj]|i|0,key0) (i=1,…,t,j=1,…,m) …(13)

【0083】
ステップS52で、CPU20は、以下に示す(14)式に従って、秘密情報sを識別する識別情報dID[s]を、1つの秘密鍵keyを用いて変換することによって、t個のxij(i=1、…、t)に対応する分散値qijを生成する。
qij=Enc(dID[sj]|i|1,key0) (i=1,…,t,j=1,…,m) …(14)

【0084】
このように、本実施形態では、ステップS50で生成されるt(≦k-1)個のxijは、連結させる値(xijは0、qijは1)を異ならせることにより、分散値qijとは異なる値として生成される。連結させる値は0及び1を用いたがこれに限られず、任意の値を用いてもよい。

【0085】
ステップS54で、CPU20は、ステップS50、S52で生成した値を用いて、t個の分散値qij以外の分散値Wit+1、…、Winを求めるための係数を算出する。具体的には、CPU20は、上記(1)式のk-1次の分散式の係数ベクトルA(i)=[s、ai1、…、aik-1におけるk-1-t次の部分ベクトルAk-1-t=[ait+1、…、aik-1を、真性乱数を用いてiごとに定める。その後、CPU20は、ステップS50で生成したt個の擬似乱数であるqijからなるQ=[qi1、…、qit及びステップS52で生成した鍵サーバ16のID系列を用いて、以下の(15)式に従って、分散式のk-1次の部分ベクトルA(i)k-1=[ai1、…、aik-1における残りの部分ベクトルA(i)=[ai1、…、aitをiごとに算出する。

【0086】
【数10】
JP2020046558A_000012t.gif

【0087】
ステップS56で、CPU20は、サーバIDがxit+1、…、xinであるデータサーバ16に関する分散値Wit+1、…、Winを、ステップS54で生成した係数行列を用いて、(k、n)閾値秘密分散法と同様の手順により算出する。

【0088】
ステップS58で、CPU20は、ステップS56で算出した分散値Wij(j=t+1、…、n)を、対応するデータサーバ16に送信する。各データサーバ16は、受信した分散値Wijを保管する。ステップS58の処理が終了すると、本分散処理が終了する。

【0089】
次に、図9を参照して、図8に示す分散処理によって分散された分散値から、秘密情報を復元する復元処理を説明する。復元装置14のCPU30が復元プログラム38を実行することで、図9に示す復元処理を実行する。

【0090】
図9のステップS60で、CPU30は、データサーバ16に保管されているk-t+u個の分散値Wijを受信する。なお、uは、検証用の分散値の数(1以上の整数)を表す。ステップS62で、CPU30は、t個の分散値と、その分散値を識別するためのxijとの送信を要求する要求情報を生成装置12に送信する。オーナは、生成装置12が要求情報を受信した後、秘密情報の復元を許可する場合は、入力装置24を介して復元を許可する操作を行い、秘密情報の復元を許可しない場合は、入力装置24を介して復元を禁止する操作を行う。生成装置12のCPU20は、オーナにより復元を許可する操作が行われた場合に、ステップS50、S52と同様の処理によりxij及び分散値qijを生成し、生成したxij及び分散値qijを復元装置14に送信する。また、CPU20は、オーナにより復元を禁止する操作が行われた場合は、xij及び分散値qijを生成しない。すなわち、この場合、CPU20は、xij及び分散値qijを復元装置14に送信しない。

【0091】
ステップS64で、CPU30は、ステップS62での要求に対応して生成装置12から送信されたxij及び分散値qijを受信したか否かを判定する。この判定が肯定判定となった場合は、処理はステップS66に移行する。

【0092】
ステップS66で、CPU30は、得られたk+u個のqij、Wij、及びxijを用いて、データサーバ16から得られた分散値Wijを異ならせて(qijは同一)、秘密情報sをu+1回復元する。換言すると、CPU30は、ステップS54で生成された係数を用いてステップS56で同一の秘密情報から生成された異なる分散値の組み合わせによって、秘密情報を2回以上復元する。

【0093】
ステップS68で、CPU30は、ステップS66で復元したu+1個の秘密情報sを用いて、復元した秘密情報sを検証する。具体的には、CPU30は、ステップS66で復元したu+1個の秘密情報sが一致した場合は、その秘密情報sは正しいと判断し、異なる場合は、その秘密情報sは不正である、すなわち、データサーバ16の少なくとも1台が攻撃されたと判断する。CPU30は、秘密情報sが正しいと判断した場合は、その秘密情報sを用いた処理を行う。一方、CPU30は、秘密情報sが不正であると判断した場合は、例えば、表示装置33にエラーメッセージを表示する。ステップS68の処理が終了すると、本復元処理が終了する。

【0094】
一方、例えば、ステップS62でxij及び分散値qijの送信を要求してから所定期間を経過してもxij及び分散値qijが受信されなかった場合等では、ステップS64の判定が否定判定となる。ステップS64の判定が否定判定となった場合は、ステップS66、S68の処理は実行されずに本復元処理が終了する。

【0095】
以下に具体例を用いて説明する。例えば、k=3、n=4、t=2、u=n-k=1とした場合、生成装置12はt=2より2台分の鍵サーバ16を含むため、それをx、xとし、x、xに対応する分散値qijを生成する。また、この場合、データサーバ16はn-t=2より2台存在し、そのサーバIDであるx、xは公開されている。この2台のデータサーバ16が、攻撃者により乗っ取られ、偽の分散値y+Δy、y+Δyを出力する場合を考える。

【0096】
この場合、復元装置14は、外部からの分散値を異ならせて復元処理を行う、すなわち1回目はx、x、xの組み合わせによって秘密情報の復元を行い、2回目はx、x、xの組み合わせによって秘密情報の復元を行う。ここで、x、xは生成装置12が生成した分散値を識別する値であるため、攻撃者はx、xを知ることはできない。この場合、1回目の復元によって、以下の(16)式に示す偽のW(0)が復元される。

【0097】
【数11】
JP2020046558A_000013t.gif

【0098】
また、この場合、2回目の復元によって、以下の(17)式に示す偽のW’’(0)が復元される。

【0099】
【数12】
JP2020046558A_000014t.gif

【0100】
ここで、x、xに対応する2台のデータサーバ16が同一の攻撃者によって乗っ取られたとしても、その攻撃者は、x、xを知ることはできないため、以下の(18)式の関係のΔy及びΔyを設定することができない。このため、W(0)とW’’(0)とは一致しない。従って、復元装置14は、データサーバ16から偽の分散値が出力されたことを検証することができる。

【0101】
【数13】
JP2020046558A_000015t.gif

【0102】
上記の例では、u=1とし、xに対応するデータサーバ16の他に、xに対応するデータサーバ16から検証用の分散値を得ている。この場合、2台のデータサーバ16のうちの何れか、又は双方が不正であるかは判断できない。

【0103】
例えば、k=3、n=5、t=2、u=n-k=2とすれば、3台のデータサーバ16が存在し、xの他に2つの分散値を検証用に使用することができる。ここで、xに対応するデータサーバ16のみが乗っ取られ、偽の分散値y+Δyを出力する場合を考える。この場合、x、xに対応する分散値を用いて2回の復元により得られた2つの秘密情報は、Δy=Δy=0となるため一致し、xに対応する分散値を用いて復元された秘密情報のみが他の秘密情報と異なる。すなわち、この場合、不正なデータサーバ16を特定することができる。

【0104】
また、2台のデータサーバ16が乗っ取られた場合、3回の復元により得られた3つの秘密情報が全て異なるため、この場合は、2台以上のデータサーバ16が不正であると判断することができる。従って、乗っ取られて偽の分散値を出力するデータサーバ16の数をeとした場合、e<uであれば、不正なデータサーバ16を特定することができる。

【0105】
なお、本実施形態では、分散処理のステップS50、S52において分散値qijと、分散値qijを識別するxijとを異なる数(本実施形態では0と1)を連結させることによって異なる値として生成する場合について説明したが、これに限定されない。xijと分散値qijとは異なる値であれば、他の任意の手法によって生成してもよい。

【0106】
また、本実施形態では、分散処理のステップS50、S52においてxij及び分散値qijをdID[s]、i、及び0(又は1)を連結させ、かつ1回の暗号化によって生成する場合について説明したが、これに限定されない。例えば、連結させる組み合わせを本実施形態とは異ならせてもよいし、複数回の暗号化によってxij及び分散値qijを生成してもよい。

【0107】
また、第1~第3実施形態を通して、xijは秘密情報sごとに生成しているが、これは、1つの秘密情報の復元時に、生成装置12からxijを得ることができても、異なるxijが設定されている他の秘密情報を復元できないようにするためである。これにより、安全性の低下を抑制することができる。また、攻撃者が分散値からxijを得ようとしても、分散値はn-t(<k)台のデータサーバ16にしか保管されていないため、同様にxijを得ることはできない。

【0108】
[第4実施形態]
開示の技術の第4実施形態を説明する。なお、秘密分散システム10の構成(図1参照)、生成装置12のハードウェア構成(図2参照)、及び復元装置14のハードウェア構成(図3参照)は、第1実施形態と同様であるため説明を省略する。

【0109】
第3実施形態では、n>kを前提とし、検証用の分散値を使用する形態例を説明した。本実施形態では、n=kとし、検証用の分散値を使用しない形態例を説明する。本実施形態では、1つの秘密情報を異なる分散式で2回分散し、第3実施形態と同様に、2回の復元によって得られた秘密情報が一致するか否かによって検証する。

【0110】
図10及び図11を参照して、本実施形態に係る秘密分散システム10の作用を説明する。まず、図10を参照して、本実施形態に係る秘密情報を分散する分散処理を説明する。生成装置12のCPU20が生成プログラム28を実行することで、図10に示す分散処理を実行する。

【0111】
図10のステップS70で、CPU20は、以下に示す(19)式及び(20)式に従って、秘密情報sを識別する識別情報dID[s]を、1つの秘密鍵keyを用いて変換することによって、xij及びxijを生成する。このxij及びxijは、互いに異なる2個のサーバIDに対応する。
xij=Enc(dID[sj]|i|0,key0) (i=1,…,t,j=1,…,m) …(19)
x'ij=Enc(dID[sj]|i|2,key0) (i=1,…,t,j=1,…,m) …(20)

【0112】
ステップS72で、CPU20は、以下に示す(21)式に従って、秘密情報sを識別する識別情報dID[s]を、1つの秘密鍵keyを用いて変換することによって、t個のxij(i=1、…、t)に対応する分散値qijを生成する。また、CPU20は、以下に示す(22)式に従って、秘密情報sを識別する識別情報dID[s]を、1つの秘密鍵keyを用いて変換することによって、t個のxij(i=1、…、t)に対応する分散値qijを生成する。
qij=Enc(dID[sj]|i|1,key0) (i=1,…,t,j=1,…,m) …(21)
q'ij=Enc(dID[sj]|i|2,key0) (i=1,…,t,j=1,…,m) …(22)

【0113】
ステップS74で、CPU20は、非対称秘密分散法の<分散>の4.の手順を用いて、t個の(xij、qij)と(0、s)とを通るk-1次の多項式W(x)を求める。多項式W(x)は、以下の(23)式で表される。

【0114】
【数14】
JP2020046558A_000016t.gif

【0115】
ステップS76で、CPU20は、非対称秘密分散法の<分散>の4.の手順を用いて、t個の(xij、qij)と(0、s)とを通るk-1次の多項式V(x)を求める。多項式V(x)は、以下の(24)式で表される。

【0116】
【数15】
JP2020046558A_000017t.gif

【0117】
ステップS78で、CPU20は、サーバIDがxit+1、…、xinであるデータサーバ16に関する分散値Wit+1、…、Winを、ステップS74で算出した多項式W(x)を用いて、(k、n)閾値秘密分散法と同様の手順により算出する。

【0118】
ステップS80で、CPU20は、サーバIDがxit+1、…、xinであるデータサーバ16に関する分散値Vit+1、…、Vinを、ステップS76で算出した多項式V(x)を用いて、(k、n)閾値秘密分散法と同様の手順により算出する。

【0119】
ステップS82で、CPU20は、ステップS78、S80で算出した分散値Wij、Vij(j=t+1、…、n)を、対応するデータサーバ16に送信する。各データサーバ16は、受信した分散値Wij、Vijを保管する。ステップS82の処理が終了すると、本分散処理が終了する。

【0120】
次に、図11を参照して、図10に示す分散処理によって分散された分散値から、秘密情報を復元する復元処理を説明する。復元装置14のCPU30が復元プログラム38を実行することで、図11に示す復元処理を実行する。

【0121】
図11のステップS90で、CPU30は、データサーバ16に保管されているk-t個の分散値Wij、Vijを受信する。ステップS92で、CPU30は、t個の分散値qij、qijと、その分散値qij、qijを識別するためのxij、xijの送信を要求する要求情報を生成装置12に送信する。オーナは、生成装置12が要求情報を受信した後、秘密情報の復元を許可する場合は、入力装置24を介して復元を許可する操作を行い、秘密情報の復元を許可しない場合は、入力装置24を介して復元を禁止する操作を行う。生成装置12のCPU20は、オーナにより復元を許可する操作が行われた場合に、ステップS70、S72と同様の処理によりxij、xij及び分散値qij、qijを生成し、生成したxij、xij及び分散値qij、qijを復元装置14に送信する。また、CPU20は、オーナにより復元を禁止する操作が行われた場合は、xij、xij及び分散値qij、qijを生成しない。すなわち、この場合、CPU20は、xij、xij及び分散値qij、qijを復元装置14に送信しない。

【0122】
ステップS94で、CPU30は、ステップS92での要求に対応して生成装置12から送信されたxij、xij及び分散値qij、qijを受信したか否かを判定する。この判定が肯定判定となった場合は、処理はステップS96に移行する。

【0123】
ステップS96で、CPU30は、得られたk個のqij、Wij、及びxijを用いて、多項式W(x)により秘密情報sを復元する。また、CPU30は、得られたk個のqij、Vij、及びxijを用いて、多項式V(x)により秘密情報sを復元する。

【0124】
ステップS98で、CPU30は、ステップS96で復元した2個の秘密情報sを用いて、復元した秘密情報sを検証する。具体的には、CPU30は、多項式W(x)により復元した秘密情報sと多項式V(x)により復元した秘密情報sとが一致した場合、その秘密情報sが正しいと判断する。一方、CPU30は、多項式W(x)により復元した秘密情報sと多項式V(x)により復元した秘密情報sとが異なる場合、その秘密情報sは不正である、すなわち、データサーバ16の少なくとも1台が攻撃されたと判断する。CPU30は、秘密情報sが正しいと判断した場合は、その秘密情報sを用いた処理を行う。一方、CPU30は、秘密情報sが不正であると判断した場合は、例えば、表示装置33にエラーメッセージを表示する。ステップS98の処理が終了すると、本復元処理が終了する。

【0125】
一方、例えば、ステップS92でxij、xij及び分散値qij、qijの送信を要求してから所定期間を経過してもxij、xij及び分散値qij、qijが受信されなかった場合等では、ステップS94の判定が否定判定となる。ステップS94の判定が否定判定となった場合は、ステップS96、S98の処理は実行されずに本復元処理が終了する。

【0126】
以下に具体例を用いて説明する。例えば、n=k=2、t=1とした場合を考える。この場合、データサーバ16はn-t=1台であり、このデータサーバ16のサーバIDをxとし、攻撃者に乗っ取られているものとする。このxに対応するデータサーバ16が偽の分散値W+ΔW、V+ΔVを出力する場合を考える。

【0127】
この場合、復元装置14は、1回目には、多項式W(x)により秘密情報の復元を行うことによって、以下の(25)式で表されるW(0)を復元する。

【0128】
【数16】
JP2020046558A_000018t.gif

【0129】
更に、この場合、復元装置14は、2回目には、多項式V(x)により秘密情報の復元を行うことによって、以下の(26)式で表されるV(0)を復元する。

【0130】
【数17】
JP2020046558A_000019t.gif

【0131】
(0)とV(0)との差分は、ΔWとΔVとが以下の(27)式の関係であれば0となるが、攻撃者はx、xを知ることはできないため、W(0)とV(0)との差分が0となるΔWとΔVとを設定することはできない。このため、W(0)とV(0)とは一致しない。従って、復元装置14は、データサーバ16から偽の分散値が出力されたことを検証することができる。

【0132】
【数18】
JP2020046558A_000020t.gif

【0133】
[第5実施形態]
開示の技術の第5実施形態を説明する。第3及び第4実施形態では、分散値の検証のためにMAC等の秘密分散とは異なる技術を用いずに、検証用の分散値を用いることによって、復元した秘密情報の正当性を検証する手法を説明した。この手法は、MAC等を用いずに同じ形式の分散値を用いるため簡易であり、かつビット長等の形式を同じにすることができる(MACはビット長が規定されている)。本実施形態では、第3及び第4実施形態と同様の特徴を持つ復号結果の検証法を暗号技術に適用した形態例を説明する。

【0134】
まず、図12を参照して、本実施形態に係る通信システム40の構成を説明する。図12に示すように、通信システム40は、送信装置42及び受信装置44を含む。送信装置42及び受信装置44は、ネットワークNに接続され、互いに通信可能とされる。また、本実施形態では、送信装置42及び受信装置44は、同一の秘密鍵を記憶している。

【0135】
送信装置42は、秘密情報を送信する送信者によって操作される装置であり、送信装置42の例としては、パーソナルコンピュータ等の情報処理装置が挙げられる。受信装置44は、秘密情報を受信する受信者によって操作される装置であり、受信装置44の例としては、パーソナルコンピュータ等の情報処理装置が挙げられる。

【0136】
次に、図13を参照して、本実施形態に係る送信装置42のハードウェア構成を説明する。図13に示すように、送信装置42は、CPU50、一時記憶領域としてのメモリ51、不揮発性の記憶部52を含む。また、送信装置42は、液晶ディスプレイ等の表示装置53、キーボード等の入力装置54、及びネットワークNに接続されるネットワークI/F55を含む。CPU50、メモリ51、記憶部52、表示装置53、入力装置54、及びネットワークI/F55は、バス56に接続される。

【0137】
記憶部52は、HDD、SSD、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部52には、送信プログラム58が記憶される。CPU50は、記憶部52から送信プログラム58を読み出してからメモリ51に展開し、展開した送信プログラム58を実行する。CPU50が送信プログラム58を実行することで、開示の技術の生成部及び送信部として動作する。

【0138】
次に、図14を参照して、本実施形態に係る受信装置44のハードウェア構成を説明する。図14に示すように、受信装置44は、CPU60、一時記憶領域としてのメモリ61、不揮発性の記憶部62を含む。また、受信装置44は、液晶ディスプレイ等の表示装置63、キーボード等の入力装置64、及びネットワークNに接続されるネットワークI/F65を含む。CPU60、メモリ61、記憶部62、表示装置63、入力装置64、及びネットワークI/F65は、バス66に接続される。

【0139】
記憶部62は、HDD、SSD、及びフラッシュメモリ等によって実現される。記憶媒体としての記憶部62には、受信プログラム68が記憶される。CPU60は、記憶部62から受信プログラム68を読み出してからメモリ61に展開し、展開した受信プログラム68を実行する。CPU70が受信プログラム68を実行することで、開示の技術の受信部及び検証部として動作する。

【0140】
次に、図15及び図16を参照して、本実施形態に係る通信システム40の作用を説明する。まず、図15を参照して、秘密情報を送信する送信処理を説明する。送信装置42のCPU50が送信プログラム58を実行することで、図15に示す送信処理を実行する。

【0141】
図15のステップS100で、CPU50は、秘密鍵を用いて、第1の乱数a及び第2の乱数αを生成する。ステップS102で、CPU50は、秘密情報aに対して、ステップS100で生成した第1の乱数a及び第2の乱数αを作用させて第1の送信データを生成する。具体的には、CPU50は、秘密情報aに第1の乱数aを加算して得られた結果に、第2の乱数αを乗算することによって暗号化した第1の送信データ(α(a+a))を生成する。ステップS104で、CPU50は、ステップS102で生成した第1の送信データを受信装置44に送信する。

【0142】
ステップS106で、CPU50は、秘密鍵を用いて、第3の乱数a及び第4の乱数αを生成する。ステップS108で、CPU50は、秘密情報aに対して、ステップS102における第1の乱数aに代えた第3の乱数a及び第2の乱数αに代えた第4の乱数αを同様に作用させて第2の送信データを生成する。具体的には、CPU50は、秘密情報aに第3の乱数aを加算して得られた結果に、第4の乱数αを乗算することによって暗号化した第2の送信データ(α(a+a))を生成する。ステップS110で、CPU50は、ステップS108で生成した第2の送信データを、第1の送信データの送信先と同一の受信装置44に送信する。ステップS110の処理が終了すると、本送信処理が終了する。

【0143】
次に、図16を参照して、図15に示す送信処理によって送信された情報を受信する受信処理を説明する。受信装置44のCPU60が受信プログラム68を実行することで、図16に示す受信処理を実行する。

【0144】
図16のステップS120で、CPU60は、送信処理のステップS104で送信装置42から送信された第1の送信データを受信する。ステップS122で、CPU60は、送信装置42が記憶している秘密鍵と同一の秘密鍵を用いて、第1の乱数a及び第2の乱数αを生成する。

【0145】
ステップS124で、CPU60は、ステップS120で受信した第1の送信データから、ステップS122で生成した第2の乱数αを排除する。具体的には、CPU60は、第1の送信データを第2の乱数αで除算する。すなわち、第1の送信データから第2の乱数αを排除した結果は、α(a+a)/αで表される。

【0146】
ステップS126で、CPU60は、送信処理のステップS110で送信装置42から送信された第2の送信データを受信する。ステップS128で、CPU60は、送信装置42が記憶している秘密鍵と同一の秘密鍵を用いて、第3の乱数a及び第4の乱数αを生成する。

【0147】
ステップS130で、CPU60は、ステップS126で受信した第2の送信データから、ステップS128で生成した第4の乱数αを排除する。具体的には、CPU60は、第2の送信データを第4の乱数αで除算する。すなわち、第2の送信データから第4の乱数αを排除した結果は、α(a+a)/αで表される。

【0148】
ステップS132で、CPU60は、ステップS124による排除結果と、ステップS130による排除結果との差分を算出する。この差分は、以下に示す(28)式で表される。
α(a+a)/α-α(a+a)/α・・・(28)

【0149】
そして、CPU60は、算出した差分が、ステップS122で生成した第1の乱数aと、ステップS128で生成した第3の乱数aとの差分(a-a)に等しいか否かを検証する。具体的には、CPU60は、(28)式で算出した差分が、第1の乱数aと第3の乱数aとの差分に等しい場合、受信したデータが正しいと判断し、秘密情報aを復号する。一方、CPU60は、(28)式で算出した差分が、第1の乱数aと第3の乱数aとの差分とは異なる場合、受信したデータに改ざんや偽造等の不正があると判断し、例えば、エラーメッセージを表示装置63に表示する。ステップS132の処理が終了すると、本受信処理が終了する。

【0150】
本実施形態において、攻撃者が、偽の第1の送信データとしてα(a+a)+Δを受信装置44に受信させ、偽の第2の送信データとしてα(a+a)+Δを受信装置44に受信させることができる。しかしながら、攻撃者はa、α、a、αを知ることはできないため、(28)式で表される差分とa-aとが等しくなるような偽の送信データを生成することはできない。従って、受信装置44は、受信したデータの正当性を検証することができる。

【0151】
なお、上記各実施形態でCPUがソフトウェア(プログラム)を実行することにより実行した各種処理を、CPU以外の各種のプロセッサが実行してもよい。この場合のプロセッサとしては、FPGA(Field-Programmable Gate Array)等の製造後に回路構成を変更可能なPLD(Programmable Logic Device)、及びASIC(Application Specific Integrated Circuit)等の特定の処理を実行させるために専用に設計された回路構成を有するプロセッサである専用電気回路等が例示される。また、各種処理を、これらの各種のプロセッサのうちの1つで実行してもよいし、同種又は異種の2つ以上のプロセッサの組み合わせ(例えば、複数のFPGA、及びCPUとFPGAとの組み合わせ等)で実行してもよい。また、これらの各種のプロセッサのハードウェア的な構造は、より具体的には、半導体素子等の回路素子を組み合わせた電気回路である。

【0152】
また、上記第1~第4実施形態では、生成プログラム28が記憶部22に予め記憶(インストール)されている態様を説明したが、これに限定されない。生成プログラム28は、CD-ROM(Compact Disc Read Only Memory)、DVD-ROM(Digital Versatile Disc Read Only Memory)、及びUSB(Universal Serial Bus)メモリ等の記録媒体に記録された形態で提供されてもよい。また、生成プログラム28は、ネットワークを介して外部装置からダウンロードされる形態としてもよい。

【0153】
また、上記第1~第4実施形態では、復元プログラム38が記憶部32に予め記憶(インストール)されている態様を説明したが、これに限定されない。復元プログラム38は、CD-ROM、DVD-ROM、及びUSBメモリ等の記録媒体に記録された形態で提供されてもよい。また、復元プログラム38は、ネットワークを介して外部装置からダウンロードされる形態としてもよい。

【0154】
また、上記第5実施形態では、送信プログラム58が記憶部52に予め記憶(インストール)されている態様を説明したが、これに限定されない。送信プログラム58は、CD-ROM、DVD-ROM、及びUSBメモリ等の記録媒体に記録された形態で提供されてもよい。また、送信プログラム58は、ネットワークを介して外部装置からダウンロードされる形態としてもよい。

【0155】
また、上記第5実施形態では、受信プログラム68が記憶部62に予め記憶(インストール)されている態様を説明したが、これに限定されない。受信プログラム68は、CD-ROM、DVD-ROM、及びUSBメモリ等の記録媒体に記録された形態で提供されてもよい。また、受信プログラム68は、ネットワークを介して外部装置からダウンロードされる形態としてもよい。
【符号の説明】
【0156】
10 秘密分散システム
12 生成装置
14 復元装置
16 サーバ
20、30、50、60 CPU
21、31、51、61 メモリ
22、32、52、62 記憶部
28 生成プログラム
38 復元プログラム
40 通信システム
42 送信装置
44 受信装置
58 送信プログラム
68 受信プログラム
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15