(57)【特許請求の範囲】
【請求項１】
プロセッサを含む演算装置における同型暗号文処理方法において、
前記プロセッサが、同型暗号文に適用しようとする演算関数に対応する近似多項式を算出するステップと、
前記プロセッサが、前記近似多項式を用いて前記同型暗号文を近似演算処理するステップと
を含み、
前記演算関数は、Ｓｉｎ関数を含み、
前記近似多項式は、加算及び乗算からなる多項式で繰り返し（ｒｅｃｕｒｓｉｖｅ）演算を行うと、前記Ｓｉｎ関数との演算結果の差が予め設定された値以下になる多項式である同型暗号文処理方法。
【請求項２】
前記近似演算によって獲得された演算結果暗号文に対する後続演算を行う場合、前記演算結果暗号文内の近似メッセージ割合が予め設定された値を超過すると、前記演算結果暗号文の平文空間を拡張するステップを更に含むことを特徴とする請求項１に記載の同型暗号文処理方法。
【請求項３】
前記平文空間を拡張するステップは、
暗号化された入力値を予め設定された閾値暗号文モジュラスで除算した商を求めて除去するように定義された関数を、前記演算結果暗号文に適用して前記平文空間を拡張することを特徴とする請求項２に記載の同型暗号文処理方法。
【請求項４】
前記予め設定された値は、早期リブート（ｅａｒｌｙ  ｒｅｂｏｏｔｉｎｇ）のために、所定値未満に設定され、前記所定値は、前記演算結果暗号文に対する後続演算ができなくなる前記平文空間の大きさであることを特徴とする請求項２に記載の同型暗号文処理方法。
【請求項５】
前記プロセッサが、前記演算結果暗号文の復号に使われる付加情報を前記演算装置内のメモリに保存するステップを更に含み、
前記付加情報は、
スケーリングファクタ及び前記演算結果暗号文のモジュラス値を含むことを特徴とする請求項２に記載の同型暗号文処理方法。
【請求項６】
同型暗号文を入力されるためのインターフェースと、
前記同型暗号文を保存するメモリと、
前記同型暗号文に適用しようとする演算関数に対応する近似多項式を算出し、前記近似多項式を用いて前記同型暗号文を近似演算処理するプロセッサと
を含み、
前記演算関数は、Ｓｉｎ関数を含み、
前記近似多項式は、加算及び乗算からなる多項式で繰り返し（ｒｅｃｕｒｓｉｖｅ）演算を行うと、前記Ｓｉｎ関数との演算結果の差が予め設定された値以下になる多項式である演算装置。
【請求項７】
前記プロセッサは、
前記近似演算によって獲得された演算結果暗号文に対する後続演算を行う場合、前記演算結果暗号文内の近似メッセージ割合が予め設定された値を超過すると、前記演算結果暗号文の平文空間を拡張することを特徴とする請求項６に記載の演算装置。
【請求項８】
前記プロセッサは、
暗号化された入力値を予め設定された閾値暗号文モジュラスで除算した商を求めて除去するように定義された関数を、前記演算結果暗号文に適用して前記平文空間を拡張することを特徴とする請求項７に記載の演算装置。
【請求項９】
前記予め設定された値は、早期リブート（ｅａｒｌｙ  ｒｅｂｏｏｔｉｎｇ）のために、所定値未満に設定されて前記メモリに保存され、
前記所定値は、前記演算結果暗号文に対する後続演算ができなくなる前記平文空間の大きさであることを特徴とする請求項７に記載の演算装置。
【請求項１０】
前記プロセッサは、
前記演算結果暗号文の復号に使われる付加情報を前記メモリに保存し、
前記付加情報は、
スケーリングファクタ及び前記演算結果暗号文のモジュラス値を含むことを特徴とする請求項７に記載の演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号文に対する近似演算を効率的に行うための装置及び方法に関する。
【背景技術】
【０００２】
通信技術が発達して電子装置の普及が進むにつれ、電子装置間の通信セキュリティを保持するための取り組みが持続的に進められている。それにより、多くの通信環境では、暗号化／復号技術が使われている。
【０００３】
暗号化技術によって暗号化されたメッセージが相手に転送されると、相手はメッセージを利用するためには、復号を行わなければならない。この場合、相手は、暗号化されたデータを復号する過程でリソース及び時間の無駄遣いを強いられるようになる。なお、相手が演算のために、一時的にメッセージを復号した状態で第三者のハッキングが行われる場合、そのメッセージが第三者に容易に流出しかねないという問題もあった。
【０００４】
このような問題を解決するために、同型暗号化方法が研究されている。同型暗号化によると、暗号化された情報を復号せずに、暗号文そのもので演算を行っても、平文に対して演算してから暗号化された値と同じ結果を得ることができる。よって、暗号文を復号していない状態で各種演算を行うことができる。
【０００５】
しかし、同型暗号文を演算に数回繰り返し使用する場合、その暗号文内の平文の領域が足りなくなり、それ以上の演算を行うことができなくなるという問題があった。それにより、効率的なデータ処理方法が求められるようになっている。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、同型暗号文に対する効率的な近似演算及び近似復号を行うことができる方法及びその装置を提供することにある。
【課題を解決するための手段】
【０００７】
本発明は、以上のような目的を達成するためのものとして、本発明の一実施形態に係る同型暗号文処理方法は、プロセッサを含む演算装置における同型暗号文処理方法において、前記プロセッサが、同型暗号文に適用しようとする演算関数に対応する近似多項式を算出するステップと、前記プロセッサが、前記近似多項式を用いて前記同型暗号文を近似演算処理するステップとを含み、前記演算関数は、Ｓｉｎ関数を含み、前記近似多項式は、加算及び乗算からなる多項式で繰り返し（ｒｅｃｕｒｓｉｖｅ）演算を行うと、前記Ｓｉｎ関数との演算結果の差が予め設定された値以下になる多項式である。
【０００８】
ここで、前記近似多項式を算出するステップは、前記演算関数が復号関数である場合、前記演算関数との差の絶対値が閾値以下になるように前記近似多項式を算出してよい。
【０００９】
また、前記近似演算によって獲得された演算結果暗号文に対する後続演算を行う場合、前記演算結果暗号文内の近似メッセージ割合が閾値を超過すると、前記演算結果暗号文の平文空間を拡張するステップを更に含んでよい。
【００１０】
ここで、前記平文空間を拡張するステップは、暗号化された入力値を予め設定された閾値暗号文モジュラスで除算した商を求めて除去するように定義された関数を、前記演算結果暗号文に適用して前記平文空間を獲得してよい。
【００１１】
なお、前記閾値は、早期リブート（ｅａｒｌｙ  ｒｅｂｏｏｔｉｎｇ）のために、限界値未満の値に設定され、前記限界値は、前記演算結果暗号文に対する後続演算ができなくなる前記平文空間の大きさであってよい。
【００１２】
以上のような方法において、前記演算結果暗号文の復号に使われる付加情報を提供するステップを更に含んでよい。ここで、付加情報は、演算過程で変更されたスケーリングファクタ及び前記平文空間の拡張に使われたモジュラス値を含んでよい。
【００１３】
一方、本発明の一実施形態に係る演算装置は、同型暗号文を入力されるためのインターフェースと、前記同型暗号文を保存するメモリと、前記同型暗号文に適用しようとする演算関数に対応する近似多項式を算出し、前記近似多項式を用いて前記同型暗号文を近似演算処理するプロセッサとを含み、前記演算関数は、Ｓｉｎ関数を含み、前記近似多項式は、加算及び乗算からなる多項式で繰り返し（ｒｅｃｕｒｓｉｖｅ）演算を行うと、前記Ｓｉｎ関数との演算結果の差が予め設定された値以下になる多項式であってもよい。
【００１４】
前記プロセッサは、前記演算関数が復号関数である場合、前記近似多項式と前記演算関数との差の絶対値が閾値以下になるように前記近似多項式を設定して前記近似演算を行い、前記近似演算によって獲得された演算結果暗号文内の平文空間を拡張してよい。
【００１５】
ここで、前記プロセッサは、前記近似演算によって獲得された演算結果暗号文に対する後続演算を行う場合、前記演算結果暗号文内の近似メッセージ割合が閾値を超過すると、前記演算結果暗号文の平文空間を拡張してよい。
【００１６】
前記閾値は、早期リブート（ｅａｒｌｙ  ｒｅｂｏｏｔｉｎｇ）のために、限界値未満の値に設定され、前記メモリに保存され、前記限界値は、前記演算結果暗号文に対する後続演算ができなくなる前記平文空間の大きさであってよい。
【００１７】
なお、前記プロセッサは、前記演算結果暗号文の復号に使われる付加情報を前記メモリに保存し、前記付加情報は、演算過程で変更されたスケーリングファクタ及び前記平文空間の拡張に使われたモジュラス値を含んでよい。
【発明の効果】
【００１８】
以上説明したように、本発明によれば、同型暗号文に対する効率的な近似演算及び近似復号を行うことができるようになる。
【図面の簡単な説明】
【００１９】
【図１】本発明の一実施形態に係るデータ処理システムを説明するためのブロック図である。
【００２０】
【図２】本発明の一実施形態に係る暗号化装置の構成を示すブロック図である。
【００２１】
【図３】本発明の一実施形態に係る演算装置の構成を示すブロック図である。
【００２２】
【図４】演算装置の動作を説明するための図である。
【００２３】
【図５】図１のデータ処理システムの動作を説明するための図である。
【００２４】
【図６】本発明の一実施形態に係る同型暗号文処理方法を説明するためのフローチャートである。
【発明を実施するための形態】
【００２５】
以下では、添付の図面を参照して、本発明について詳細に説明する。本明細書で行う情報（データ）伝送過程は、必要に応じて、暗号化／復号が適用されてよく、本明細書及び特許請求の範囲で情報（データ）伝送過程を説明する表現は、格別に言及しなくても、全て暗号化／復号する場合も含むものとして解釈されるべきである。本明細書で「ＡからＢに伝送（伝達）」又は「ＡがＢから受信」というような形態の表現は、中間に別の媒体が含まれて伝送（伝達）又は受信されることも含み、必ずしもＡからＢに直接伝送（伝達）又は受信されることのみを表現するものではない。
【００２６】
本発明の説明において、各ステップの順番は、先行ステップが論理的及び時間的に必ずしも後行ステップの前に行われなければならない場合ではなければ、各ステップの順番は非制限的に理解されるべきである。即ち、上記のような例外的な場合を除いては、後行ステップとして説明された過程が先行ステップとして説明された過程より前に行われたとしても、発明の本質には影響がなく、権利範囲もステップの順番によらず定義されるべきである。そして、本明細書で「Ａ又はＢ」と記載したのは、ＡとＢのうちいずれかを選択的に指すだけでなく、ＡとＢの両方を含むことも意味するものとして定義される。なお、本明細書で「含む」という用語は、含むものとして並び立てられた用語の他に、更に別の構成要素を更に含むことも包括する意味を有する。
【００２７】
本明細書においては、本発明の説明に必要な構成要素のみを説明し、本発明の本質に関係のない構成要素については、言及しない。そして、言及される構成要素のみを含む排他的な意味として解釈されてはならず、他の構成要素も含むことができる非排他的な意味として解釈されるべきである。
【００２８】
そして、本明細書において「値」とは、スカラー値だけでなく、ベクトルも含む概念として定義される。
【００２９】
後述の本発明の各ステップの数学的な演算及び算出は、当該演算又は算出を行うために公知となっているコーディング方法及び／又は本発明に適するように考案されたコーディングによってコンピュータ演算で実現されてよい。
【００３０】
以下で説明する具体的な数学式は、可能な複数の代案ののうち例示的に説明されるものであり、本発明の権利範囲が本明細書に言及された数学式に制限されるものとして解釈されてはならない。
【００３１】
以下では、添付の図面を用いて、本発明の多様な実施形態について具体的に説明する。
【００３２】
図１は、本発明の一実施形態に係るデータ処理システムの構成を示す図である。図１によると、データ処理システムは、複数の装置１００−１〜１００−３及び演算装置２００を含む。図１においては、３つの装置を含むものとして示しているが、それは、使用例によって異なることがある。例えば、一つの装置だけで実現されてよく、３つ以上の装置で実現されてよい。
【００３３】
各装置１００−１〜１００−３及び演算装置２００は、携帯電話、タブレット、ゲームプレーヤ、パソコン、ラップトップパソコン、ホームサーバ、キオスク端末などのような多様な装置で実現されてよく、その他に、ＩｏＴ機能が適用された家電製品で実現されてよい。
【００３４】
第１装置１００−１及び第２装置１００−２は、それぞれ同型暗号化を行い、その結果値である同型暗号文を演算装置２００に提供する。ここで、同型暗号文は、それぞれ誤差を含む近似メッセージに対する同型暗号文を意味する。
【００３５】
具体的には、第１及び第２装置１００−１、１００−２から生成する同型暗号文は、後で秘密鍵を用いて復号した際、メッセージ及び誤差値を含む結果値が復元される形態で生成されてよい。以下、本明細書においては、メッセージに誤差が含まれた状態を近似メッセージという。
【００３６】
第１及び第２装置１００−１、１００−２は、それぞれ伝送しようとするメッセージが入力されると、誤差を含む近似メッセージに対する同型暗号文を生成する。
【００３７】
一例として、第１及び第２装置１００−１、１００−２のそれぞれは、自主的に生成した誤差をメッセージに含めて近似メッセージを作ることができる。具体的には、伝送するメッセージＭが入力されると、第１及び第２装置１００−１、１００−２のそれぞれは、任意の多項式ｃ１をランダムに生成し、小さな誤差ｅを生成した後、ｃ０＝  −ｃ１＊ｓ＋Ｍ＋ｅ（ｍｏｄ  ｑ）を計算し、同型暗号文Ｅ（ｍ，ｓ）＝ｃｔ＝（ｃ０，ｃ１）を生成する。後でそれを復号することになると、Ｄｅｃ（ｃｔ）＝Ｍ＋ｅ（ｍｏｄ  ｑ）になることが分かる。
【００３８】
別の例として、第１及び第２装置１００−１、１００−２のそれぞれがメッセージを同型暗号化する過程で誤差が追加され、近似メッセージの形態であってよい。具体的には、第１及び第２装置１００−１、１００−２のそれぞれが生成する同型暗号文は秘密鍵を用いて復号した際、次のような性質を満たす形態で生成される。
【００３９】
（数式１）
【００４０】
Ｄｅｃ（ｃｔ，ｓｋ）  ＝  ＜ｃｔ，ｓｋ＞  ＝  Ｍ＋ｅ（ｍｏｄ  ｑ）
【００４１】
ここで、＜，＞は、内積（ｕｓｕａｌ  ｉｎｎｅｒ  ｐｒｏｄｕｃｔ）、ｃｔは暗号文、ｓｋは秘密鍵、Ｍは平文メッセージ、ｅは暗号化誤差値、ｑは暗号文の除数（モジュラス（Ｍｏｄｕｌｕｓ））を意味する。
【００４２】
演算装置２００は、受信された同型暗号文に対する演算を行う。演算の種類は、多様に設定されてよい。同型暗号文の性質上、演算装置２００は復号をしていない状態で演算を行うことができ、その結果値も暗号文の形態になる。本明細書においては、演算によって獲得された結果値を演算結果暗号文という。演算装置２００は、演算結果暗号文を第３装置１００−３に伝送する。第３装置１００−３は、受信された演算結果暗号文を復号し、各同型暗号文に含まれたデータの演算結果値を獲得することができる。
【００４３】
図１においては、第１及び第２装置で暗号化を行い、第３装置が復号を行う場合を示しているが、必ずしもそれに限られるものではない。例えば、演算装置２００は、演算結果値を第１及び第２装置のうち少なくとも一つに提供することもできる。なお、一つの装置、例えば、第１装置１００−１で２回の暗号化を行い、２つの同型暗号文を提供することもできる。
【００４４】
演算装置２００は、ユーザの要請によって、演算を数回行うことができる。この場合、毎回演算の度に獲得される演算結果暗号文内の近似メッセージ割合が異なるようになる。演算装置２００は、近似メッセージ割合が閾値を超過すると、演算結果暗号文内の平文空間を拡張する動作を行う。
【００４５】
演算装置２００は、暗号化された入力値を予め設定された閾値暗号文モジュラスで除算した商を求めて除去するように定義された関数を、演算結果暗号文に適用し、平文空間を拡張することができる。
【００４６】
具体的には、上述の数式１において、ｑがＭより小さい場合、Ｍ＋ｅ（ｍｏｄ  ｑ）はＭ＋ｅと異なる値を有するため、復号ができなくなる。よって、ｑ値は常にＭより大きく保持されなければならない。しかし、演算が進められることにより、ｑ値は次第に減少するようになる。平文空間の拡張とは、暗号文ｃｔをより大きいモジュラスを有する暗号文に変化させることを意味する。平文空間を拡張する動作は、他にリブート（ｒｅｂｏｏｔｉｎｇ）とすることもできる。リブートを行うことにより、暗号文は再び演算が可能な状態になってよい。
【００４７】
一方、図１においては、第１及び第２装置１００−１、１００−２において、それぞれ誤差を含む近似メッセージに対する同型暗号文を作り、演算装置２００に提供するものとして図示及び説明しているが、必ずしもそれに限るものではない。例えば、演算装置２００は、近似メッセージがでない、メッセージそのものに対する同型暗号文を入力されることもできる。
【００４８】
なお、演算装置２００は、入力された同型暗号文に対して近似演算を行うこともできる。近似演算とは、正確な演算式ではなく、それに類似する結果が得られる近似式を用いて演算を行うことを意味する。近似演算は、近似メッセージに対する同型暗号文だけでなく、通常のメッセージに対する同型暗号文に対しても適用されてよい。
【００４９】
近似演算のために、演算装置２００は適用しようとする演算関数に対応する近似多項式を算出する。演算関数が復号関数である場合、演算装置２００は演算関数との差の絶対値が閾値以下になるように近似多項式を算出することができる。この場合、近似演算によって、演算結果暗号文の平文空間が拡張されることができる。
【００５０】
もし、復号関数に対応する近似多項式ではない場合、近似演算によって獲得された演算結果暗号文に対する後続演算を行わなければならない場合、その演算結果暗号文内の近似メッセージ割合を閾値と比較し、閾値を超過した際、平文空間の拡張動作を行うこともできる。
【００５１】
以下において、各装置の構成及び動作について説明する。
【００５２】
図２は、本発明の一実施形態に係る暗号化装置の構成を示す。図１におけるシステムで、第１、第２装置１００−１、１００−２のように、同型暗号化を行う装置を、他には暗号化装置ということができる。
【００５３】
図２によると、暗号化装置１００は、プロセッサ１１０、メモリ１２０を含む。図２においては、暗号化動作に必要な最小限の構成のみを示しており、暗号化装置１００の種類によって多様な構成要素が更に追加されてよい。例えば、通信インターフェース、ディスプレイ部、入力手段などが更に含まれてよく、このような構成は、同型暗号化と直接関連性がないため、図示及び説明は省略する。
【００５４】
プロセッサ１１０は、伝送しようとするメッセージが入力されると、メモリ１２０に保存する。プロセッサ１１０は、メモリ１２０に保存された各種設定値及びプログラムを用いて、メッセージを同型暗号化する。この場合、公開鍵が使用されてよい。
【００５５】
プロセッサ１１０は、暗号化を行うのに必要な公開鍵を自主的に生成して使用することもでき、外部装置から受信して使用することもできる。一例として、復号を行う第３装置１００−３が公開鍵を他の装置に配布することができる。
【００５６】
自主的に鍵を生成する場合、プロセッサ１１０はＲｉｎｇ−ＬＷＥ技法を用いて公開鍵を生成することができる。具体的に説明すると、プロセッサ１１０は先ず各種パラメータ及びリングを設定し、メモリ１２０に保存する。パラメータの例としては、平文メッセージビットの長さ、公開鍵及び秘密鍵の大きさなどがあってよい。
【００５７】
リングは、次のような数式で表されてよい。
【００５８】
（数式２）
【００５９】
【数１】
0006964688.tif 000002
【００６０】
リング（Ｒｉｎｇ）とは、予め設定された係数を有する多項式の集合を意味する。一例として、リングは、係数がＺｑであるｎ次多項式の集合を意味する。数式２において、ｆ（ｘ）はｎ次多項式を意味する。具体的には、ｎがΦ（Ｎ）とすると、Ｎ次円分多項式（Ｎ−ｔｈ  ｃｙｃｌｏｔｏｍｉｃ  ｐｏｌｙｎｏｍｉａｌ）を意味する。（ｆ（ｘ））とは、ｆ（ｘ）で生成されるＺｑ[ｘ]のイデアル（ｉｄｅａｌ）を示す。Ｅｕｌｅｒ  ｔｏｔｉｅｎｔ関数Φ（Ｎ）とは、Ｎと互いに素であり、Ｎより小さい自然数の数を意味する。ΦＮ（ｘ）をＮ次円分多項式として定義すると、リングは次のような数式でも表されてよい。
【００６１】
（数式３）
【００６２】
【数２】
0006964688.tif 000003
【００６３】
秘密鍵（ｓｋ）は、次のように表されてよい。
【００６４】
（数式４）
【００６５】
【数３】
0006964688.tif 000004
【００６６】
ｓ（ｘ）は、小さい係数でランダムに生成した多項式を意味する。
【００６７】
プロセッサ１１０は、リングから第１ランダム多項式（ａ（ｘ））を算出する。第１ランダム多項式は、次のように表されてよい。
【００６８】
（数式５）
【００６９】
【数４】
0006964688.tif 000005
【００７０】
なお、プロセッサ１１０は、離散ガウシアン分布またはそれと統計的な距離が近い分布から誤差を抽出する。誤差は、次のような数式で表されてよい。
【００７１】
（数式６）
【００７２】
【数５】
0006964688.tif 000006
【００７３】
誤差まで算出されると、暗号化装置１００は第１ランダム多項式及び秘密鍵に誤差をモジュラー演算して第２ランダム多項式を算出することができる。第２ランダム多項式は、次のように表されてよい。
【００７４】
（数式７）
【００７５】
【数６】
0006964688.tif 000007
【００７６】
最終的に、公開鍵（ｐｋ）は、第１ランダム多項式及び第２ランダム多項式を含む形態で次のように設定される。
【００７７】
（数式８）
【００７８】
【数７】
0006964688.tif 000008
【００７９】
上述の鍵生成方法は一例に過ぎないため、必ずしもそれに限るものではなく、その他に、別の方法で公開鍵及び秘密鍵を生成することもできる。
【００８０】
プロセッサ１１０は、同型暗号文が生成されると、メモリ１２０に保存するか、ユーザからの要請または予め設定されたデフォルト命令に応じて同型暗号文を演算装置２００に伝送することができる。
【００８１】
図３は、本発明の一実施形態に係る演算装置２００の構成を示すブロック図である。図３によると、演算装置２００は、インターフェース２１０、プロセッサ２２０、メモリ２３０を含む。図２と同様に、図３の演算装置も多様な付加構成を更に含むこともできるが、本発明の動作に関連性がないか、微弱な部分は図示及び説明を省略する。
【００８２】
インターフェース２１０は、各種装置からデータ及び信号を受信するか送信するための構成である。具体的には、インターフェース２１０は、ＬＡＮ、無線ＬＡＮ、Ｗｉ−Ｆｉ（登録商標）、ブルートゥース（登録商標）、ＮＦＣ（Ｎｅａｒ  Ｆｉｅｌｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ）、Ｚｉｇｂｅｅ（登録商標）などのような様々な有無線通信インターフェースで実現されてよい。
【００８３】
プロセッサ２２０は、誤差を含む近似メッセージに対する同型暗号文がインターフェース２１０を介して入力されると、それをメモリ２３０に保存する。誤差を含まない通常のメッセージに対する同型暗号文が入力された場合でも、プロセッサ２２０はそれをメモリ２３０に保存する。
【００８４】
メモリ２３０は、同型暗号文だけでなく、各種プログラム及びデータを保存するための構成要素である。
【００８５】
プロセッサ２２０は、ユーザの要請又は予め設定された設定値に応じて、同型暗号文に対する演算を行う。この場合、同型暗号文に対する復号は行わない。演算の種類は、様々に設定されてよい。一例として、２つの同型暗号文に対する乗算値や平均値を要請されたなら、プロセッサ２２０は指定された２つの同型暗号文を乗算したり、乗算した後２で割るなどの演算を行うことができる。または、プロセッサ２２０は、近似演算を行うこともできる。
【００８６】
プロセッサ２２０は、演算によって獲得された演算結果暗号文内の近似メッセージ割合を確認する。プロセッサ２２０は、近似メッセージ割合が閾値を超過すると、演算結果暗号文の平文空間を拡張する。
【００８７】
具体的には、プロセッサ２２０は、予め設定された関数を演算結果暗号文に適用して平文空間を拡張することができる。プロセッサ２２０は、暗号化された入力値を予め設定された閾値暗号文モジュラスで除算した商を求めて除去するように定義された関数を使用することができる。閾値は、暗号化/復号の性能に適するように任意の値に設定され、メモリ２３０に保存されていてよい。一例として、閾値は、演算結果が平文空間の全てを占める際の割合、即ち１００％に設定されてよい。別の例として、平文空間を全て占める前にリブートを行うことができるように、即ち、早期リブートのために限界値未満の値に設定されることもできる。例えば、８０〜５０％程度の限界値が設定されていてよい。限界値は、演算結果暗号文に対する後続演算ができなくなる平文空間の大きさを意味する。
【００８８】
または、プロセッサ２２０は、同型暗号文に適用しようとする演算多項式に対応する近似多功式を算出し、算出された近似多項式を用いて演算結果暗号文を演算し、平文空間を拡張することもできる。この場合、演算多項式が復号関数なら、近似多項式は、演算多項式との差の絶対値が閾値以下になるように設定されてよい。一例として、復号関数は、次のように設定されてよい。
【００８９】
（数式９）
【００９０】
【数８】
0006964688.tif 000009
【００９１】
数式９の復号関数に含まれたモジュラス演算は、次のような方法で近似的に変えてよい。
【００９２】
（数式１０）
【００９３】
【数９】
0006964688.tif 000010
【００９４】
別の例として、モジュラス演算を再帰的（ｒｅｃｕｒｓｉｖｅ）方法で計算することもできる。この場合、モジュラス演算は、次のように表されてよい。
【００９５】
（数式１１）
【００９６】
【数１０】
0006964688.tif 000011
【００９７】
数式１１において、ｋは任意の整数である。Ｋは計算の精度やパラメータの特性によって変動してよい。
【００９８】
数式１１において、Ｓｋは、次のような４つの数式を用いて算出することができる。
【００９９】
（数式１２）
【０１００】
【数１１】
0006964688.tif 000012
【０１０１】
【数１２】
0006964688.tif 000013
【０１０２】
【数１３】
0006964688.tif 000014
【０１０３】
【数１４】
0006964688.tif 000015
【０１０４】
ここで、Ｓｋは、数式１１でのように、演算関数がＳｉｎ関数である際の近似多項式を意味する。
【０１０５】
なお、プロセッサ２２０は、演算結果暗号文が後で復号される際に、使用されなければならない付加情報をメモリ２３０に保存しておくこともできる。付加情報は、演算結果暗号文内における演算結果メッセージの位置、平文空間の拡張に使用されたモジュラス値などを含むことができる。
【０１０６】
プロセッサ２２０は、演算結果を要請した装置に対して、演算結果暗号文と付加情報とをインターフェース２１０を介して提供することもできる。
【０１０７】
図４は、演算装置の動作を具体的に説明するための図である。図４においては、２つの同型暗号文１０、２０に対する演算及びリブートの過程を示す。
【０１０８】
各同型暗号文１０、２０は、近似メッセージ領域１１、２１をそれぞれ含む。近似メッセージ領域１１、２１には、メッセージ及び誤差（ｍ１＋ｅ１，ｍ２＋ｅ２）が同時に含まれている。
【０１０９】
演算装置は、両同型暗号文１０、２０を入力値として、特定の演算を行う。演算結果暗号文３０は、各近似メッセージ間の演算結果（ｍ３＋ｅ３）が込まれた近似メッセージ領域３１を含む。演算結果が入力値より大きくなるにつれ、近似メッセージ領域も大きくなり、よって、残りの平文空間３２が小さくなる。このような演算が数回行われると、結局残りの平文空間３２がなくなるか、限界値より小さくなり、演算ができなくなる。このような状態と判断されると、演算装置２００はリブートを行う。
【０１１０】
リブートの行われた暗号文４０は、近似メッセージ領域４１が小さくなる代わりに、平文空間４２が拡張されていることが分かる。リブート前の暗号文内の近似メッセージ（ｍ３＋ｅ３）とリブート後の暗号文内の近似メッセージ（ｍ３’＋ｅ３’）には若干の差があるものの、誤差の大きさの差が小さいため、元のメッセージと比較した際に大差がなくなる。従来の暗号化／復号メカニズムの場合、復号後のデータが元の平文と同様になるように設計するが、本実施形態によると、ぴったり同じ平文の代わりに、近似メッセージが出力される。結果的に、安全性のために必要とする誤差と有効数字演算を通じて発生する誤差とを含んで一つのノイズとして扱うため、暗号化された状態で実数演算が可能となり、暗号化／復号の効率性を増大させることができる。
【０１１１】
図５は、本発明の一実施形態に係るデータ処理方法を説明するための図である。図５によると、第１装置１００−１及び第２装置１００−２は、それぞれメッセージｍ１、ｍ２を同型暗号化して同型暗号文ＥＬ（ｍ１’）、ＥＬ（ｍ２’）を出力する。演算装置２００は、同型暗号文ＥＬ（ｍ１’）、ＥＬ（ｍ２’）に対する演算を行い、演算結果暗号文ＥＬ−ｉ（ｍ３’）を出力する。ここで、Ｌは暗号文のモジュラスレベルを意味する。演算が繰り返されることにより、モジュラスレベルは持続的に減少するようになる。例えば、演算装置２００が暗号化された状態で行いたい演算のデプスがｉなら、モジュラスレベルはｉの分減少するようになる。それにより、モジュラスレベルが閾値未満に減少すると、同型暗号文に対するそれ以上の演算はできなくなる。
【０１１２】
図５においては、閾値をレベル１に設定している。それにより、レベル１の同型暗号文Ｅ１（ｍ４’）、Ｅ１（ｍ５’）は演算不可の状態であることが分かる。
【０１１３】
演算装置２００は、Ｅ１（ｍ４’）、Ｅ１（ｍ５’）をそれぞれリブートして、ＥＬ（ｍ４”）、ＥＬ（ｍ５”）を生成する。リブートによってモジュラスレベルはＬと略類似するレベルＬ’となり、近似メッセージもｍ４’、ｍ５’で略類似するｍ４”、ｍ５”のように変化する。
【０１１４】
演算装置２００は、リブートした暗号文を演算し、演算結果暗号文ＥＬ’−ｉ（ｍ６”）を第３装置１００−３に提供する。最終的に演算された演算結果暗号文は、次の数式のように表されてよい。
【０１１５】
（数式１３）
【０１１６】
【数１５】
0006964688.tif 000016
【０１１７】
第３装置１００−３は、演算結果暗号文を復号して近似メッセージｍ６”を獲得する。
【０１１８】
復号のために、第３装置１００−３は付加情報を利用することできる。上述のように、付加情報は、スケーリングファクタ及び演算結果暗号文のモジュラス値などを含むことができる。
【０１１９】
モジュラス値がΔ’なら、復号された近似メッセージはｍ６”／Δ’であってよい。それにより、実数平文が暗号化過程で整数化されているとしても、復号で再び実数により復旧されることがある。なお、付加情報内のモジュラス値は数式９でリング（Ｒ）のモジュラスとして使用されてよい。
【０１２０】
第３装置１００−３は、復号を通じて最終的にｍ６”を獲得することができるようになる。
【０１２１】
図６は、本発明の一実施形態に係る同型暗号文処理方法を説明するためのフローチャートである。図６によると、近似メッセージの同型暗号文が入力され、その暗号文に対する演算要請が入力されると、要請された演算を行う（Ｓ６１０）。一例として、演算は、乗算、除算、加算、減算などのような基本的な演算に設定することもできるが、必ずしもそれに限るものではない。具体的には、暗号化されたメッセージが複素数の場合、共役（ｃｏｎｊｕｇａｔｅ）演算が行われてよく、その他に統計やソーティングなどの演算も行われてよい。
【０１２２】
演算装置は、演算前に又は演算後に同型暗号文内の近似メッセージ割合が閾値を超過しているか否かを判断することができる（Ｓ６２０）。図６においては、演算後にすることを示しているが、必ずしもそれに限るものではない。判断の結果、閾値を超過すると判断されると、演算装置は平文空間を拡張するリブートを行う（Ｓ６３０）。それにより、演算が効率的に繰り返し行われてよい。
【０１２３】
演算装置は、その他に、演算結果暗号文の復号に使用される付加情報を提供するステップを更に行うこともできる。
【０１２４】
なお、上述のように、演算装置は、演算そのものを近似演算に置き換えることができる。この場合、演算装置は、同型暗号文に適用しようとする演算関数に対応する近似多項式を算出するステップ及び算出された近似多項式を用いて同型暗号文を近似演算するステップを順次に行うことができる。ここで、近似多項式は、演算関数が復号関数である場合、演算関数との差の絶対値が閾値以下になるように算出することができる。このような近似多項式を用いて近似演算を行うと、演算結果暗号文の平文空間が拡張されてよい。
【０１２５】
その他の場合には、近似演算によって獲得された演算結果暗号文に対する後続演算を行う場合、近似メッセージ割合が閾値を超過すると、平文空間を拡張することもできる。平文空間の拡張方法については、既に具体的に説明しているため、繰り返し説明は省略する。
【０１２６】
以上では、多様な実施形態をフローチャート及びブロック図を用いて説明してきた。各フローチャートに示したステップの順番は例示に過ぎず、状況によって順番が入れ替わってよい。なお、実施形態によっては、一部のステップが省略されたり追加されてよい。
【０１２７】
なお、以上のような多様な実施形態による暗号化方法、処理方法、復号方法、リブート方法、演算方法などは、その方法を行うためのプログラムコードの形態で記録媒体に保存されて配布されてよい。この場合、記録媒体の搭載された装置は、上述の多様な実施形態による動作を行うことができる。
【０１２８】
記録媒体は、ＲＯＭ、ＲＡＭ、メモリチップ、メモリカード、外付けハード、ハード、ＣＤ、ＤＶＤ，磁気ディスクまたは磁気テープなどのような多様なコンピュータ読み取り可能な媒体であってよい。
【０１２９】
以上、添付図面を参照しながら本発明の好適な実施形態について詳細に説明したが、本発明は以上の実施形態に限定されない。本発明の属する技術の分野における通常の知識を有する者であれば、特許請求の範囲に記載された技術的趣旨の範疇内において、各種の変更例又は修正例に想到し得ることは明らかであり、これらについても、当然に本発明の技術的範囲に属するものと了解される。
【図１】
0006964688.tif 000017
【図２】
0006964688.tif 000018
【図３】
0006964688.tif 000019
【図４】
0006964688.tif 000020
【図５】
0006964688.tif 000021
【図６】
0006964688.tif 000022