(57)【要約】暗号化方法が開示される。本方法によると、メッセージにスケーリングファクタを反映した後、公開鍵を用いて同型暗号文を生成することができる。生成された同型暗号文は、復号化した際、メッセージにスケーリングファクタを反映した値にエラー値を加算した結果値が復元される形態で生成される。それにより、暗号文状態で演算が可能な同型暗号文を効果的に生成することができる。
2020528232.tif 000002
【特許請求の範囲】
【請求項１】
端末装置の暗号化方法において、
スケーリングファクタを設定するステップと、
暗号化するメッセージに前記スケーリングファクタを反映した後、公開鍵を用いて暗号化して同型暗号文を生成するステップと
を含み、
前記同型暗号文は、復号化した際、前記メッセージに前記スケーリングファクタを反映した値にエラー値を加算した結果値が復元される形態である暗号化方法。
【請求項２】
前記同型暗号文のモジュラスは、
一つのスケーリングファクタのべき乗に設定されることを特徴とする請求項１に記載の暗号化方法。
【請求項３】
前記同型暗号文のモジュラスは、
複数の相互異なるスケーリングファクタを乗算した値であり、
前記複数の相互異なるスケーリングファクタは、類似範囲内で互いに素な値に設定されることを特徴とする請求項１に記載の暗号化方法。
【請求項４】
前記同型暗号文を生成するステップは、
離散ガウシアン分布又は前記離散ガウシアン分布と統計的な距離が近い分布からエラーを算出するステップと、
前記メッセージに前記スケーリングファクタを乗算して前記エラーを加算した後、前記公開鍵を用いて暗号化して前記同型暗号文を生成するステップと
を含むことを特徴とする請求項１に記載の暗号化方法。
【請求項５】
前記メッセージが複数のメッセージベクトルである場合、前記複数のメッセージベクトルを、並列的に暗号化することができる形態の多項式に変換するステップを更に含み、
前記同型暗号文を生成するステップは、前記多項式に前記スケーリングファクタを乗算した後、前記公開鍵を用いて同型暗号化することを特徴とする請求項１に記載の暗号化方法。
【請求項６】
サーバ装置の暗号文処理方法において、
個別的に暗号化された複数の同型暗号文を受信するステップと、
前記複数の同型暗号文に対して予め設定された演算を行うステップと、
前記演算によって算出された結果暗号文からノイズ領域を除去して有効領域のデータを抽出するステップと
を含み、
前記複数の同型暗号文のそれぞれは、メッセージにスケーリングファクタを乗算した後で暗号化した暗号文であり、
前記ノイズ領域は、前記スケーリングファクタの大きさに対応するように決定される暗号文処理方法。
【請求項７】
前記複数の同型暗号文のそれぞれが、複数のメッセージベクトルをパッキングした暗号文であり、前記複数の同型暗号文のそれぞれに含まれたメッセージベクトルを並列的に演算処理するステップを更に含むことを特徴とする請求項６に記載の暗号文処理方法。
【請求項８】
前記複数の同型暗号文に含まれた各メッセージベクトルの間の順番をローテーションさせるステップを更に含むことを特徴とする請求項７に記載の暗号文処理方法。
【請求項９】
前記メッセージが複素数である場合、前記複数の同型暗号文に対して共役（ｃｏｎｊｕｇａｔｉｏｎ）演算を行うステップを更に含むことを特徴とする請求項７に記載の暗号文処理方法。
【請求項１０】
端末装置において、
スケーリングファクタ及び公開鍵が保存されたメモリと、
暗号化するメッセージに前記スケーリングファクタを反映した後、前記公開鍵を用いて暗号化して同型暗号文を生成するプロセッサと、
前記同型暗号文を外部装置に伝送する通信部と
を含み、
前記同型暗号文は、復号化した際、前記メッセージに前記スケーリングファクタを反映した値にエラー値を乗算した結果値が復元される形態である端末装置。
【請求項１１】
前記メッセージ及び前記スケーリングファクタを入力されるための入力部を更に含み、
前記プロセッサは、前記入力部を介して入力された前記メッセージ及び前記スケーリングファクタを前記メモリに保存することを特徴とする請求項１０に記載の端末装置。
【請求項１２】
前記プロセッサは、
前記同型暗号文のモジュラスを前記スケーリングファクタのべき乗に設定し、前記メモリに保存することを特徴とする請求項１０に記載の端末装置。
【請求項１３】
前記プロセッサは、
前記同型暗号文のモジュラスを複数の相互異なるスケーリングファクタを乗算した値に設定し、前記メモリに保存し、
前記複数の相互異なるスケーリングファクタは、類似範囲内で互いに素な値に設定されることを特徴とする請求項１０に記載の端末装置。
【請求項１４】
前記プロセッサは、
離散ガウシアン分布又は前記離散ガウシアン分布と統計的な距離が近い分布からエラーを算出し、前記メッセージ及び前記スケーリングファクタを乗算した値に前記エラーを加算した後、前記公開鍵を用いて暗号化することを特徴とする請求項１０に記載の端末装置。
【請求項１５】
前記プロセッサは、
前記メッセージが複数のメッセージベクトルである場合、前記複数のメッセージベクトルを、並列的に暗号化することができる形態の多項式に変換し、
前記多項式に前記スケーリングファクタを乗算した後、前記公開鍵を用いて同型暗号化することを特徴とする請求項１０に記載の端末装置。
【請求項１６】
端末装置における暗号化方法において、
要素の間で加算と乗算が定義されており、加算と乗算に対して閉じている集合のうち、平文空間が実数の集合であるリング（Ｒｉｎｇ）を設定するステップと、
前記リングから秘密鍵を算出するステップと、
前記算出された秘密鍵に対応して公開鍵を算出するステップと、
メッセージに前記公開鍵を適用して同型暗号文を生成するステップと
を含む暗号化方法。
【請求項１７】
前記リングは、以下の数式を満たし、
2020528232.tif 000114
ａ（Ｘ）は、前記リングに属する多項式、Ｒは、平文空間が複素数であるリングであることを特徴とする請求項１６に記載の暗号化方法。
【請求項１８】
前記同型暗号文は、
加算又は乗算の演算に対してｏ（ｎ  ｌｏｇ  ｎ）複雑度（ｃｏｍｐｌｅｘｉｔｙ）を有することを特徴とする請求項１６に記載の暗号化方法。
【請求項１９】
前記リングから第１ランダム多項式を算出するステップと、
エラーを抽出するステップと、
前記第１ランダム多項式及び前記秘密鍵に前記エラーをモジュラ演算して第２ランダム多項式を算出するステップと
を更に含み、
前記公開鍵を算出するステップは、
前記第１ランダム多項式及び前記第２ランダム多項式を用いて前記公開鍵を算出することを特徴とする請求項１６に記載の暗号化方法。
【請求項２０】
前記同型暗号文を生成するステップは、
前記メッセージを前記リングに属する多項式で算出し、前記算出された多項式に前記公開鍵を適用して同型暗号文を生成することを特徴とする請求項１６に記載の暗号化方法。
【請求項２１】
前記生成された同型暗号文及び予め生成された同型暗号文に対し、加算及び乗算のうち少なくとも一つの演算を行うステップを更に含み、
前記演算を行うステップは、
前記生成された同型暗号文及び前記予め生成された同型暗号文のそれぞれを第１関数処理し、第１関数処理された同型暗号文の間で演算を行い、前記演算の行われた同型暗号文を前記第１関数に逆関数である第２関数処理することを特徴とする請求項１６に記載の暗号化方法。
【請求項２２】
前記第１関数は、
ＮＴＴ（Ｎｕｍｂｅｒ  Ｔｈｅｏｒｅｔｉｃ  Ｔｒａｎｓｆｏｒｍ）関数であることを特徴とする請求項２１に記載の暗号化方法。
【請求項２３】
前記同型暗号文は、復号化した際、前記メッセージにエラー値を加算した結果値が復元される形態であることを特徴とする請求項１６に記載の暗号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、同型暗号化を行う端末装置と、その暗号文を処理するサーバ装置及びその方法に関し、より詳細には、リングの平文空間を実数の空間に調整し、演算速度の向上した同型暗号文を生成する実数の平文に対する同型暗号化方法に関する。
【背景技術】
【０００２】
電子及び通信技術の発展により、多様な装置の間でデータを送受信して活用する多様なサービスがサポートされている。そのうち、一例として、ユーザが自分の個人情報などをサーバに保存しておき、自分の端末装置を用いてサーバの情報を用いるクラウドコンピューティングサービスも盛んに使われている。
【０００３】
このような環境では、データの流出を防止するためのセキュリティ技術の使用が必須である。よって、サーバは、暗号化されたデータを保存するようになる。この場合、サーバは、保存されたデータを検索したり、そのデータに基づいた一連の作業を行う度に、暗号化されたデータを復号化しなければならないため、リソース及び時間の無駄が生じるようになる。
【０００４】
なお、サーバで演算のために一時的に復号化した状態で第三者によってハッキングされる場合、個人情報が第三者に容易に流出されるおそれがあるという問題点もあった。
【０００５】
このような問題を解決するために、同型暗号化方法が研究されている。同型暗号化によると、暗号化された情報を復号化せずに暗号文そのもので演算を行うとしても、平文に対して演算した後で暗号化した値と同一の結果を得ることができる。よって、暗号文を復号化していない状態で各種演算を行うことができる。
【０００６】
しかし、従来の同型暗号化方法によって整数演算を行うと、平文のビット数が幾何級数的に増加し、演算にかかる時間が大幅に増加するという問題があった。
【０００７】
一方、従来の同型暗号化方式は、演算過程で平文の虚数部が大きくなるという短所があった。具体的に、従来の同型暗号化方式の複素数空間でメッセージを同型暗号化しているという点において、実数の空間のメッセージを同型暗号化する場合にも、虚数部にエラーが追加された。もし、同型暗号文に対する演算が繰り返される場合、虚数部のエラーが次第に大きくなるようになり、虚数部のエラーが大きくなりすぎると、以後の同型乗算演算過程で実際のメッセージに該当する実数部のメッセージが損なわれるおそれがある。
【０００８】
よって、暗号文の状態でも、演算速度を向上させることができ、演算過程で平文の虚数部が大きくなることを防ぐことができる方法が求められている。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、メッセージにスケーリングファクタを反映した後で暗号化して同型暗号文を生成する端末装置と、その暗号文を演算するサーバ装置及びその方法を提供し、リングの平文空間を実数の空間に調整し、演算速度の向上した同型暗号文を生成する実数の平文に対する同型暗号化方法を提供することにある。
【課題を解決するための手段】
【００１０】
以上のような目的を達成するために、本発明の一実施形態に係る端末装置の暗号化方法は、スケーリングファクタを設定するステップと、暗号化するメッセージに前記スケーリングファクタを反映した後、公開鍵を用いて暗号化して同型暗号文を生成するステップとを含む。ここで、前記同型暗号文は、復号化した際、前記メッセージに前記スケーリングファクタを反映した値にエラー値を加算した結果値が復元される形態であってよい。
【００１１】
そして、前記同型暗号文のモジュラスは、一つのスケーリングファクタのべき乗に設定されてよい。
【００１２】
又は、前記同型暗号文のモジュラスは、複数の相互異なるスケーリングファクタを乗算した値に設定されてよい。ここで、前記複数の相互異なるスケーリングファクタは、類似範囲内で互いに素な値に設定されてよい。
【００１３】
なお、前記同型暗号文を生成するステップは、離散ガウシアン分布又は前記離散ガウシアン分布と統計的な距離が近い分布からエラーを算出するステップと、前記メッセージに前記スケーリングファクタを乗算して前記エラーを加算した後、前記公開鍵を用いて暗号化して前記暗号文を生成するステップとを含んでよい。
【００１４】
又は、前記メッセージが複数のメッセージベクトルである場合、前記複数のメッセージベクトルを、並列的に暗号化することができる形態の多項式に変換するステップを更に含んでよい。この場合、前記同型暗号文を生成するステップは、前記多項式に前記スケーリングファクタを乗算した後、前記公開鍵を用いて同型暗号化してよい。
【００１５】
一方、本発明の一実施形態に係るサーバ装置の暗号文処理方法は、個別的に暗号化された複数の同型暗号文を受信するステップと、前記複数の同型暗号文に対して予め設定された演算を行うステップと、前記演算によって算出された結果暗号文からノイズ領域を除去して有効領域のデータを抽出するステップとを含む。ここで、前記複数の同型暗号文のそれぞれは、メッセージにスケーリングファクタを乗算した後で暗号化した暗号文であり、前記ノイズ領域は、前記スケーリングファクタの大きさに対応するように決定されてよい。
【００１６】
なお、前記複数の同型暗号文のそれぞれが、複数のメッセージベクトルをパッキングした暗号文であり、前記複数の暗号文のそれぞれに含まれたメッセージベクトルを並列的に演算処理するステップを更に含んでよい。
【００１７】
この場合、前記複数の暗号文に含まれた各メッセージベクトルの間の順番をローテーションさせるステップを更に含んでよい。
【００１８】
なお、前記メッセージが複素数である場合、前記複数の暗号文に対して共役（ｃｏｎｊｕｇａｔｉｏｎ）演算を行うステップを更に含んでよい。
【００１９】
本発明の一実施形態に係る端末装置は、スケーリングファクタ及び公開鍵が保存されたメモリと、暗号化するメッセージに前記スケーリングファクタを反映した後、前記公開鍵を用いて暗号化して同型暗号文を生成するプロセッサと、前記同型暗号文を外部装置に伝送する通信部とを含む。ここで、前記同型暗号文は、復号化した際、前記メッセージに前記スケーリングファクタを反映した値にエラー値を乗算した結果値が復元される形態であってよい。
【００２０】
なお、前記メッセージ及び前記スケーリングファクタを入力されるための入力部を更に含んでよい。前記プロセッサは、前記入力部を介して入力された前記メッセージ及び前記スケーリングファクタを前記メモリに保存してよい。
【００２１】
なお、前記プロセッサは、同型暗号文のモジュラスを前記スケーリングファクタのべき乗に設定し、前記メモリに保存してよい。
【００２２】
又は、前記プロセッサは、前記同型暗号文のモジュラスを複数の相互異なるスケーリングファクタを乗算した値に設定し、前記メモリに保存してよい。この場合、前記複数の相互異なるスケーリングファクタは、類似範囲内で互いに素な値に設定されてよい。
【００２３】
なお、前記プロセッサは、離散ガウシアン分布又は前記離散ガウシアン分布と統計的な距離が近い分布からエラーを算出し、前記メッセージ及び前記スケーリングファクタを乗算した値に前記エラーを加算した後、前記公開鍵を用いて暗号化してよい。
【００２４】
なお、前記プロセッサは、前記メッセージが複数のメッセージベクトルである場合、前記複数のメッセージベクトルを、並列的に暗号化することができる形態の多項式に変換し、前記多項式に前記スケーリングファクタを乗算した後、前記公開鍵を用いて同型暗号化してよい。
【００２５】
一方、以上のような目的を達成するために、本発明の一実施形態に係る端末装置の暗号化方法は、要素の間で加算と乗算が定義されており、加算と乗算に対して閉じている集合のうち、平文空間が実数の集合であるリング（Ｒｉｎｇ）を設定するステップと、前記リングから秘密鍵を算出するステップと、前記算出された秘密鍵に対応して公開鍵を算出するステップと、メッセージに前記公開鍵を適用して同型暗号文を生成するステップとを含んでよい。
【００２６】
この場合、前記リングは、以下の数式を満たすことができる。
2020528232.tif 000003
ここで、ａ（Ｘ）は、前記リングに属する多項式、Ｒは、平文空間が複素数であるリ
ングであってよい。
【００２７】
一方、前記同型暗号文は、加算又は乗算の演算に対してｏ（ｎ  ｌｏｇ  ｎ）複雑度（ｃｏｍｐｌｅｘｉｔｙ）を有してよい。
【００２８】
一方、本暗号化方法は、前記リングから第１ランダム多項式を算出するステップと、エラーを抽出するステップと、前記第１ランダム多項式及び前記秘密鍵に前記エラーをモジュラ演算して第２ランダム多項式を算出するステップとを含み、前記公開鍵を算出するステップは、前記第１ランダム多項式及び前記第２ランダム多項式を用いて前記公開鍵を算出してよい。
【００２９】
一方、前記同型暗号文を生成するステップは、前記メッセージを前記リングに属する多項式で算出し、前記算出された多項式に前記公開鍵を適用して同型暗号文を生成してよい。
【００３０】
一方、本暗号化方法は、前記生成された同型暗号文及び予め生成された同型暗号文に対し、加算及び乗算のうち少なくとも一つの演算を行うステップを更に含み、前記演算を行うステップは、前記生成された同型暗号文及び前記予め生成された同型暗号文のそれぞれを第１関数処理し、第１関数処理された同型暗号文の間で演算を行い、前記演算の行われた同型暗号文を前記第１関数に逆関数である第２関数処理してよい。
【００３１】
この場合、前記第１関数は、ＮＴＴ（Ｎｕｍｂｅｒ  Ｔｈｅｏｒｅｔｉｃ  Ｔｒａｎｓｆｏｒｍ）関数であってよい。
【００３２】
一方、前記同型暗号文は、復号化した際、前記メッセージにエラー値を加算した結果値が復元される形態であってよい。
【００３３】
一方、本発明の一実施形態に係る端末装置は、メッセージを保存するメモリと、要素の間で加算と乗算が定義されており、加算と乗算に対して閉じている集合のうち、平文空間が実数の集合であるリング（Ｒｉｎｇ）を設定し、前記リングから秘密鍵を算出し、前記算出された秘密鍵に対応して公開鍵を算出し、前記メモリに保存されたメッセージに前記公開鍵を適用して同型暗号文を生成するプロセッサとを含む。
【００３４】
この場合、前記リングは、以下の数式を満たすことができる。
2020528232.tif 000004
【００３５】
ここで、ａ（Ｘ）は、前記リングに属する多項式、Ｒは、平文空間が複素数であるリング。
【００３６】
一方、前記同型暗号文は、加算又は乗算の演算に対してｏ（ｎ  ｌｏｇｎ）複雑度（ｃｏｍｐｌｅｘｉｔｙ）を有してよい。
【００３７】
一方、前記プロセッサは、前記リングから第１ランダム多項式を算出し、エラーを抽出し、前記第１ランダム多項式及び前記秘密鍵に前記エラーをモジュラ演算して第２ランダム多項式を算出し、前記第１ランダム多項式及び前記第２ランダム多項式を用いて前記公開鍵を算出してよい。
【００３８】
一方、前記プロセッサは、前記メッセージを前記リングに属する多項式で算出し、前記算出された多項式に前記公開鍵を適用して同型暗号文を生成してよい。
【００３９】
一方、本プロセッサは、前記生成された同型暗号文及び予め保存された同型暗号文のそれぞれを第１関数処理し、第１関数処理された同型暗号文の間で加算及び乗算のうち、少なくとも一つの演算を行い、前記演算の行われた同型暗号文を前記第１関数に逆関数である第２関数処理してよい。
【００４０】
この場合、前記第１関数は、ＮＴＴ（Ｎｕｍｂｅｒ  Ｔｈｅｏｒｅｔｉｃ  Ｔｒａｎｓｆｏｒｍ）関数であってよい。
【発明の効果】
【００４１】
以上説明したように、本発明によれば、有効領域を含む同型暗号文を生成することができるようになるため、メッセージの損失を最小化しつつ、演算時間及び負担を軽減させることができるようになる。
【００４２】
そして、リングの平文空間を実数の空間に調整して同型暗号文を生成するため、演算過程で平文の虚数部が大きくなることを根本から防ぐことができ、従来のＨＥＡＡＮのような安全性、連想速度、メモリ（暗号文、鍵サイズ）を有すると同時に、倍もある並列実数演算をサポートすることができるようになる。
【図面の簡単な説明】
【００４３】
【図１】本発明の一実施形態に係るネットワークシステムの構造を説明するための図である。
【図２】本発明の一実施形態に係る端末装置及びサーバ装置の構成を示すブロック図である。
【図３】本発明の一実施形態に係る端末装置の暗号化方法を説明するためのフローチャートである。
【図４】本発明の一実施形態に係るサーバ装置の暗号文処理方法を説明するためのフローチャートである。
【図５】サーバ装置の暗号文処理方法の多様な例を説明するための図である。
【図６】サーバ装置の暗号文処理方法の多様な例を説明するための図である。
【図７】サーバ装置の暗号文処理方法の多様な例を説明するための図である。
【図８】本発明の一実施形態に係るネットワークシステムの暗号文処理方法を説明するための図である。
【図９】本発明の一実施形態に係るネットワークシステムの構成を説明するための図である。
【図１０】本発明の一実施形態に係る端末装置の概略的な構成を示すブロック図である。
【図１１】本発明の一実施形態に係る端末装置の具体的な構成を示すブロック図である。
【図１２】公開鍵及び秘密鍵の生成動作を説明するための図である。
【図１３】演算鍵の生成動作を説明するための図である。
【図１４】近似同型暗号文の生成及び復号動作を説明するための図である。
【図１５】同型暗号文の加算計算を説明するための図である。
【図１６】同型暗号文の乗算計算を説明するための図である。
【図１７】本発明の暗号化方法を説明するためのフローチャートである。
【図１８】本発明の一実施形態に係るネットワークシステムの暗号文処理方法を説明するための図である。
【発明を実施するための形態】
【００４４】
以下では、添付の図面を参照して、本発明について詳細に説明する。本明細書で行う情報（データ）伝送過程は、必要に応じて、暗号化／復号化が適用されてよく、本明細書及び特許請求範囲で情報（データ）伝送過程を説明する表現は、格別に言及しなくても、全て暗号化／復号化する場合も含むものとして解釈されるべきである。本明細書で「ＡからＢに伝送（伝達）」又は「ＡがＢから受信」というような形態の表現は、中間に別の媒介体が含まれて伝送（伝達）又は受信されることも含み、必ずしもＡからＢに直接伝送（伝達）又は受信されることのみを表現するものではない。
【００４５】
本発明の説明において、各ステップの順番は、先行ステップが論理的及び時間的に必ずしも後行ステップの前に行われなければならない場合ではなければ、各ステップの順番は非制限的に理解されるべきである。即ち、上記のような例外的な場合を除いては、後行ステップとして説明された過程が先行ステップとして説明された過程より前に行われたとしても、発明の本質には影響がなく、権利範囲もステップの順番によらず定義されるべきである。そして、本明細書で「Ａ又はＢ」と記載したのは、ＡとＢのうちいずれかを選択的に指すだけでなく、ＡとＢの両方を含むことも意味するものとして定義される。なお、本明細書で「含む」という用語は、含むものとして並び立てられた要素の他に、更に別の構成要素を更に含むことも包括する意味を有する。
【００４６】
本明細書においては、本発明の説明に必要な構成要素のみを説明し、本発明の本質に関係のない構成要素については、言及しない。そして、言及される構成要素のみを含む排他的な意味として解釈されてはならず、他の構成要素も含むことができる非排他的な意味として解釈されるべきである。
【００４７】
そして、本明細書において「値」とは、スカラー値だけでなく、ベクトルも含む概念として定義される。
【００４８】
後述の本発明の各ステップの数学的な演算及び算出は、当該演算又は算出を行うために公知となっているコーディング方法及び／又は本発明に適するように考案されたコーディングによってコンピュータ演算で実現されてよい。
【００４９】
以下で説明する具体的な数式は、可能ないくつかの代案のうち例示的に説明されるものであり、本発明の権利範囲が本明細書に言及された数式に制限されるものとして解釈されてはならない。
【００５０】
説明の便宜のために、本明細書では、次のように表記を定めることとする。
【００５１】
ａ←Ｄ：分布（Ｄ）に応じて要素（ａ）を選択する。
【００５２】
ｓ１、ｓ２∈Ｒ：Ｓ１、Ｓ２のそれぞれはＲ集合に属する要素である。
【００５３】
ｍｏｄ（ｑ）：ｑ要素でモジュラ（ｍｏｄｕｌａｒ）演算
【００５４】
2020528232.tif 000005
は、内部値を四捨五入する。
【００５５】
以下では、添付の図を用いて、本発明の多様な実施形態について具体的に説明する。
【００５６】
図１は、本発明の一実施形態に係るネットワークシステムの構成を示す図である。図１によると、複数の端末装置１００−１〜１００ｎ、第１サーバ装置２００、第２サーバ装置３００が、ネットワーク１０を介して相互接続されてよい。ネットワーク１０は、多様な有無線通信ネットワーク、放送通信ネットワーク、光通信ネットワーク、クラウドネットワークなどで実現されてよく、各装置は別途の媒介体のないＷｉ−Ｆｉ、ブルートゥース（登録商標）、ＮＦＣ（Ｎｅａｒ  Ｆｉｅｌｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ）などのような方式で接続されてよい。
【００５７】
図１においては、端末装置が複数１００−１〜１００−ｎであるとして示しているが、必ずしも複数の端末装置が使用されるわけではなく、一つの装置が使われてよい。一例として、端末装置１００−１〜１００−ｎは、携帯電話、タブレットパソコン、ゲームプレーヤ、パソコン、ラップトップパソコン、ホームサーバ、キオスク端末などのような多様な装置で実現されてよく、その他にＩｏＴ機能が適用された家電製品で実現されてよい。
【００５８】
ユーザは、自分が使う端末装置１００−１〜１００−ｎを介して多様な情報を入力することができる。入力された情報は、端末装置１００−１〜１００−ｎそのものに保存されてよいが、保存容量及びセキュリティなどを理由に外部装置に伝送されて保存されてよい。図１においては、第１サーバ装置２００は、このような情報を保存する役割を担い、第２サーバ装置３００は、第１サーバ装置２００に保存された情報の一部又は全部を用いる役割を担う。
【００５９】
各端末装置１００−１〜１００−ｎは、入力された情報を同型暗号化し、同型暗号文を第１サーバ装置２００に伝送する。第１サーバ装置２００は、伝送された同型暗号文を復号化せずに、暗号文の状態で保存することができる。
【００６０】
第２サーバ装置３００は、同型暗号文に対する特定の処理結果を第１サーバ装置２００に要求することができる。第１サーバ装置２００は、要求に応じて、特定の演算を行った後、その結果を第２サーバ装置３００に伝送する。一例として、二つの端末装置１００−１、１００−２が伝送した暗号文ｃｔ１、ｃｔ２が第１サーバ装置２００に保存された場合、第２サーバ装置３００は両端末装置１００−１、１００−２から提供された情報を合算した値を第１サーバ装置２００に要求することができる。第１サーバ装置２００は、要求に応じて、両暗号文を合算する演算を行った後、その結果値（ｃｔ１＋ｃｔ２）を第２サーバ装置３００に伝送することができる。
【００６１】
各端末装置は、同型暗号化を行う過程で算出される暗号化ノイズ、即ち、エラーを暗号文に含ませる。具体的には、各端末装置１００−１〜１００−ｎで生成する同型暗号文は、その後に秘密鍵を用いて復号化した際に、メッセージ及びエラー値を含む結果値が復元される形態で生成されてよい。
【００６２】
一例として、端末装置１００−１〜１００−ｎで生成する同型暗号文は、秘密鍵を用いて復号化した際、次のような性質を満たす形態で生成される。
【００６３】
（数式１）
Ｄｅｃ（ｃｔ，ｓｋ）  ＝  ＜ｃｔ，ｓｋ＞  ＝  ΔＭ＋ｅ（ｍｏｄ  ｑ）
【００６４】
ここで、＜及び＞は内積（ｕｓｕａｌ  ｉｎｎｅｒ  ｐｒｏｄｕｃｔ）、ｃｔは暗号文、ｓｋは秘密鍵、Ｍは平文メッセージ、ｅは暗号化エラー値、Δはスケーリングファクタ（ｓｃａｌｉｎｇ  ｆａｃｔｏｒ）、そしてｑは暗号文の除数（モジュラス（Ｍｏｄｕｌｕｓ））を意味する。ｑは、スケーリングファクタがメッセージに乗算された結果値ΔＭより大きく選択されなければならない。エラー値ｅの絶対値がΔＭに比べて十分に小さいと、暗号文の復号化値ΔＭ＋ｅは有効数字演算で元のメッセージを同一の精度に代替できる値である。復号化されたデータのうち、エラーは最下位のビット（ＬＳＢ）側に配置され、ΔＭは次下位のビット側に配置される。
【００６５】
メッセージの大きさが小さすぎるか大きすぎる場合、スケーリングファクタを用いてその大きさを調節することもできる。スケーリングファクタを使うと、整数形態のメッセージだけでなく、実数のメッセージまで暗号化することができるようになるため、活用性が大きく増大することができる。なお、スケーリングファクタを用いてメッセージの大きさを調節することで、演算が行われた後の暗号文でメッセージが存在する領域、即ち、有効領域の大きさも調節されてよい。
【００６６】
実施形態によって、暗号文のモジュラスｑは、様々に設定されて使われてよい。一例として、暗号文のモジュラスは、スケーリングファクタΔのべき乗ｑ＝ΔＬに設定されてよい。Δが２であると、ｑ＝２１０のような値に設定されてよい。
【００６７】
別の例として、暗号文のモジュラスは、複数の相互異なるスケーリングファクタを乗算した値に設定されてよい。各ファクタは、類似する範囲内の値、即ち、相互に似た大きさの値に設定される。具体的には、ｑ＝ｑ１  ｑ２  ｑ３・・・ｑｘに設定され、ｑ１，ｑ２，ｑ３，…，ｑｘのそれぞれは、スケーリングファクタΔと似た大きさであり、互いに素な値に設定される。スケーリングファクタを、このような方式で設定されると、ＣＲＴ（Ｃｈｉｎｅｓｅ  Ｒｅｍａｉｎｄｅｒ  Ｔｈｅｏｒｅｍ）によって全演算を複数のモジュラス演算に分離して進めることができるようになるため、演算の負担を軽減させることができる。なお、互いに似た大きさのファクタを使うことにより、後述のステップでラウンディング処理を行った際、上述の例における結果値と略同じ結果を得ることができる。
【００６８】
以上のように、各端末装置１００−１〜１００−ｎから生成した暗号文は、第１サーバ装置２００によって処理された後、暗号文の状態で第２サーバ装置３００に伝送される。第２サーバ装置３００は、伝送された暗号文を秘密鍵を用いて復号化する。同型暗号化処理が行われたため、復号化されたデータは、メッセージそのものを復号化した後で演算処理した結果と同じ結果になってよい。結果的に、中間過程で第三者に流出される危険性を防止することができるようになる。
【００６９】
図１の実施形態において、暗号化を行うのに使われる公開鍵は、各端末装置によって生成されてよく、復号化を行う第２サーバ装置３００で生成した後で各端末装置に配布することもできる。
【００７０】
鍵生成過程では、Ｒｉｎｇ−ＬＷＥ技法が使われてよい。第２サーバ装置３００が鍵を生成する場合に仮定すると、第２サーバ装置３００は各種パラメータ及びリングを設定する。具体的には、平文メッセージビットの長さ、公開鍵及び秘密鍵の大きさなどのような多様なパラメータを設定することができる。
【００７１】
リングは、次のような数式で表されてよい。
【００７２】
（数式２）
2020528232.tif 000006
【００７３】
リング（Ｒｉｎｇ）とは、予め設定された係数を有する多項式の集合を意味する。一例として、リングは係数がＺｑであるｎ次多項式の集合を意味する。数式２において、ｆ（ｘ）はｎ次多項式を意味する。具体的には、ｎがΦ（Ｎ）である際、Ｎ次円分多項式（Ｎ−ｔｈ  ｃｙｃｌｏｔｏｍｉｃ  ｐｏｌｙｎｏｍｉａｌ）を意味する。（ｆ（ｘ））とは、ｆ（ｘ）で生成されるＺｑ[ｘ]のイデアル（ｉｄｅａｌ）を表す。Ｅｕｌｅｒ  ｔｏｔｉｅｎｔ関数Φ（Ｎ）とは、Ｎと互いに素であり、Ｎより小さい自然数の数を意味する。ΦＮ（ｘ）をＮ次円分多項式に定義すると、リングは次のような数式でも表されてよい。
【００７４】
（数式３）
2020528232.tif 000007
【００７５】
次に、第２サーバ装置３００は、リングから秘密鍵（ｓｋ）を算出する。
【００７６】
（数式４）
2020528232.tif 000008
【００７７】
ｓ（ｘ）は、小さい係数でランダムに生成した多項式を意味する。
【００７８】
第２サーバ装置３００は、リングから第１ランダム多項式（ａ（ｘ））を算出する。第１ランダム多項式は、次のように表されてよい。
【００７９】
（数式５）
ａ（ｘ）  ←  Ｒ
【００８０】
なお、第２サーバ装置３００は、離散ガウシアン分布又はそれと統計的な距離が近い分布からエラーを算出する。エラーは、次のような数式で表されてよい。
【００８１】
（数式６）
2020528232.tif 000009
【００８２】
エラーまで算出されると、第２サーバ装置３００は、第１ランダム多項式及び秘密鍵にエラーをモジュラ演算して第２ランダム多項式を算出することができる。第２ランダム多項式は、次のように表されてよい。
【００８３】
（数式７）
ｂ（ｘ）  ＝  −ａ（ｘ）ｓ（ｘ）  ＋  ｅ（ｘ）  （ｍｏｄ  ｑ）
【００８４】
最終的に、公開鍵（ｐｋ）は、第１ランダム多項式及び第２ランダム多項式を含む形態で次のように設定される。
【００８５】
（数式８）
ｐｋ  ＝  （ｂ（ｘ），ａ（ｘ））
【００８６】
第２サーバ装置３００は、生成された公開鍵を各端末装置１００−１〜１００−ｎに伝送する。各端末装置１００−１〜１００−ｎは、受信された公開鍵を保存した後、暗号化の際に使う。
【００８７】
上述のような例においては、第２サーバ装置３００が公開鍵及び秘密鍵を生成するものとして説明しているが、別の例では、各端末装置１００−１〜１００−ｎ又はその他の装置が公開鍵及び秘密鍵のうち少なくとも一つを生成した後、他装置と共有することも可能である。なお、上述の鍵生成方法は一例に過ぎないため、必ずしもそれに限定されるものではなく、その他に別の方法で公開鍵及び秘密鍵を生成することができる。
【００８８】
図２は、本発明の一実施形態に係る端末装置１００及びサーバ装置２００の構成を示すブロック図である。
【００８９】
図２によると、端末装置１００は、メモリ１１０、プロセッサ１２０、通信部１３０を含む。
【００９０】
メモリ１１０は、端末装置１００を駆動するためのＯ／Ｓや各種ソフトウェア、データなどを保存するための構成要素である。メモリ１１０は、ＲＡＭやＲＯＭ、フラッシュメモリ、ＨＤＤ、外付けメモリ、メモリカードなどのような形態で実現されてよく、何れかに限定されるわけではない。
【００９１】
メモリ１１０は、公開鍵、スケーリングファクタなどを保存することができる。
【００９２】
プロセッサ１２０は、メモリ１１０に保存されたプログラムを実行させて各種演算作業を行うための構成要素である。
【００９３】
通信部１３０は、外部装置と通信を行うための構成要素である。通信部１３０は、Ｗｉ−Ｆｉ、Ｚｉｇｂｅｅ（登録商標）、ブルートゥース（登録商標）、ＮＦＣなどのような無線通信だけでなく、各種有線通信インターフェースを介した有線通信をサポートする形態でも実現されてよい。
【００９４】
プロセッサ１２０は、暗号化するメッセージにスケーリングファクタを反映した後、公開鍵を用いて暗号化して同型暗号文を生成する。プロセッサ１２０は、生成された同型暗号文を外部装置に伝送するように通信部１３０を制御することができる。
【００９５】
同型暗号文は、上述のような数式１のような性質を満たすように生成される。具体的に、プロセッサ１２０は、暗号化するメッセージＭにスケーリングファクタΔを乗算して整数又は整数係数の多項式であるΔＭを計算する。
【００９６】
その後、多項式ｖをランダムに決定する。プロセッサ１２０は、ｖを小さい分布（例えば、離散ガウシアン又はそれと類似する分布）から算出することができる。プロセッサ１２０は、エラーｅ０、ｅ１も小さいエラー分布（例えば、離散ガウシアン又はそれと類似する分布）から選ぶことができる。
【００９７】
プロセッサ１２０は、公開鍵ｐｋ  ＝  （ｂ（ｘ），ａ（ｘ））と、次のような数式を用いて暗号文を生成する。
【００９８】
（数式９）
2020528232.tif 000010
【００９９】
暗号化するメッセージは、外部ソースから受信することもでき、端末装置１００に直接備えるか又は接続された入力装置から入力されてよい。なお、スケーリングファクタもユーザが直接入力するか、別の装置を介して提供されることもできる。例えば、端末装置１００がタッチスクリーンやキーパッドを含む場合、プロセッサ１２０はユーザがタッチスクリーンやキーパッドを介して入力するデータをメモリ１１０に保存した後、暗号化することができる。生成された同型暗号文は、復号化した際にメッセージにスケーリングファクタを反映した値にエラーを加算した結果値に復元される形態であってよい。スケーリングファクタは、事前に入力されて設定された値をそのまま使うこともできる。
【０１００】
上述の暗号文のモジュラスｑは、実施形態によって異なるように設定されてよい。一例として、プロセッサ１２０は、暗号文モジュラスをスケーリングファクタΔのべき乗ｑ＝ΔＬで設定することができる。別の例として、プロセッサ１２０は、暗号文モジュラスを複数の相互異なるスケーリングファクタを乗算した値に設定することもできる。プロセッサ１２０は、設定した暗号文モジュラスをメモリ１１０に保存することもできる。上述のように、各ファクタは類似範囲内で互いに素な関係を有することができる。
【０１０１】
プロセッサ１２０は、公開鍵の暗号化のために、エラーを使うこともできる。エラーは、離散ガウシアン分布又は前記離散ガウシアン分布と統計的な距離が近い分布から算出することができる。一例として、上述の数式６のような形態のエラーを算出することができる。プロセッサ１２０は、メッセージが入力されると、スケーリングファクタをそのメッセージに乗算した値にエラーを加算した後、公開鍵を用いて暗号化することができる。この場合、暗号文を復号化した際に算出されるエラー値は、暗号化の際に加算した初期エラーと異なるように導出される。
【０１０２】
又は、メッセージ及びスケーリングファクタを乗算した状態で直ちに公開鍵を用いて暗号化することもできる。この場合、暗号化過程で算出されるエラーがメッセージ及びスケーリングファクタを乗算した結果値に加算されてよい。
【０１０３】
プロセッサ１２０は、暗号文の長さをスケーリングファクタの大きさに対応するように生成することができる。
【０１０４】
一方、本発明の一実施形態によると、パッキング（ｐａｃｋｉｎｇ）が行われてよい。同型暗号化でパッキングを用いるようになると、複数のメッセージを一つの暗号文で暗号化することが可能になる。この場合、第１サーバ装置２００で各暗号文の間の演算を行うようになると、結果的に複数のメッセージに対する演算が並列的に処理されるため、演算の負担を大幅に軽減するようになる。
【０１０５】
具体的には、プロセッサ１２０は、メッセージが複数のメッセージベクトルで行われる場合、複数のメッセージベクトルを並列的に暗号化できる形態の多項式に変換した後、その多項式にスケーリングファクタを乗算して公開鍵を用いて同型暗号化することもできる。それにより、複数のメッセージベクトルをパッキングした暗号文を生成することができる。
【０１０６】
具体的には、プロセッサ１２０は、Ｎ次円分多項式
2020528232.tif 000011
が複素数（
2020528232.tif 000012
）内で相互異なる
2020528232.tif 000013
個の根
2020528232.tif 000014
（ｐｒｉｍｉｔｉｖｅ  Ｎ−ｔｈ  ｒｏｏｔｓ  ｏｆ  ｕｎｉｔｙ）を有することを用いる。複素数概念を導入することで、後述のように、複数のメッセージを同時に同型暗号化することが可能である。
【０１０７】
次に、標準埋め込み関数（ｃａｎｏｎｉｃａｌ  ｅｍｂｅｄｄｉｎｇ  ｆｕｎｃｔｉｏｎ）を変形してパッキング関数（σ）を計算する。標準埋め込み関数は、多項式
2020528232.tif 000015
を
2020528232.tif 000016
の根
2020528232.tif 000017
の中で、複素数共役（ｃｏｍｐｌｅｘ  ｃｏｎｊｕｇａｔｅ）関係ではない（ｎ／２）個の根
2020528232.tif 000018
における値の対
2020528232.tif 000019
で対応させる関数である。その関数が同型関数（ｈｏｍｏｍｏｒｐｈｉｓｍ）であることは、この分野において通常の知識を有する者なら、容易に証明することができる。
【０１０８】
標準埋め込み関数を行列（Ｃ）で表現すると、次のようである。
【０１０９】
（数式１０）
2020528232.tif 000020
【０１１０】
多項式Ｍ（ｘ）を係数の列ベクトルＭ＝（Ｍ０，…，Ｍｎ−１）で表現すると、この多項式のパッキング関数
2020528232.tif 000021
とは
2020528232.tif 000022
関係、即ち、次のような関係を有するようになる。
【０１１１】
（数式１１）
2020528232.tif 000023
【０１１２】
このように、標準埋め込み関数を算出している状態で、プロセッサ１２０は、複数（例えば、ｎ／２個）のメッセージベクトル
2020528232.tif 000024
が入力されると、上述の標準埋め込み関数を用いてメッセージベクトルを多項式に変換する。
【０１１３】
（数式１２）
2020528232.tif 000025
【０１１４】
数式１２のような方式で変換された多項式Ｍ（ｘ）は、
2020528232.tif 000026
のような関係を満たす。
【０１１５】
プロセッサ１２０は、上述の方式で変換された多項式にスケーリングファクタを乗算した後、公開鍵を用いて同型暗号化することができる。一例として、同型暗号化方法の一つであるＲｉｎｇ  ＬＷＥ（Ｌｅａｒｎｉｎｇ  ｗｉｔｈ  Ｅｒｒｏｒｓ）方式を用いて同型暗号化することができる。
【０１１６】
具体的な暗号文は、次のような形態で表されてよい。
【０１１７】
（数式１３）
2020528232.tif 000027
【０１１８】
上述のように、端末装置１００が生成した同型暗号文は、第１サーバ装置２００に提供されてよい。第１サーバ装置２００は、端末装置１００から受信される同型暗号文を保存し、その後で演算過程で使うことができる。第１サーバ装置２００は、複数の相互異なる端末装置から伝送される複数の同型暗号文だけでなく、一つの端末装置１００から伝送される複数の同型暗号文に対しても演算処理を行うことができる。
【０１１９】
第１サーバ２００も、メモリ２１０、プロセッサ２２０、通信部２３０を含む形態で実現されてよい。
【０１２０】
通信部２３０は、端末装置１００から各種同型暗号文を受信することができる。各同型暗号文は、相互異なる端末装置又は一つの端末装置で個別的に暗号化されたデータを意味する。
【０１２１】
プロセッサ２２０は、受信された同型暗号文をメモリ２１０に保存する。図２では、メモリ２１０のみを示しているが、第１サーバ装置２００は大容量のデータを保存するための別途のストレージを更に含んでよく、それと別途に外部装置と接続され、その外部保存装置に各同型暗号文を保存することもできる。
【０１２２】
プロセッサ２２０は、複数の同型暗号文に対して予め設定された演算を行うことができる。行われる演算の種類は、第１サーバ装置２００の管理者によって直接選択されてよく、第２サーた装置３００から要求を受けることもできる。
【０１２３】
一例として、演算は乗算、除算、加算、減算などのような基本演算に設定されてよいが、必ずしもそれに限るものではない。具体的には、暗号化されたメッセージが複素数形態である場合、共役（ｃｏｎｊｕｇａｔｅ）演算が行われてよく、その他に統計やソーティングなどの演算も行われてよい。
【０１２４】
複数の同型暗号文のそれぞれが、複数のメッセージベクトルをパッキングした暗号文である場合には、プロセッサ２２０は、複数の暗号文のそれぞれに含まれた多項式の暗号文を並列的に演算処理することもできる。この場合、複数の暗号文の演算の順番をローテーションさせるか、ランダムに混ぜて演算を行うこともできる。第２サーバ装置２００の具体的な演算動作については、具体的に後述することとする。
【０１２５】
図２においては、端末装置１００及び第１サーバ装置２００がそれぞれ通信部、メモリ、プロセッサのみを含む形態で示しているが、必ずしもこのような構成に限定されるものではない。即ち、各装置の種類及び使用環境などに応じて、入力手段、ディスプレイ、バスなどのような多様な構成要素を更に含んでよい。一例として、端末装置１００は、伝送するメッセージやスケーリングファクタなどを入力されるための入力部（図示せず）を更に含んでよい。プロセッサ１２０は、入力部を介して入力されたメッセージ又はスケーリングファクタなどをメモリ１１０に保存することができる。なお、プロセッサ１２０は、入力されたスケーリングファクタを用いて上述の多様な方法で暗号文のモジュラスを設定した後、メモリ１１０に保存することもできる。
【０１２６】
図３は、本発明の一実施形態に係る端末装置の暗号化方法を説明するためのフローチャートである。
【０１２７】
図３によると、端末装置１００は、スケーリングファクタを設定する（Ｓ３１０）。スケーリングファクタの設定方法は、上述のように様々に実現されてよい。
【０１２８】
端末装置１００は、設定されたスケーリングファクタを保存する。端末装置１００は、暗号化するメッセージが発生すると、そのメッセージにスケーリングファクタを反映した後、公開鍵を用いて同型暗号化を行う（Ｓ３２０）。公開鍵は、端末装置１００が直接生成することもでき、外部装置から提供されることもできる。
【０１２９】
図４は、本発明の一実施形態に係るサーバ装置の暗号文処理方法を説明するためのフローチャートである。図１に示すように、暗号文処理は、第１サーバ装置で行われるため、以下では第１サーバ装置２００が行う方法で説明する。
【０１３０】
図４によると、第１サーバ装置２００は、複数の同型暗号文を受信する（Ｓ４１０）。各同型暗号文は、スケーリングファクタの適用された状態で公開鍵を用いて同型暗号化したデータを意味する。
【０１３１】
第１サーバ装置２００は、外部装置又は管理者から演算の要求が入力されると（Ｓ４２０）、複数の同型暗号文を対象に、要求された演算を行う（Ｓ４３０）。演算が完了すると、第１サーバ装置２００は、演算結果データから有効領域のデータを検出する（Ｓ４４０）。第１サーバ装置２００は、演算結果データをラウンディング処理を行って有効領域のデータを検出することができる。ラウンディング処理とは、暗号化された状態でメッセージの四捨五入（ｒｏｕｎｄ−ｏｆｆ）を行うことを意味し、リスケール（ｒｅｓｃａｌｉｎｇ）と呼ぶこともできる。具体的には、第１サーバ装置３００は、暗号文のそれぞれの成分にスケール因数の逆数であるΔ−１を乗算して四捨五入し、ノイズ領域を除去する。ノイズ領域は、スケーリングファクタの大きさに対応するように決定されてよい。結果的に、ノイズ領域の除去された有効領域のメッセージを検出することができる。暗号化状態で進められるため、更なるエラーが発生するが、大きさは十分に小さいため、無視することができる。
【０１３２】
図５は、図４の暗号文処理方法を具体的に説明するための模式図である。
【０１３３】
例えば、第１同型暗号文５１と第２同型暗号文５２とを対象に、乗算演算が要求された場合、第１サーバ装置２００は暗号文状態で乗算Ｓ５１０を進めて演算暗号文５３を生成する。算出された演算暗号文５３は、スケーリングファクタが反映されたメッセージ部（Δ２Ｍ１Ｍ２）とエラーデータ（ｅｍｕｌｔ）を含む。乗算過程でエラーデータの大きさが大きくなるが、後述のように、メッセージ部の大きさが縮小されるため、問題が発生しない。それは、加算に対しても、同様に作用する。
【０１３４】
次に、メッセージ部（Δ２Ｍ１Ｍ２）を有効数字に該当する部分、即ち、有効領域に大きさが縮小させ、最終の演算暗号文５４を生成する。上述のように、第２サーバ装置３００は演算暗号文５３に対してスケーリングファクタの逆数を乗算した後、ラウンディング処理する方式で、ノイズ領域を除去することができる。結果的に、有効領域に該当するデータ（（ΔＭ１Ｍ２）‘＋ｅ’）を含む最終の演算暗号文５４を生成することができる。このような処理過程によって更なるエラーが発生し、エラーデータ（ｅｍｕｌｔ）がｅ’に変更されるが、大きさは十分に小さいため、無視することができる。
【０１３５】
図６は、上記で説明したパッキング方法を通じて複数のメッセージを一つの暗号文に暗号化した場合、演算を行う方法を説明するための方法である。説明の便宜のために、複数のメッセージベクトルを暗号化した暗号文をパッキング暗号文と称する。図６によると、第１パッキング暗号文（ｃｔ）は、複数のメッセージ６１−１〜６１−ｋからなるベクトルを暗号化しており、第２パッキング暗号文（ｃｔ’）は、複数のメッセージ６２−１〜６２−ｋからなるベクトルを暗号化した暗号文である。
【０１３６】
第１サーバ装置２００は、第１パッキング暗号文（ｃｔ）と第２パッキング暗号文（ｃｔ’）に対する演算が要求されると、既に説明した実施形態などの方法で両暗号文の演算を行う。結果的に、一度の暗号文演算で複数のデータの並列処理が可能なＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）演算が行われてよい。
【０１３７】
図６によると、第１パッキング暗号文（ｃｔ）の一番目のメッセージ成分６１−１と第２パッキング暗号文ｃｔ’の一番目のメッセージ成分６２−１が乗算されるようになる。それと同時に、二番目のメッセージ成分６１−２、６２−２の乗算も行われる。結果的に、最終のパッキング暗号文（ｃｔｍｕｌｔ）は、同じ位置にあるメッセージ成分の乗算値からなるベクトル６３−１〜６３−ｋを暗号化した暗号文と理解することができる。
【０１３８】
図７は、ＳＩＭＤ演算を行ううえで、一部の同型暗号文の位置を変更して処理する方法を説明するための図である。図７によると、第１パッキング暗号文（ｃｔ）を用いて新たな第２パッキング暗号文（ｃｔ’）を生成することができる。このとき、第２パッキング暗号文の一番目の成分は、第１パッキング暗号文の二番目のメッセージ成分と同様になるように、第１パッキング暗号文（ｃｔ）をシフトさせる。それと同時に、第２パッキング暗号文の二番目の成分は、第１パッキング暗号文の三番目のメッセージ成分と同様になる。結果的に、第２パッキング暗号文は、第１パッキング暗号文の全メッセージ位置を移動させた新たなメッセージベクトルを暗号化したパッキング暗号文である。本明細書では、以上のように暗号文の位置を移動させる作業をローテーション処理とする。
【０１３９】
図８は、第１のネットワークシステムの動作を総合的に説明するためのシーケンス図である。図８では、二つの端末装置１００−１、１００−２から暗号文を伝送する場合を示している。
【０１４０】
まず、端末装置１（１００−１）で第１メッセージが入力されると（Ｓ８１０）、端末装置１（１００−１）は、上述の方式で第１同型暗号文を生成した後（Ｓ８１５）、第１サーバ装置２００に伝送することができる（Ｓ８２０）。一例として、端末装置１（１００−１）のユーザが写真を撮影した場合には、その写真及び撮影場所などが暗号化されてよく、ユーザが音楽コンテンツを再生するか、特定のＵＲＬに接続したなら、その再生履歴やＵＲＬ接続履歴などが暗号化されてよい。
【０１４１】
端末装置２（１００−２）も、類似する形態で暗号文を生成して第１サーバ装置２００に伝送することができる（Ｓ８２５、Ｓ８３０、Ｓ８３５）。
【０１４２】
第１サーバ装置２００は、伝送する暗号文を暗号化されたそのままの状態で保存する。このような状態で、第２サーバ装置３００が特定の演算を要求するなら（Ｓ８４０）、第１サーバ装置２００は暗号文状態で演算を行った後（Ｓ８４５）、第２サーバ装置３００に伝送する（Ｓ８５０）。第２サーバ装置３００は、伝送された暗号文を復号化してメッセージを検出する。
【０１４３】
例えば、数式９のような形態で暗号化された暗号文を第２サーバ装置３００が秘密鍵ｓｋ＝（１，ｓ）に復号化する場合、その結果は次のような数式で表されてよい。
【０１４４】
（数式１４）
＜Ｃｔｘｔ，ｓｋ＞
＝（ｖ・ｂ（ｘ）＋△・Ｍ＋ｅ０）＋ｓ（ｘ）（ｖ・ａ（ｘ）＋ｅ1）
＝ｖ（ｂ（ｘ）＋ａ（ｘ）ｓ（ｘ））＋△・△＋ｅ０＋ｓ（ｘ）・ｅ１
＝△・Ｍ＋（ｖ・ｅ＋ｅ０＋ｓ（ｘ）・ｅ１）
＝△・Ｍ＋ｅｓｍａｌｌ
【０１４５】
結果的に、復号化されたデータは、スケーリングファクタ及びメッセージを乗算した値に小さなエラーｅｓｍａｌｌを加算した値を含み、エラーは、ＬＳＢ側に配置され、ΔＭは、エラーに隣接する位置に配置されるようになる。
【０１４６】
具体的に例を挙げると、第１メッセージが１．２３であり、第２メッセージが３．４５であり、スケーリングファクタΔ＝１０３であると仮定すると、ΔＭ１＋ｅ１≒１２３０、ΔＭ２＋ｅ２≒３４５０になる。第１サーバ装置２００で乗算演算を行うと、データはΔ２Ｍ１Ｍ２＋ｅｔｏｔａｌ≒４２４３５００になる。この結果値にΔ−１を乗算した後、ラウンディング処理すると４２４３になる。第２サーバ装置２００は、復号化によってこのような結果値を得ることができる。
【０１４７】
第２サーバ装置３００は、復号化されたメッセージを出力することができる（Ｓ８６０）。例えば、端末装置１、２（１００−１、１００−２）がそれぞれ写真を第１サーバ装置２００に伝送した状態なら、第２サーバ装置３００は、各装置１００−１、１００−２で撮影された写真をまとめて出力することができる。
【０１４８】
上述のような実施形態においては、第１サーバ装置２００で暗号文の間の演算を行い、ノイズ領域を除去した後で第２サーバ装置３００に伝送するものとして図示及び説明しているが、必ずしもそれに限定されるものではない。例えば、第２サーバ装置３００がスケーリングファクタに対する情報を知っている場合、直接ノイズ領域を除去して有効領域を検出した後で復号化を行うこともできる。
【０１４９】
一方、以上のような暗号化方法及び暗号文処理方法は、実数平文に対して適用することができる。
【０１５０】
図９は、本発明の一実施形態に係るネットワークシステムの構成を示す図である。
【０１５１】
図９を参照すると、ネットワークシステムは、複数の端末装置１００−１〜１００−ｎ、第１サーバ装置２００、第２サーバ装置３００を含んでよく、各構成は、ネットワーク１０を介して相互接続されてよい。
【０１５２】
ネットワーク１０は、多様な有無線通信ネットワーク、放送通信ネットワーク、光通信ネットワーク、クラウドネットワークなどで実現されてよく、各装置は別途の媒介体のないＷｉ−Ｆｉ、ブルートゥース（登録商標）、ＮＦＣ（Ｎｅａｒ  Ｆｉｅｌｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ）などのような方式で接続されてよい。
【０１５３】
図９においては、端末装置が複数１００−１〜１００−ｎであるとして示しているが、必ずしも複数の端末装置が使用されるわけではなく、一つの装置が使われてよい。一例として、端末装置１００−１〜１００−ｎは、携帯電話、タブレットパソコン、ゲームプレーヤ、パソコン、ラップトップパソコン、ホームサーバ、キオスク端末などのような多様な装置で実現されてよく、その他にＩｏＴ機能が適用された家電製品で実現されてよい。
【０１５４】
ユーザは、自分が使う端末装置１００−１〜１００−ｎを介して多様な情報を入力することができる。入力された情報は、端末装置１００−１〜１００−ｎそのものに保存されてよいが、保存容量及びセキュリティなどを理由に外部装置に伝送されて保存されてよい。図１においては、第１サーバ装置２００は、このような情報を保存する役割を担い、第２サーバ装置３００は、第１サーバ装置２００に保存された情報の一部又は全部を用いる役割を担う。
【０１５５】
各端末装置１００−１〜１００−ｎは、入力された情報を同型暗号化し、同型暗号文を第１サーバ装置２００に伝送することができる。第１サーバ装置２００は、伝送された同型暗号文を復号化せずに、暗号文の状態で保存することができる。
【０１５６】
第２サーバ装置３００は、同型暗号文に対する特定の処理結果を第１サーバ装置２００に要求することができる。第１サーバ装置２００は、要求に応じて、特定の演算を行った後、その結果を第２サーバ装置３００に伝送する。一例として、二つの端末装置１００−１、１００−２が伝送した暗号文ｃｔ１、ｃｔ２が第１サーバ装置２００に保存された場合、第２サーバ装置３００は両端末装置１００−１、１００−２から提供された情報を合算した値を第１サーバ装置２００に要求することができる。第１サーバ装置２００は、要求に応じて、両暗号文を合算する演算を行った後、その結果値（ｃｔ１＋ｃｔ２）を第２サーバ装置３００に伝送することができる。
【０１５７】
各端末装置１００−１〜１００−ｎは、同型暗号化を行う過程で算出される暗号化ノイズ、即ち、エラーを暗号文に含ませることができる。具体的には、各端末装置１００−１〜１００−ｎで生成する同型暗号文は、その後に秘密鍵を用いて復号化した際に、メッセージ及びエラー値を含む結果値が復元される形態で生成されてよい。
【０１５８】
一例として、端末装置１００−１〜１００−ｎで生成する同型暗号文は、秘密鍵を用いて復号化した際、次のような性質を満たす形態で生成される。
【０１５９】
（数式１）
Ｄｅｃ（ｃｔ，ｓｋ）  ＝  ＜ｃｔ，ｓｋ＞  ＝  ΔＭ＋ｅ（ｍｏｄ  ｑ）
【０１６０】
ここで、＜及び＞は内積（ｕｓｕａｌ  ｉｎｎｅｒ  ｐｒｏｄｕｃｔ）、ｃｔは暗号文、ｓｋは秘密鍵、Ｍは平文メッセージ、ｅは暗号化エラー値、Δはスケーリングファクタ（ｓｃａｌｉｎｇ  ｆａｃｔｏｒ）、そしてｑは暗号文のモジュラス（Ｍｏｄｕｌｕｓ）を意味する。ｑは、スケーリングファクタがメッセージに乗算された結果値ΔＭより大きく選択されなければならない。エラー値ｅの絶対値がΔＭに比べて十分に小さいと、暗号文の復号化値ΔＭ＋ｅは有効数字演算で元のメッセージを同一の精度に代替できる値である。復号化されたデータのうち、エラーは最下位のビット（ＬＳＢ）側に配置され、ΔＭは次下位のビット側に配置される。
【０１６１】
メッセージの大きさが小さすぎるか大きすぎる場合、スケーリングファクタを用いてその大きさを調節することもできる。スケーリングファクタを使うと、整数形態のメッセージだけでなく、実数のメッセージまで暗号化することができるようになるため、活用性が大きく増大することができる。なお、スケーリングファクタを用いてメッセージの大きさを調節することで、演算が行われた後の暗号文でメッセージが存在する領域、即ち、有効領域の大きさも調節されてよい。
【０１６２】
実施形態によって、暗号文のモジュラスｑは、様々に設定されて使われてよい。一例として、暗号文のモジュラスは、スケーリングファクタΔのべき乗ｑ＝ΔＬに設定されてよい。Δが２であると、ｑ＝２１０のような値に設定されてよい。
【０１６３】
別の例として、暗号文のモジュラスは、互いに素な複数の整数値に設定されてよい。具体的に、ｑ＝ｑ１  ｑ２  ｑ３・・・ｑｘに設定され、ｑ１，ｑ２，ｑ３，…，ｑｘのそれぞれは、スケーリングファクタΔと似た大きさであり、互いに素な値に設定される。スケーリングファクタを、このような方式で設定されると、ＣＲＴ（Ｃｈｉｎｅｓｅ  Ｒｅｍａｉｎｄｅｒ  Ｔｈｅｏｒｅｍ）によって全演算を複数のモジュラス演算に分離して進めることができるようになるため、演算の負担を軽減させることができる。互いに素な複数の整数値をモジュラスとして用いる方式をＲＮＳ  ＨＥＡＡＮ方式と称し、ＲＮＳ  ＨＥＡＡＮ方式については、図１２ないし図１６を参照してより詳細に説明する。
【０１６４】
以上のように、各端末装置１００−１〜１００−ｎから生成した暗号文は、第１サーバ装置２００によって処理された後、暗号文の状態で第２サーバ装置３００に伝送される。第２サーバ装置３００は、伝送された暗号文を秘密鍵を用いて復号化することができる。同型暗号化処理が行われたため、復号化されたデータは、メッセージそのものを復号化した後で演算処理した結果と同じ結果になってよい。結果的に、中間過程で第三者に流出される危険性を防止することができるようになる。
【０１６５】
図９の実施形態において、暗号化を行うのに使われる公開鍵は、各端末装置によって生成されてよく、復号化を行う第２サーバ装置３００で生成した後で各端末装置に配布することもできる。以下では、説明を容易にするために、端末装置１００側で各種鍵を生成するものとして説明する。
【０１６６】
鍵生成過程では、Ｒｉｎｇ−ＬＷＥ技法が使われてよい。
【０１６７】
端末装置１００は、鍵生成及びリング設定のための各種パラメータを入力されることができる。具体的に、平文メッセージビットの長さ、公開鍵及び秘密鍵の大きさなどのような多様なパラメータを設定することができる。そして、端末装置１００は、入力されるパラメータに基づいて秘密鍵及び公開鍵などの生成に必要な設定パラメータを生成することができる。
【０１６８】
リングは、次のような数式で表されてよい。
【０１６９】
（数式２）
2020528232.tif 000028
【０１７０】
ここで、Ｒはリング、Ｚｑは係数、ｆ（ｘ）はｎ次多項式である。
【０１７１】
リング（Ｒｉｎｇ）とは、予め設定された係数を有する多項式の集合として、要素の間の加算と乗算が定義されており、加算と乗算に対して閉じている集合を意味する。このようなリングは、環と称してよい。
【０１７２】
一方、上述の数式２において、ｎがΦ（Ｎ）である際、Ｎ次円分多項式（Ｎ−ｔｈ  ｃｙｃｌｏｔｏｍｉｃ  ｐｏｌｙｎｏｍｉａｌ）を意味する。（ｆ（ｘ））とは、ｆ（ｘ）で生成されるＺｑ[ｘ]のイデアル（ｉｄｅａｌ）を表す。Ｅｕｌｅｒ  ｔｏｔｉｅｎｔ関数Φ（Ｎ）とは、Ｎと互いに素であり、Ｎより小さい自然数の数を意味する。ΦＮ（ｘ）をＮ次円分多項式に定義すると、リングは次のような数式でも表されてよい。そして、上述の多項式を相反方程式を用いる場合、リングは数式１５のように表されてよい。
【０１７３】
（数式３）
2020528232.tif 000029
【０１７４】
（数式１５）
2020528232.tif 000030
【０１７５】
一方、上述の数式３及び１５のリングは、平文空間で複素数を有する。一方、本発明では、同型暗号文に対する演算速度を向上させるために、上述のリングの集合のうち平文空間が実数である集合のみを用いることができる。ここで、平文空間が実数であるリングを以下ではＲ’と称し、Ｒ’は次のような数式で表されてよい。Ｒ’を用いる方式をＲｅａｌ  ＨＥＡＡＮ方式と称する。
【０１７６】
（数式１６）
2020528232.tif 000031
【０１７７】
このように、リングが設定されると、端末装置１００はリングから秘密鍵（ｓｋ）を算出することができる。
【０１７８】
（数式１７）
2020528232.tif 000032
【０１７９】
ここで、Ｓは小さな係数でランダムに生成された値を意味する。
【０１８０】
そして、端末装置１００は、リングから第１ランダム多項式（ａ）を算出する。第１ランダム多項式は、次のように表されてよい。
【０１８１】
（数式１８）
2020528232.tif 000033
【０１８２】
なお、端末装置１００はエラーを算出することができる。具体的に、端末装置１００は、離散ガウシアン分布又はそれと統計的な距離が近い分布から抽出することができる。このようなエラーは、次のように表されてよい。
【０１８３】
（数式１９）
2020528232.tif 000034
【０１８４】
エラーまで算出されると、端末装置１００は、第１ランダム多項式及び秘密鍵にエラーをモジュラ演算して第２ランダム多項式を算出することができる。第２ランダム多項式は、次のように表されてよい。
【０１８５】
（数式２０）
2020528232.tif 000035
【０１８６】
最終的に、公開鍵（ｐｋ）は、第１ランダム多項式及び第２ランダム多項式を含む形態で次のように設定されてよい。
【０１８７】
（数式２１）
2020528232.tif 000036
【０１８８】
端末装置１００は、生成された公開鍵を他の端末装置１００−２〜１００−ｎ及び／又はサーバ装置２００に伝送することができる。
【０１８９】
上述のような例においては、端末装置１００が公開鍵及び秘密鍵を生成するものとして説明しているが、別の例では、サーバ装置２００又はその他の装置が公開鍵及び秘密鍵のうち少なくとも一つを生成した後、他装置と共有することも可能である。なお、上述の鍵生成方法は一例に過ぎないため、必ずしもそれに限定されるものではなく、その他に別の方法で公開鍵及び秘密鍵を生成することができる。
【０１９０】
より具体的な公開鍵及び秘密鍵生成動作については、図１２を参照して後述する。
【０１９１】
図１０は、本発明の一実施形態に係る端末装置の概略な構成を示すブロック図である。
【０１９２】
図１０を参照すると、端末装置１００は、メモリ１１０及びプロセッサ１２０で構成されてよい。
【０１９３】
メモリ１１０は、端末装置１００を駆動するためのＯ／Ｓや各種ソフトウェア、データなどを保存するための構成要素である。メモリ１１０は、ＲＡＭやＲＯＭ、フラッシュメモリ、ＨＤＤ、外付けメモリ、メモリカードなどのような形態で実現されてよく、何れかに限定されるわけではない。
【０１９４】
メモリ１１０は、暗号化するメッセージを保存する。ここで、メッセージは、ユーザが各種引用した各種信用情報、個人情報などであってよく、端末装置１００で使われる位置情報、インターネット使用時間情報など、使用履歴などに関連する情報であってよい。
【０１９５】
そして、メモリ１１０は、公開鍵を保存することができ、端末装置１００が直接公開鍵を生成した装置である場合、秘密鍵だけでなく、公開鍵及び秘密鍵の生成に必要な各種パラメータを保存することができる。
【０１９６】
なお、メモリ１００は、後述する過程で生成された同型暗号文を保存することができる。
【０１９７】
プロセッサ１２０は、端末装置１００内の各構成を制御する。このようなプロセッサ１２０は、ＣＰＵのような単一装置で構成されてよく、クロック発生回路、ＣＰＵ、グラフィックプロセッサなどの複数の装置で構成されてよい。
【０１９８】
そして、プロセッサ１２０は、メモリ１１０に保存されたプログラムを実行させて同型暗号文の生成に必要な秘密鍵及び公開鍵を生成することができる。そのために、優先的にプロセッサ１２０は予め設定された係数を有する多項式の集合であるリングを設定することができる。このとき、リングは、上述の数式１５又は数式１６を満たすことができる。
【０１９９】
そして、プロセッサ１２０は、リングから秘密鍵を算出することができる。具体的に、プロセッサ１２０は、以下のような数式に基づいてリングから秘密鍵（ＳＫ）を算出することができる。
【０２００】
そして、プロセッサ１２０は、リングから第１ランダム多項式（ａ）を算出することができ、離散ガウシアン分布又はそれと統計的な距離が近い分布からエラーを抽出することができる。
【０２０１】
なお、プロセッサ１２０は、第１ランダム対向式及び秘密鍵にエラーをモジュラ演算して第２ランダム多項式を算出し、最終的に第１ランダム多項式及び第２ランダム多項式を含む形態で公開鍵（ｐｋ）を生成することができる。一方、端末装置１００がＲＮＳ  ＨＥＡＡＮをサポートする場合、プロセッサ１２０は互いに素な複数の整数のそれぞれに対応する複数の公開鍵を生成することができる。
【０２０２】
そして、プロセッサ１２０は、メッセージに対する同型暗号文を生成することができる。具体的に、プロセッサ１２０は、メッセージに対して既に生成された公開鍵を適用して同型暗号文を生成することができる。
【０２０３】
一方、端末装置１００がＲＮＳ  ＨＥＡＡＮをサポートする場合、プロセッサ１２０は、メッセージに互いに素な複数の整数のそれぞれに対応する複数の公開鍵を用いて複数の基底（ｂａｓｉｓ）で表現される同型暗号文を生成することができる。
【０２０４】
なお、プロセッサ１２０は、暗号化するメッセージをリングに属する多項式で算出し、算出された多項式に公開鍵を適用して同型暗号文を生成することができる。暗号化するメッセージは、外部ソースから受信することもでき、端末装置１００に直接備えるか又は接続された入力装置から入力されてよい。なお、スケーリングファクタもユーザが直接入力するか、別の装置を介して提供されることもできる。
【０２０５】
上述の暗号文のモジュラスｑは、実施形態によって異なるように設定されてよい。一例として、プロセッサ１２０は、暗号文モジュラスをスケーリングファクタΔのべき乗ｑ＝ΔＬで設定することができる。別の例として、プロセッサ１２０は、互いに素な複数の整数値に設定される値が用いられてよい。
【０２０６】
なお、プロセッサ１２０は、暗号文の長さをスケーリングファクタの大きさに対応するように生成されてよい。
【０２０７】
一方、本発明の一実施形態によると、パッキング（ｐａｃｋｉｎｇ）が行われてよい。同型暗号化でパッキングを用いるようになると、複数のメッセージを一つの暗号文で暗号化することが可能になる。この場合、第１サーバ装置２００で各暗号文の間の演算を行うようになると、結果的に複数のメッセージに対する演算が並列的に処理されるため、演算の負担を大幅に軽減するようになる。
【０２０８】
具体的には、プロセッサ１２０は、メッセージが複数のメッセージベクトルで行われる場合、複数のメッセージベクトルを並列的に暗号化できる形態の多項式に変換した後、その多項式にスケーリングファクタを乗算して公開鍵を用いて同型暗号化することもできる。それにより、複数のメッセージベクトルをパッキングした暗号文を生成することができる。
【０２０９】
プロセッサ１２０は、暗号文に対する演算を行うことができる。具体的に、プロセッサ１２０は、同型暗号文に対して暗号化された状態を維持した状態で加算又は乗算などの演算を行うことができる。具体的に、プロセッサ１２０は、演算に使われる同型暗号文のそれぞれを第１関数処理し、第１関数処理された同型暗号文の間で加算又は乗算などの演算を行い、演算が行われた同型暗号文を第１関数の逆関数である第２関数処理することができる。ここで、第１関数は、ＮＴＴ関数であってよい。
【０２１０】
一方、同型暗号文を上述のＲＮＳ方式で生成した場合、プロセッサ１２０は生成された同型暗号文内の基底別に加算及び乗算を行うことができる。
【０２１１】
一方、端末装置１００は、演算が完了すると、演算結果データから有効領域のデータを検出することができる。具体的に、端末装置１００は、演算結果データをラウンディング処理を行って有効領域のデータを検出することができる。ラウンディング処理とは、暗号化された状態でメッセージの四捨五入（ｒｏｕｎｄ−ｏｆｆ）を行うことを意味し、リスケール（ｒｅｓｃａｌｉｎｇ）と呼ぶこともできる。具体的には、端末装置１００は、暗号文のそれぞれの成分にスケール因数の逆数であるΔ−１を乗算して四捨五入し、ノイズ領域を除去する。ノイズ領域は、スケーリングファクタの大きさに対応するように決定されてよい。結果的に、ノイズ領域の除去された有効領域のメッセージを検出することができる。暗号化状態で進められるため、更なるエラーが発生するが、大きさは十分に小さいため、無視することができる。
【０２１２】
もし、端末装置１００がＲＮＳ  ＨＥＡＡＮをサポートする場合、プロセッサ１２０は、複数の基底のうちいずれかの割合が閾値を超過すると、生成された同型暗号文内の複数の基底のそれぞれに対するメッセージの四捨五入処理を行って同型暗号文をリスケールすることができる。
【０２１３】
なお、端末装置１００は、演算結果暗号文内の近似メッセージの割合が閾値を超過すると、演算結果暗号文の平文空間を拡張することができる。具体的に、上述の数式１でｑがＭより小さいと、Ｍ＋ｅ（ｍｏｄ  ｑ）はＭ＋ｅと異なる値を有するため、復号化ができなくなる。よって、ｑ値は、常にＭより大きく維持されなければならない。しかし、演算が進められるにつれ、ｑ値は次第に減少するようになる。平文空間の拡張とは、暗号文ｃｔをより大きいモジュラスを有する暗号文に変換させることを意味する。平文空間を拡張する動作は、リブート（ｒｅｂｏｏｔｉｎｇ）と称してよい。リブートを行うことで、暗号文は再び演算が可能な状態になる。
【０２１４】
一方、以上では、端末装置１００を構成する概略な構成についてのみ図示して説明しているが、実現の際には、多様な構成が更に備えられてよい。それについては、図１１を参照して以下で説明する。
【０２１５】
図１１は、本発明の一実施形態に係る端末装置の具体的な構成を示すブロック図である。
【０２１６】
図１１を参照すると、本発明の端末装置１００は、メモリ１１０、プロセッサ１２０、通信部１３０、ディスプレイ１４０及び操作入力装置１５０で構成されてよい。
【０２１７】
メモリ１１０については、図１０を参照して既に説明しているため、繰り返し説明は省略する。そして、プロセッサ１２０についても、図１０を参照して説明しているため、図１０で説明した内容は繰り返し記載せずに、図１１に追加された構成に関連する内容のみを以下で説明する。
【０２１８】
通信部１３０は、端末装置１００を外部装置（図示せず）と接続するために形成され、近距離通信網（ＬＡＮ：Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）及びインターネット網を通じて外部装置に接続される形態だけでなく、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）ポート又は無線通信（例えば、ＷｉＦｉ  ８０２．１１ａ/ｂ/ｇ/ｎ、ＮＦＣ、Ｂｌｕｅｔｏｏｔｈ（登録商標））ポートを通じて接続される形態も可能である。このような通信部１３０は、送受信部（ｔｒａｎｓｃｅｉｖｅｒ）と称されてよい。
【０２１９】
通信部１３０は、公開鍵を外部装置から受信することができ、端末装置１００で生成された公開鍵を外部装置に伝送することができる。
【０２２０】
そして、通信部１３０は、外部装置からメッセージを受信することができ、生成した同型暗号文を外部装置に送信することができる。
【０２２１】
なお、通信部１３０は、暗号文の生成に必要な各種パラメータを外部装置から受信することができる。一方、実現時に、各種パラメータは後述する操作入力装置１５０を介してユーザから直接入力されることができる。
【０２２２】
ディスプレイ１４０は、端末装置１００がサポートする機能を選択されるためのユーザインターフェースウィンドウを表示する。具体的に、ディスプレイ１４０は、端末装置１００が提供する各種機能を選択されるためのユーザインターフェースウィンドウを表示することができる。このようなディスプレイ１４０は、ＬＣＤ、ＣＲＴ、ＯＬＥＤなどのようなモニタであってよく、後述の項さ入力装置１５０の機能を同時の行うことができるタッチスクリーンで実現されてよい。
【０２２３】
ディスプレイ１４０は、秘密鍵及び公開鍵の生成に必要なパラメータの入力を要求するメッセージを表示することができる。そして、ディスプレイ１４０は、暗号化の対象がメッセージを選択するメッセージを表示することができる。一方、実現時に、暗号化の対象はユーザが直接選択することもでき、自動的に選択されることもできる。即ち、暗号化が必要な個人情報などは、ユーザが直接メッセージを選択しなくても自動的に設定されてよい。
【０２２４】
操作入力装置１５０は、ユーザから端末装置１００の機能選択及び当該機能に対する制御命令を入力されることができる。具体的に、操作入力装置１５０は、ユーザから秘密鍵及び公開鍵の生成に必要なパラメータを入力されることができる。なお、操作入力装置１５０は、ユーザから暗号化されるメッセージを設定されることができる。
【０２２５】
プロセッサ１２０は、ユーザから秘密鍵及び公開鍵の生成に必要なパラメータを入力されると、入力されるパラメータに基づいて設定パラメータを生成し、生成された設定パラメータに基づいて秘密鍵及び公開鍵を生成することができる。
【０２２６】
そして、メッセージに対する暗号文の生成が必要になると、プロセッサ１２０はメッセージに公開鍵を適用して同型暗号文を生成することができる。具体的に、プロセッサ１２０は、メッセージを多項式に変換し、変換された多項式のメッセージに公開鍵を適用して同型暗号文を生成することができる。
【０２２７】
そして、プロセッサ１２０は、同型暗号文に対する復号が必要な場合、同型暗号文に秘密鍵を適用して多項式の復号文を生成し、多項式の復号文をデコードしてメッセージを生成することができる。このとき、生成したメッセージは、前記数式１で触れたようにエラーを含むことがある。
【０２２８】
なお、プロセッサ１２０は、同型暗号文に対する演算が必要になる場合、ユーザが要求した複数の同型暗号文に対して加算又は乗算演算を行うことができる。具体的な演算動作については、図１５及び図１６を参照して後述する。
【０２２９】
以上のように、本実施形態に係る端末装置１００は、メッセージに同型暗号文を生成することができるため、演算が必要な場合にも、メッセージの安全性を向上させることができる。なお、生成される同型暗号文はエラーを含むため、高度のセキュリティ性が求められる生態情報などに対しても、安定したセキュリティを保持することができる。なお、本実施形態に係る端末装置１００は、平文空間が実数であるリングを用いることから、演算速度を向上することができる。即ち、従来の平文空間が複素数であるリングを用いる場合より倍多い並列実数演算ができるようになる。
【０２３０】
以下では、ＲＥＡＬ  ＨＥＡＡＮ方式にアルゴリズムを先に説明する。
【０２３１】
暗号文間の演算は、
2020528232.tif 000037
要素の間の加算、乗算の演算であるため、
2020528232.tif 000038
上における演算の効率性を増大させることが必要である。
2020528232.tif 000039
上に乗算を最もナイーブ（ｎａｉｖｅ）に行うと、０（ｎ２）の複雑度（ｃｏｍｐｌｅｘｉｔｙ）有する。
【０２３２】
このような演算の複雑度を軽減させるために、本発明では、ｎｕｍｂｅｒ  Ｔｈｅｏｒｅｔｉｃ  Ｔｒａｎｓｆｏｒｍ（ＮＴＴ）技法を用いる。ＮＴＴｍとは、
2020528232.tif 000040
から
2020528232.tif 000041
に進むフィールド同型（ｆｉｅｌｄ  ｉｓｏｍｏｒｐｈｉｓｍ）であり、それの逆関数をＩＮＴＴｍと称する。
【０２３３】
このようなＮＴＴｍ、ＩＮＴＴｍは、ファストプリエトランスフォーム（Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）アルゴリズムの適用の際、０（ｍ  ｌｏｇ  ｍ）の複雑度を有する。
【０２３４】
即ち、
2020528232.tif 000042
に対して
2020528232.tif 000043
を計算したい場合、
2020528232.tif 000044
で演算を行うと、０（ｍ  ｌｏｇｍ）の複雑度を有する。
【０２３５】
以下では、上述の技法をリングを適用する方式を説明する。
【０２３６】
リングに属する要素のそれぞれは、
2020528232.tif 000045
を満たし、
2020528232.tif 000046
である際、要素は以下のような数式２２のように表されてよい。
【０２３７】
（数式２２）
2020528232.tif 000047
【０２３８】
まず、Ｒ’に対してＮＴＴｍ（ＮＴＴ’ｎ／２）に関連し、
2020528232.tif 000048
を計算し、
2020528232.tif 000049
は、次のような数式２３のように表されてよい。
【０２３９】
（数式２３）
2020528232.tif 000050
【０２４０】
そして、Ｒ’に対するＮＴＴｍ（ＮＴＴ’ｎ／２）に関連し、
2020528232.tif 000051
を計算し、数式２４のような値を出力することができる。
【０２４１】
（数式２４）
2020528232.tif 000052
【０２４２】
ここで、
2020528232.tif 000053
である。
【０２４３】
よって、上述の数式２３及び２４をまとめると、次の通りである。
【０２４４】
（数式２５）
2020528232.tif 000054
【０２４５】
即ち、
2020528232.tif 000055
に対するＮＴＴとＩｎｖｅｒｓｅ  ＮＴＴいずれも、０（ｎ  ｌｏｇ  ｎ）の複雑度を有する。よって、
2020528232.tif 000056
を満たす場合に、
2020528232.tif 000057
を計算したい場合に、
2020528232.tif 000058
で演算を行う場合、０（ｎ  ｌｏｇ  ｎ）の複雑度を有する。
【０２４６】
以下では、ＲＥＡＬ  ＨＥＡＡＮが適用される場合の秘密鍵、公開鍵の生成アルゴリズム、同型暗号文生成方式及び演算方式について、図１２ないし図１６を参照して説明する。
【０２４７】
図１２は、公開鍵及び秘密鍵の生成動作を説明するための図である。
【０２４８】
図１２を参照すると、セットアップモジュール７１は、ユーザからスケーリングファクタ（Δ）、セキュリティパラメータ（λ）、レベルパラメータ（Ｌ）を入力されることができる。ここで、スケーリングファクタ（Δ）は、メッセージの大きさを調節するパラメータとして１より大きい。そして、セキュリティパラメータ（λ）は、いくらスキームが安定しているかを示す指標として、計算の複雑度と称してよい。そして、レベルパラメータは、演算をサポートするデプスを示す指標である。
【０２４９】
上述のように、パラメータを入力されるセットアップモジュール７１は、モジュライ（ｍｏｄｕｌｉ）を設定し、整数（ｎ）と正数（Ｐ）をランダムに選択し、
2020528232.tif 000059
のような設定パラメータを出力することができる。
【０２５０】
鍵生成モジュール７２は、既にセットアップモジュール７１に生成された設定パラメータを入力され、入力される設定パラメータに基づいて秘密鍵と公開鍵を生成することができる。
【０２５１】
具体的に、鍵生成モジュール７２は、
2020528232.tif 000060
、
2020528232.tif 000061
に基づいて、秘密鍵を生成し、
2020528232.tif 000062
によってエラーを算出することができる。
【０２５２】
そして、鍵生成モジュール７２は、
2020528232.tif 000063
のように、第１ランダム多項式を生成し、
2020528232.tif 000064
のように第２ランダム多項式を生成することができる。既に作られている第１タンダム多項式と第２ランダム多項式に基づいて既に説明した数式２１のような公開鍵を生成することができる。
【０２５３】
図１３は、演算鍵の生成動作を説明するための図である。
【０２５４】
図１３を参照すると、演算モジュール７３を満たす値と
2020528232.tif 000065
、ｅ’←Ｘｅｒｒを算出し、
2020528232.tif 000066
を満たす
2020528232.tif 000067
を算出することができる。それにより、演算モジュール７３は、
2020528232.tif 000068
のような演算鍵を出力することができる。
【０２５５】
図１４は、近似同型暗号文の生成及び復号動作を説明するための図である。
【０２５６】
図１４を参照すると、エンコードモジュール７４は、メッセージとスケーリングファクタを入力され、メッセージにスケーリングファクタを反映して多項式に変換することができる。
【０２５７】
具体的に、エンコードモジュール７４は、
2020528232.tif 000069
、
１以上のスケーリングファクタを入力されると、メッセージを以下の数式２６のような多項式を出力することができる。
【０２５８】
（数式２６）
2020528232.tif 000070
【０２５９】
ここで、ｍ（ｘ）は、多項式形態のメッセージである。
【０２６０】
そして、暗号化モジュール７５は、多項式形態のメッセージを受信し、受信したメッセージに公開鍵を反映して同型暗号文を生成することができる。具体的に、以下のような数式２７を用いて同型暗号文を生成することができる。
【０２６１】
（数式２７）
2020528232.tif 000071
【０２６２】
ここで、ｖはＸｅｎｃによって選択された要素であり、ｅ０、ｅ１もＸｅｒｒによって選択されたエラー値である。
【０２６３】
復号化モジュール７６は、暗号文と秘密鍵を入力され、暗号文を復号化してエラーを含むメッセージを出力することができる。具体的に、復号化モジュール７６は、入力された暗号文が
2020528232.tif 000072
である場合、
2020528232.tif 000073
のようなメッセージを出力することができる。
【０２６４】
一方、復号化モジュール７６から出力されるメッセージは、多項式形態のメッセージであることから、デコードモジュール７７で、復号化モジュール７６から出力されたメッセージとスケーリングファクタに基づいて、メッセージを最終的に出力することができる。具体的に、復号化モジュール７６は、多項式メッセージが
2020528232.tif 000074
を満たす場合、
2020528232.tif 000075
のようなメッセージを出力することができる。
【０２６５】
図１５は、同型暗号文の加算計算を説明するための図である。
【０２６６】
図１５を参照すると、第１端末装置８１−１から第１メッセージに対する第１同型暗号文（Ｃｔ１）を出力し、第２端末装置８１−２から第２メッセージに対する第２同型暗号文（Ｃｔ２）を出力する。
【０２６７】
第１同型暗号文（Ｃｔ１）と第２同型暗号文（Ｃｔ２）とを受信したサーバ装置の演算モジュール８３は、両同型暗号文に対する加算演算を行うことができる。具体的に、
2020528232.tif 000076
を満たす場合、演算モジュール８３は
2020528232.tif 000077
のように両同型暗号文に対する加算演算を行うことができる。
【０２６８】
即ち、両同型暗号文に対して第１関数処理し、関数処理された同型暗号文に対する加算演算を行い、加算演算された同型暗号文を第１関数に逆関数である第２関数処理して、両同型暗号文に対する加算演算を行うことができる。
【０２６９】
その後、実際の値が必要になる場合、復号モジュール８５は加算結果を復号及びデコードして第１メッセージ及び第２メッセージの合算値を出力することができる。
【０２７０】
図１６は、同型暗号文の乗算計算を説明するための図である。
【０２７１】
図１６を参照すると、第１端末装置８１−１から第１メッセージに対する第１同型暗号文（Ｃｔ１）を出力し、第２端末装置８１−２から第２メッセージに対する第２同型暗号文（Ｃｔ２）を出力することができる。第１同型暗号文（Ｃｔ１）と第２同型暗号文（Ｃｔ２）とを受信したサーバ装置の演算モジュール８７は、両同型暗号文に対する乗算演算を行うことができる。具体的に、
2020528232.tif 000078
を満たす場合、演算モジュール８７は、
2020528232.tif 000079
のように、両同型暗号文に対する加算演算を行うことができる。ここで、
2020528232.tif 000080
である。
【０２７２】
即ち、両同型暗号文に対して第１関数処理し、関数処理された同型暗号文に対する乗算演算を行い、乗算演算された同型暗号文を第１関数に逆関数である第２関数処理して、両同型暗号文に対する乗算演算を行うことができる。
【０２７３】
演算によって獲得された演算結果暗号文内の近似メッセージ割合が閾値を超過すると、リスケールモジュール８８は、演算結果暗号文の平文空間を拡張することができる。具体的に、リスケールモジュール８８は、以下のような数式２８のように暗号文をアップデートすることができる。
【０２７４】
（数式２８）
2020528232.tif 000081
【０２７５】
ここで、
2020528232.tif 000082
である。
【０２７６】
その後、復号モジュール８５は、加算結果を復号及びデコードして第１メッセージ及び第２メッセージの合算値を出力することができる。
【０２７７】
以上では、Ｒｅａｌ  ＨＥＡＡＮ方式について説明しているが、以下では、ＲＮＳ  ＨＥＡＡＮ方式について説明する。
【０２７８】
ＲＮＳ  ＨＥＡＡＮは、従来のＨＥＡＡＮ方式が中国人の残りの整理のような方法が適用できなかった問題を解決するために、従来の暗号文空間である
2020528232.tif 000083
を
2020528232.tif 000084
に代替して使う方式で、それによって、エラービットサイズが５〜１０くらい大きい近似計算結果を有するようになるが、演算速度で３〜１０倍の性能改善があった。
【０２７９】
動作方式は、既に説明したＲｅａｌ  ＨＥＡＡＮ方式と類似するため、相違する部分に対してのみ説明する。
【０２８０】
まず、ＲＮＳ  ＨＥＡＡＮでモジュラスは、以下の数式２９のように互いに素である複数の整数で定義されてよい。
【０２８１】
（数式２９）
2020528232.tif 000085
【０２８２】
それにより、生成される評価鍵は、次のような数式３０のようであり、公開鍵も、数式３１のように複数の互いに素に対応する複数の基底で表されてよい。
【０２８３】
（数式３０）
2020528232.tif 000086
【０２８４】
ここで、
2020528232.tif 000087
であり、
2020528232.tif 000088
である。そして、
2020528232.tif 000089
である。
【０２８５】
（数式３１）
2020528232.tif 000090
【０２８６】
ここで、
2020528232.tif 000091
であり、
2020528232.tif 000092
である。
【０２８７】
よって、暗号文を生成する場合に、以下の数式３２のように、複数の基底で表現される同型暗号文が生成される。
【０２８８】
（数式３２）
2020528232.tif 000093
【０２８９】
ここで、
2020528232.tif 000094
であり、
2020528232.tif 000095
、
2020528232.tif 000096
である。
【０２９０】
一方、ＲＮＳ  ＨＥＡＡＮ方式で生成された同型暗号文（
2020528232.tif 000097
、
2020528232.tif 000098
）に対する加算演算は、次のような数式３３のように行われてよい。
【０２９１】
（数式３３）
2020528232.tif 000099
【０２９２】
ここで、
2020528232.tif 000100
である。
【０２９３】
一方、ＲＮＳ  ＨＥＡＡＮ方式で生成された同型暗号文（
2020528232.tif 000101
、
2020528232.tif 000102
）に対する演算は、次のようなステップで行われてよい。
【０２９４】
まず、数式３４のような演算を一次的に行う。
【０２９５】
（数式３４）
2020528232.tif 000103
【０２９６】
その後、数式３５のように、ｍｏｄｕｐ動作を行うことができる。
【０２９７】
（数式３５）
2020528232.tif 000104
【０２９８】
そして、数式３６のような二次演算を行うことができる。
【０２９９】
（数式３６）
2020528232.tif 000105
【０３００】
ここで、
2020528232.tif 000106
であり、
2020528232.tif 000107
である。
【０３０１】
そして、数式３７のような演算を行い、最終的に数式３８のような値を最終出力する。
【０３０２】
（数式３７）
2020528232.tif 000108
【０３０３】
（数式３８）
2020528232.tif 000109
【０３０４】
2020528232.tif 000110
【０３０５】
一方、演算の後で暗号文（
2020528232.tif 000111
）の少なくとも一つの基底に対する割合が閾値を超過すると、以下のような数式３９の
ように、複数の基底のそれぞれに対するメッセージの四捨五入処理を行って同型暗号文をリスケールし、リスケールされた暗号文（
2020528232.tif 000112
）を出力することができる。
【０３０６】
（数式３９）
2020528232.tif 000113
【０３０７】
図１７は、本発明の暗号化方法を説明するためのフローチャートである。
【０３０８】
まず、予め設定された係数を有する多項式の集合であるリングを設定する（Ｓ９１０）。具体的に、要素の間で加算と乗算とが定義されており、加算と乗算に対して閉じており、平文空間が実数である数式１６のようなリングを設定することもできる。
【０３０９】
そして、リングから秘密鍵を算出する（Ｓ９２０）。Ｘｋｅｙに基づいてｓを選択し、選択されたｓに基づいて秘密鍵（ＳＫ）を算出することができる。
【０３１０】
そして、算出された秘密鍵に対応して公開鍵を算出する（Ｓ９３０）。具体的に、リングから第１ランダム多項式を算出し、エラーを抽出し、算出された第１ランダム多項式と秘密鍵にエラーをモジュラ演算して第２ランダム多項式を算出し、算出された第１ランダム多項式と第２ランダム多項式を用いて公開鍵を算出することができる。
【０３１１】
そして、メッセージに公開鍵を適用して同型暗号文を生成する（Ｓ９４０）。具体的に、メッセージをリングに属する多項式でエンコードを行い、エンコードされたメッセージに公開鍵を適用して同型暗号文を生成することができる。一方、ＲＮＳ  ＨＥＡＡＮを用いる場合、生成された複数の公開鍵を用いて、複数の基底で表現される同型暗号文を生成することができる。
【０３１２】
以上のように、本実施形態に係る暗号化方法は、エラーを含む同型暗号文を生成するため、高度のセキュリティ性が求められる生態情報などに対しても、安定的なセキュリティを保持することができる。なお、本実施形態に係る暗号化方法は、平文空間が実数であるリングを用いて、演算過程で平文の虚数部が大きくなることを根本から防ぐことができ、従来のＨＥＡＡＮのような安定性、連想速度、メモリ（暗号文、鍵サイズ）を有すると同時に、倍大きい並列実数演算をサポートすることができる。
【０３１３】
図１８は、本発明の一実施形態に係るネットワークシステムの暗号文処理方法を説明するための図である。具体的に、図１８では、二つの端末装置１００−１、１００−２で暗号文を伝送する場合を示している。
【０３１４】
まず、端末装置１（１００−１）で第１メッセージが入力されると（Ｓ１０１０）、端末装置１（１００−１）は、上述の方式で第１同型暗号文を生成した後（Ｓ１０１５）、第１サーバ装置２００に伝送することができる（Ｓ１０２０）。一例として、端末装置１（１００−１）のユーザが写真を撮影した場合には、その写真及び撮影場所などが暗号化されてよく、ユーザが音楽コンテンツを再生したり特定のＵＲＬに接続したなら、その再生履歴やＵＲＬ接続履歴などが暗号化されてよい。
【０３１５】
端末装置２（１００−２）も、類似する形態で暗号文を生成して第１サーバ装置２００に伝送することができる（Ｓ１０２５、Ｓ１０３０、Ｓ１０３５）。
【０３１６】
第１サーバ装置２００は、伝送された暗号文を暗号化されたそのままの状態で保存することができる。このような状態で、第２サーバ装置３００が特定の演算を要求する場合（Ｓ１０４０）、第１サーバ装置２００は同型暗号文に対して第２サーバ装置３００が要求した特定の演算を行った後（Ｓ１０４５）、第２サーバ装置３００に伝送することができる（Ｓ１０５０）。第２サーバ装置３００は、伝送された暗号文を復号化してメッセージを検出することができる。
【０３１７】
そして、第２サーバ装置３００は、復号化されたメッセージを出力することができる（Ｓ１０６０）。例えば、端末装置１、２（１００−１、１００−２）がそれぞれ写真を第１サーバ装置２００に伝送した状態なら、第２サーバ装置３００は各装置１００−１、１００−２で撮影された写真をまとめて出力することができる。
【０３１８】
以上のような暗号化方法及び暗号文処理方法は、各種アプリケーションの実行結果だけでなく、ユーザが直接入力した各種信用情報や個人情報の収集にも使われることができる。第２サーバ装置３００が銀行サーバである場合、銀行は顧客の信号情報のうち必要な項目だけを集めて確認することができる。
【０３１９】
一方、上述の多様な実施形態による暗号化方法及び暗号文処理方法などは、各段階を行うためのプログラムコードの形態で実現され、記録媒体に保存されて配布されてよい。この場合、記録媒体の登載された装置は、上述の暗号化又は暗号文処理などの動作を行うことができる。
【０３２０】
このような記録媒体は、ＲＯＭ、ＲＡＭ、メモリチップ、メモリカード、外付けハード、ハード、ＣＤ、ＤＶＤ，磁気ディスクまたは磁気テープなのような多様なコンピュータ読み取り可能な媒体であってよい。
【０３２１】
以上のように、本発明の多様な実施形態によって、暗号化及び暗号文処理などを行うようになると、量子コンピュータ時代でも安全であり、暗号化／復号化速度を大幅に向上させることができ、暗号文のサイズも減らすことができる。特に、暗号化に使用されるメッセージを実数領域まで拡張させることができるため、活用性が大きく増大する。
【０３２２】
以上、添付図面を参照しながら本発明の好適な実施形態について詳細に説明したが、本発明は以上の実施形態に限定されない。本発明の属する技術の分野における通常の知識を有する者であれば、特許請求の範囲に記載された技術的趣旨の範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、これらについても、当然に本発明の技術的範囲に属するものと了解される。
【図１】
2020528232.tif 000115
【図２】
2020528232.tif 000116
【図３】
2020528232.tif 000117
【図４】
2020528232.tif 000118
【図５】
2020528232.tif 000119
【図６】
2020528232.tif 000120
【図７】
2020528232.tif 000121
【図８】
2020528232.tif 000122
【図９】
2020528232.tif 000123
【図１０】
2020528232.tif 000124
【図１１】
2020528232.tif 000125
【図１２】
2020528232.tif 000126
【図１３】
2020528232.tif 000127
【図１４】
2020528232.tif 000128
【図１５】
2020528232.tif 000129
【図１６】
2020528232.tif 000130
【図１７】
2020528232.tif 000131
【図１８】
2020528232.tif 000132
【国際調査報告】
2020528232.tif 000133
2020528232.tif 000134
2020528232.tif 000135
2020528232.tif 000136