(57)【要約】      （修正有）【課題】堅牢性を向上させた格子暗号の公開鍵生成装置を提供する。【解決手段】生成装置１００は、多項式環を用いて定義される格子による格子空間を所定の回転行列で回転させた回転格子空間の基底ベクトルｆ、ｇを用いて、公開鍵暗号における公開鍵ｈを生成する生成部と、前記生成部により生成された公開鍵を出力する出力部とを有する。【効果】従来の格子暗号に比べて、回転行列によって格子空間が回転する分、秘密鍵が不明である際に、格子空間をどのように回転させたかを特定する分、暗号強度を向上させることができる。【選択図】図１
2019032377.tif 000002
【特許請求の範囲】
【請求項１】
多項式環を用いて定義される格子による格子空間を所定の回転行列で回転させた回転格子空間の基底ベクトルを用いて、公開鍵暗号における公開鍵を生成する生成部と、
前記生成部により生成された公開鍵を出力する出力部と
を有することを特徴とする生成装置。
【請求項２】
前記生成部は、前記格子空間から選択された第１の基底ベクトルを秘密鍵とし、前記格子空間から選択された第２の基底ベクトルと、前記回転行列と、前記秘密鍵の逆行列との積に基づいて、前記公開鍵を生成する
ことを特徴とする請求項１に記載の生成装置。
【請求項３】
前記生成部は、第１素数と、前記第２の基底ベクトルと、前記回転行列と、前記秘密鍵の逆行列との積を第２素数で除算した剰余を公開鍵として算出する
ことを特徴とする請求項１または２に記載の生成装置。
【請求項４】
暗号化の対象となる平文を受付ける受付部と、
請求項１〜３に記載の生成装置により生成された公開鍵と所定の乱数との積算値に、平文を前記第２素数で除算した剰余を加算することで前記平文を暗号化する暗号化部と
を有することを特徴とする暗号化装置。
【請求項５】
請求項４に記載の暗号化装置により暗号化された暗号文を受信する受信部と、
前記秘密鍵と、前記暗号文と、前記回転行列の逆行列との積を前記第２素数で除算した剰余に基づいて、平文を復号化する復号化部と
を有する復号化装置。
【請求項６】
暗号化装置が実行する暗号化方法であって、
暗号化の対象となる平文を受付ける受付工程と、
多項式環を用いて定義される格子による格子空間を所定の回転行列で回転させた回転格子空間の基底ベクトルを用いて生成された公開鍵暗号における公開鍵を用いて、平文を暗号化する暗号化手順と、
を含むことを特徴とする暗号化方法で生成される暗号化データ。
【請求項７】
生成装置が実行する生成方法であって、
多項式環を用いて定義される格子による格子空間を所定の回転行列で回転させた回転格子空間の基底ベクトルを用いて、公開鍵暗号における公開鍵を生成する生成工程と、
前記生成工程により生成された公開鍵を出力する出力工程と
を含むことを特徴とする生成方法。
【請求項８】
コンピュータに
多項式環を用いて定義される格子による格子空間を所定の回転行列で回転させた回転格子空間の基底ベクトルを用いて、公開鍵暗号における公開鍵を生成する生成手順と、
前記生成手順により生成された公開鍵を出力する出力手順と
を実行させるための生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、生成装置、暗号化装置、復号化装置、暗号化データ、生成方法、および生成プログラムに関する。
【背景技術】
【０００２】
近年、インターネットの飛躍的な普及に伴い、インターネットを介した情報配信が盛んに行われている。このような情報配信においては、セキュリティを担保するため、共通鍵暗号方式や公開鍵暗号方式により暗号化された情報を配信するといった処理が行われている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】米国特許第６２９８１３７号明細書
【非特許文献】
【０００４】
【非特許文献１】「General  n-Dimensional  Rotations」、Antonio  Aguilera、Ricardo  Perez-Aguila、インターネット＜http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.4.8662&rep=rep1&type=pdf＞  平成２９年７月２８日検索
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来技術では、セキュリティを担保することができない場合がある。
【０００６】
近年、物質の量子的なふるまいを利用する量子コンピューティングの技術が進歩しているが、このような量子コンピューティングの技術を用いた場合には、暗号化された情報から、暗号鍵や復号鍵を有意な時間内で取得することができるため、暗号化された情報が第３者により復号化される恐れがある。
【０００７】
本願は、上記に鑑みてなされたものであって、暗号の堅牢性を向上させることを目的とする。
【課題を解決するための手段】
【０００８】
本願に係る生成装置は、多項式環を用いて定義される格子による格子空間を所定の回転行列で回転させた回転格子空間の基底ベクトルを用いて、公開鍵暗号における公開鍵を生成する生成部と、前記生成部により生成された公開鍵を出力する出力部とを有することを特徴とする。
【発明の効果】
【０００９】
実施形態の一態様によれば、暗号の堅牢性を向上させることができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施形態に係る各処理の一例を示す図である。
【図２】図２は、実施形態に係る生成装置、復号化装置および暗号化装置の構成例を示す図である。
【図３】図３は、実施形態に係る生成処理の流れの一例を説明するフローチャートである。
【図４】図４は、実施形態に係る復号化処理の流れの一例を説明するフローチャートである。
【図５】図５は、ハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１１】
以下に、本願に係る生成装置、暗号化装置、復号化装置、暗号化データ、生成方法、および生成プログラムを実施するための形態（以下、「実施形態」と記載する。）について図面を参照しつつ詳細に説明する。なお、この実施形態により本願に係る生成装置、暗号化装置、復号化装置、暗号化データ、生成方法、および生成プログラムが限定されるものではない。また、以下の各実施形態において同一の部位には同一の符号を付し、重複する説明は省略される。
【００１２】
［実施形態］
〔１−１．暗号化装置の一例〕
まず、図１を用いて、生成装置が実行する生成処理、暗号化装置が実行する暗号化処理、および復号化装置が実行する復号化処理の一例について説明する。図１は、実施形態に係る各処理の一例を示す図である。
【００１３】
生成装置１００は、公開鍵暗号方式における公開鍵と秘密鍵とを生成する生成処理を実行する情報処理装置であり、例えば、サーバ装置やクラウドシステム等により実現される。また、復号化装置２００は、生成装置１００によって生成された公開鍵と秘密鍵とを受付けると、公開鍵を暗号化装置３００に提供し、暗号化装置３００が公開鍵を用いて生成した暗号文を秘密鍵を用いて平文へと復号化する復号化処理を実行する情報処理装置であり、例えば、サーバ装置やクラウドシステム等により実現される。また、暗号化装置３００は、生成装置１００によって生成された秘密鍵を用いて、平文を暗号化した暗号文を生成する暗号化処理を実行する情報処理装置であり、例えば、サーバ装置やクラウドシステム等により実現される。
【００１４】
ここで、生成装置１００は、復号化装置２００、および暗号化装置３００は、インターネット等の所定のネットワークＮ（例えば、図２参照）を介して、相互に通信が可能である。なお、生成装置１００は、復号化装置２００に対して公開鍵と秘密鍵（以下、「暗号鍵」と総称する場合がある。）とを送信する際、暗号鍵を暗号化して送信してもよく、ＶＰＮ（Virtual  Private  Network）等、安全性を担保できる通信方式により送信してもよい。
【００１５】
〔１−２．生成処理の一例〕
ここで、共通鍵暗号方式や公開鍵暗号方式等といった従来の暗号方式では、セキュリティを担保することができない場合がある。例えば、従来の暗号方式では、暗号化や復号化に用いる鍵を有意な時間内に暗号文から求めることができないように、十分に大きな暗号鍵空間をあらかじめ準備したり、因数分解といった古典的なコンピュータでは計算に時間がかかる問題を利用している。しかしながら、近年、物質の量子的なふるまいを利用する量子コンピューティングの技術が進歩しているが、このような量子コンピューティングの技術を用いた場合には、暗号化された情報から、暗号鍵や復号鍵を有意な時間内で取得することができる可能性がある。
【００１６】
そこで、格子暗号と呼ばれる暗号方式が提案されている。例えば、格子暗号においては、暗号文の受信者側は、所定の空間内に規則的に並んだ点の集合を格子空間とし、格子空間において直行するベクトルの集合を秘密鍵とし、格子空間において平行に近いベクトルの集合を公開鍵として暗号文の送信者側に提供する。一方、暗号文の送信者側は、秘密鍵を整数倍したベクトルに、平文と対応するずれを加算したベクトルを暗号文として生成し、生成した暗号文を受信者側へと送信する。そして、暗号文の受信者側は、秘密鍵、すなわち、格子空間において直行するベクトルの集合を用いて、暗号文となるベクトルの先端に最も近い格子点を特定し、特定した格子点と暗号文となるベクトルとのずれから、平文を復号する。
【００１７】
ここで、秘密鍵となるベクトルが互いに直行している場合には、暗号文となるベクトルの先に最も近い格子点を特定する処理を高速に行うことができるので、暗号鍵の受信者側は、秘密鍵を用いて、暗号文を高速に復号化することができる。一方で、公開鍵となるベクトルが十分に平行に近い場合、暗号文となるベクトルの先に最も近い格子点を特定するには、基底ベクトルを求めなければならず、非常に時間がかかると考えられている。このため、暗号文の送信者は、比較的安全な暗号文を送信することができる。
【００１８】
このような格子暗号の安全性をさらに向上させるため、生成装置１００は、以下の生成処理を実行する。まず、生成装置１００は、多項式環を用いて定義される格子による格子空間を所定の回転行列で回転させた回転格子空間の基底ベクトルを用いて、公開鍵暗号における公開鍵を生成する。そして、生成装置１００は、生成された公開鍵を出力する。
【００１９】
例えば、生成装置１００は、格子空間から選択された第１の基底ベクトルを秘密鍵とし、格子空間から選択された第２の基底ベクトルと、回転行列と、秘密鍵の逆行列との積に基づいて、公開鍵を生成する。より具体的な例を挙げると、生成装置１００は、第１素数と、第２の基底ベクトルと、回転行列と、秘密鍵の逆行列との積の値が１となる行列との積を第２素数で除算した剰余を公開鍵として算出する。そして、生成装置１００は、秘密鍵と、公開鍵と、回転行列または回転行列の逆行列とを復号化装置２００に提供する。
【００２０】
一方、復号化装置２００は、秘密鍵と回転行列または回転行列の逆行列を秘匿し、公開鍵を暗号化装置３００へと提供する。このような場合、暗号化装置３００は、以下の暗号化処理を実行する。まず、暗号化装置３００は、暗号化の対象となる平文を受付ける。そして、暗号化装置３００は、生成装置１００により生成された公開鍵と所定の乱数との積算値に、平文を第２素数で除算した剰余を加算することで平文を暗号化する。そして、暗号化装置３００は、平文を暗号化した暗号文を復号化装置２００へと送信する。
【００２１】
また、復号化装置２００は、以下の復号化処理を実行する。まず、復号化装置２００は、暗号化装置３００により暗号化された暗号文を受信する。そして、復号化装置２００は、秘密鍵と、暗号文と、回転行列の逆行列との積を第２素数で除算した剰余を平文として算出する。
【００２２】
すなわち、生成装置１００は、格子暗号において用いられる格子空間を所定の回転行列で回転させ、回転された格子空間上において十分に平行に近いベクトルを秘密鍵として採用する。この結果、生成装置１００は、回転行列によって格子空間が回転する分、秘密鍵（すなわち、格子空間における基底ベクトル）が不明である際に、格子空間をどのように回転させたかを特定する分、暗号強度を向上させることができる。
【００２３】
〔１−３．数式の一例〕
以下、生成装置１００が暗号鍵を生成する処理の一例を数式を用いて説明する。なお、以下の説明では、格子空間を回転させない格子暗号における数式の一例を説明した後に、生成装置１００が格子空間を回転させた場合に生成する暗号鍵、暗号鍵を用いた暗号化、および復号化の処理の一例について説明する。
【００２４】
例えば、格子空間として、環に係数を持つ一変数または多変数の多項式の全体の集合が成す多項式環Ｒを考える。このようなＲの元は、整数係数のｎ−１時の多項式（ａ＝ａ０＋ａ１ｘ＋・・・＋ａｎ−１ｘｎ−１）で表現される。このようなＲの元ａ、ｂを考えると、ａとｂとの和は、通常の多項式の足し算、ａとｂとの積は、多項式の積ａｂをｘｎ−１で除算した剰余として定義される。
【００２５】
このようなＲの係数が十分に小さい部分集合をＬｓとする。まず、格子暗号においては、式（１）および式（２）を満たす自然数ｐ、ｑを選択する。
【００２６】
【数１】
2019032377.tif 000003
【００２７】
【数２】
2019032377.tif 000004
【００２８】
ここで、格子空間であるＲから以下の式（３）を満たすようにランダムな元ｆ、ｇを選択する。
【００２９】
【数３】
2019032377.tif 000005
【００３０】
このような元ｆを秘密鍵とするとともに、以下の式（４）を用いて、公開鍵ｈを算出する。すなわち、第１の係数（素数）と、格子空間の元となるベクトルと、秘密鍵の逆行列との積を、第２の係数（素数）で除算した剰余が格子暗号における公開鍵となる。
【００３１】
【数４】
2019032377.tif 000006
【００３２】
ここで、平文をｍとする。ここで、平文ｍは、以下の式（５）を満たすものとする。
【００３３】
【数５】
2019032377.tif 000007
【００３４】
続いて、以下の式（６）を満たす乱数ｒを生成する。
【００３５】
【数６】
2019032377.tif 000008
【００３６】
ここで、平文ｍの暗号文をｃとすると、格子暗号における暗号文ｃは、以下の式（７）で示すことができる。すなわち、暗号文ｃは、公開鍵に乱数を積算した値と、平文を第２係数で除算した剰余との和（すなわち、秘密鍵となるベクトルの整数倍に平文に基づくズレを加算した体）となる。
【００３７】
【数７】
2019032377.tif 000009
【００３８】
式（７）に示すように暗号文ｃを復号化する場合、以下の処理を実行する。まず、以下の式（８）に示すベクトルｄを算出し、ベクトルｄの係数を以下の式（９）に示す範囲としたベクトルをベクトルｄ’として算出する。
【００３９】
【数８】
2019032377.tif 000010
【００４０】
【数９】
2019032377.tif 000011
【００４１】
そして、秘密鍵である元ｆを用いて、以下の式（１０）を用いて、暗号文ｃを平文ｍに復号化する。
【００４２】
【数１０】
2019032377.tif 000012
【００４３】
このような格子暗号において、格子空間Ｒを回転行列により回転させることで、生成装置１００は、格子暗号の堅牢化を図る。まず、生成装置１００は、公開鍵ｈを生成する場合、式（４）に代えて、以下の式（１１）を用いる。ここで、ｖは、格子空間を回転させる所定の回転行列である。すなわち、生成装置１００は、回転行列を用いて、秘密鍵として選択した元ｆの逆行列を回転させる。そして、生成装置１００は、生成した公開鍵ｈと
秘密鍵ｆと、回転行列ｖとを復号化装置２００に提供する。
【００４４】
【数１１】
2019032377.tif 000013
【００４５】
一方、復号化装置２００は、公開鍵ｈを暗号化装置３００へと送信する。このような場合、暗号化装置３００は、式（１１）を用いた公開鍵ｈを用いて、以下の式（１２）、すなわち、従来の格子暗号と同様の処理を実行することで、平文ｍを暗号文ｈへと変換する。
【００４６】
【数１２】
2019032377.tif 000014
【００４７】
また、復号化装置２００は、上述した式（８）に代えて、以下の式（１３）を用いて、ベクトルｄの値を算出する。
【００４８】
【数１３】
2019032377.tif 000015
【００４９】
ここで、上述した式（１３）に、式（１１）および式（１２）を代入した場合、ベクトルｄは、以下の式（１４）で示すことができる。
【００５０】
【数１４】
2019032377.tif 000016
【００５１】
また、式（１４）で示されるベクトルｄの係数を式（９）に示す範囲とした場合、ベクトルｄ’は、以下の式（１５）で示すことができる。
【００５２】
【数１５】
2019032377.tif 000017
【００５３】
このような式（１５）を式（１０）に代入すると、式（１６）を得ることができる。そこで、復号化装置２００は、上述した式（１３）を用いてベクトルｄを算出し、ベクトルｄの係数を上述した式（９）の範囲に揃えるとともに、式（１６）を用いて、平文ｍを生成する。すなわち、復号化装置２００は、秘密鍵と暗号文と回転行列の逆行列との積を第２係数で除算した剰余のベクトルの係数を所定の範囲内に収めたベクトルｄ’を算出し、算出したベクトルｄ’と、秘密鍵の逆行列と、回転行列の逆行列との積を第２係数で除算した剰余の値を平文として算出する。
【００５４】
【数１６】
2019032377.tif 000018
【００５５】
〔１−４．回転行列について〕
ここで、生成装置１００は、格子空間であるＲを回転させることができるｎ次回転行列であれば、任意の手法により算出された行列を回転行列ｖとして採用可能である。例えば、生成装置１００は、上述した非特許文献１に開示された手法により、格子空間であるＲを回転させる回転行列ｖを生成し、生成した回転行列ｖを用いて、公開鍵ｈの生成を行えばよい。
【００５６】
〔１−５．処理の一例〕
次に、図１を用いて、生成処理、暗号化処理および復号化処理の一例について説明する。まず、生成装置１００は、格子暗号の格子空間を所定の回転行列で回転させた回転格子空間の基底ベクトルを用いて、秘密鍵と公開鍵とを生成する（ステップＳ１）。例えば、生成装置１００は、格子空間Ｒから基底ベクトルとなるベクトルｆおよびベクトルｇを選択する。ここで、生成装置１００は、ベクトルｆおよびベクトルｇとして、格子空間Ｒにおいて可能な限り直行するベクトルを選択する。また、生成装置１００は、格子空間Ｒを回転させる回転行列ｖを生成する。
【００５７】
そして、生成装置１００は、上述した式（１１）を用いて、公開鍵ｈを生成する。より具体的には、生成装置１００は、所定の第１係数と、基底ベクトルであるベクトルｇと、回転行列と、秘密鍵である基底ベクトルｆの逆行列との積を第２係数で除算した剰余を、秘密鍵ｈとして算出する。すなわち、生成装置１００は、格子空間Ｒではなく、格子空間Ｒを回転行列によって回転させた回転格子空間における基底ベクトルを用いて、公開鍵ｈを生成する。
【００５８】
また、生成装置１００は、生成した公開鍵ｈと、秘密鍵ｆとともに、回転行列ｖの逆行列ｖ−１を復号化装置２００に提供する（ステップＳ２）。また、復号化装置２００は、公開鍵ｈを暗号化装置３００に送信する（ステップＳ３）。
【００５９】
ここで、暗号化装置３００は、平文ｍを取得する（ステップＳ４）。このような場合、暗号化装置３００は、上述した式（１２）を用いて、平文ｍから暗号文ｃを生成する（ステップＳ５）。より具体的には、暗号化装置３００は、秘密鍵ｈに乱数ｒを積算した値と、平文ｍを第２係数で除算した剰余との和を暗号文ｃとして算出する。そして、暗号化装置３００は、暗号文ｃを復号化装置２００へと送信する（ステップＳ６）。
【００６０】
一方、復号化装置２００は、暗号文ｃを受信した場合は、暗号文ｃを復号する（ステップＳ７）。例えば、復号化装置２００は、上述した式（１３）を用いて、ベクトルｄを算出する。すなわち、復号化装置２００は、秘密鍵ｆと暗号文ｃと回転行列の逆行列ｖ−１との積を第２係数で除算した剰余をベクトルｄとして算出する。そして、復号化装置２００は、ベクトルｄから係数を揃えたベクトルｄ’を算出し、上述した式（１６）を用いて、ベクトルｄ’から平文ｍを算出する（ステップＳ８）。
【００６１】
なお、上述したベクトルｆ、ベクトルｇ、秘密鍵ｈ、暗号文ｃ、平文ｍは、それぞれベクトルや行列等の多次元量により実現される。
【００６２】
〔２．生成装置、暗号化装置および復号化装置の構成の一例〕
以下、上記した生成処理を実行する生成装置１００、上述した復号化処理を実行する復号化装置２００、および上述した暗号化処理を実行する暗号化装置３００が有する機能構成の一例について説明する。図２は、実施形態に係る生成装置、復号化装置および暗号化装置の構成例を示す図である。
【００６３】
図２に示す例では、生成装置１００は、通信部１２０、記憶部１３０、制御部１４０を有する。また、復号化装置２００は、通信部２２０、記憶部２３０、制御部２４０を有する。また、暗号化装置３００は、通信部３２０、記憶部３３０、制御部３４０を有する。
【００６４】
通信部１２０、２２０、３２０は、例えば、ＮＩＣ（Network  Interface  Card）等によって実現される。そして、通信部１２０、２２０、３２０は、ネットワークＮと有線または無線で接続され、生成装置１００、復号化装置２００、および暗号化装置３００間の情報の送受信を実現する。
【００６５】
記憶部１３０、２３０、３３０は、例えば、ＲＡＭ（Random  Access  Memory)、フラッシュメモリ（Flash  Memory）等の半導体メモリ素子、または、ハードディスク、光ディスク等の記憶装置によって実現される。ここで、記憶部２３０は、生成装置１００によって生成された秘密鍵２３１、公開鍵２３２、および回転行列の逆行列２３３を記憶する。また、記憶部３３０は、公開鍵２３２を記憶する。
【００６６】
制御部１４０、２４０、３４０は、コントローラ（controller）であり、例えば、ＣＰＵ（Central  Processing  Unit）、ＭＰＵ（Micro  Processing  Unit）等のプロセッサによって、生成装置１００、復号化装置２００、および暗号化装置３００内部の記憶装置に記憶されている各種プログラムがＲＡＭ等を作業領域として実行されることにより実現される。また、制御部１４０、２４０、３４０は、コントローラ（controller）であり、例えば、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）等の集積回路により実現されてもよい。
【００６７】
図２に示すように、制御部１４０は、生成部１４１および出力部１４２を有する。また、制御部２４０は、受信部２４１および復号化部２４２を有する。また、制御部３４０は、平文受付部３４１および暗号化部３４２を有する。
【００６８】
生成部１４１は、多項式環を用いて定義される格子による格子空間を所定の回転行列で回転させた回転格子空間の基底ベクトルを用いて、公開鍵暗号における公開鍵を生成する。例えば、生成部１４１は、格子空間Ｒを設定するとともに、格子空間Ｒを回転させる回転行列ｖを生成する。また、生成部１４１は、格子空間Ｒから基底ベクトルとなるベクトルｆおよびベクトルｇを生成し、生成したベクトルｆを秘密鍵とする。また、生成部１４１は、第１係数ｐおよび第２係数ｑを設定する。なお、第１係数と第２係数とは、素数であり、第２係数は、第１係数と比較して十分に大きいことが望ましい。
【００６９】
そして、生成部１４１は、上述した式（１１）を用いて、公開鍵ｈを生成する。すなわち、生成部１４１は、格子空間Ｒから選択された第１の基底ベクトル（すなわち、ベクトルｆ）を秘密鍵とし、格子空間Ｒから選択された第２の基底ベクトル（すなわち、ベクトルｇ）と、回転行列ｖと、秘密鍵であるベクトルｆの逆行列との積に基づいて、公開鍵ｈを生成する。より具体的には、生成部１４１は、第１係数ｐと、ベクトルｇと、回転行列ｖと、ベクトルｆの逆行列ｆ−１との積を、第２係数ｑで除算した剰余を秘密鍵ｈとして算出する。
【００７０】
出力部１４２は、生成された公開鍵を出力する。例えば、出力部１４２は、秘密鍵ｆと、公開鍵ｈと、回転行列ｖの逆行列ｖ−１と、第１係数ｐと、第２係数ｑとを復号化装置３００へと送信する。
【００７１】
受信部２４１は、暗号化装置３００により暗号化された暗号文ｃを受信する。例えば、受信部２４１は、生成装置１００から、秘密鍵ｆと、公開鍵ｈと、回転行列ｖの逆行列ｖ−１と、第１係数ｐと、第２係数ｑとを受信すると、秘密鍵ｆと、公開鍵ｈと、回転行列ｖの逆行列ｖ−１とを記憶部２３０に秘密鍵２３１、公開鍵２３２、および逆行列２３３として登録する。また、受信部２４１は、暗号化装置３００から公開鍵の送信要求を受付けた場合は、公開鍵２３２と、第２係数とを暗号化装置３００へと送信する。そして、受信部２４１は、暗号化装置３００が公開鍵２３２を用いて生成した暗号文を受信する。
【００７２】
復号化部２４２は、秘密鍵２３１と、暗号文ｃと、回転行列の逆行列ｖ−１との積を第２係数で除算した剰余に基づいて、平文を復号化する。例えば、復号化部２４２は、暗号文ｃが受信された場合、式（１３）を用いて、ベクトルｄの値を算出する。
【００７３】
例えば、復号化部２４２は、秘密鍵２３１と、暗号文ｃと、回転行列の逆行列ｖ−１との積を第２係数で除算した剰余のベクトルｄを生成する。続いて、復号化部２４２は、ベクトルｄの係数を式（９）の範囲に収めたベクトルｄ’を算出し、上述した式（１６）を用いて、平文ｍを復号化する。より具体的には、復号化部２４２は、ベクトルｄ’と、秘密鍵の逆行列ｆ−１と、回転行列の逆行列ｖ−１との積を第１係数で除算した剰余のベクトルを平文ｍとして生成する。そして、復号化部２４２は、利用者が利用する端末装置や画面などの出力装置（図示は省略）に平文ｍを出力する。
【００７４】
平文受付部３４１は、暗号化の対象となる平文ｍを受付ける。例えば、平文受付部３４１は、利用者が利用する端末装置やキーボード等の入力装置（図示は省略）から、平文ｍの入力を受付ける。
【００７５】
暗号化部３４２は、暗号化処理を実行する。より具体的には、暗号化部３４２は、生成装置１００により生成された公開鍵ｈと所定の乱数との積算値に、平文ｍを第２係数ｑで除算した剰余を加算することで平文ｍを暗号化する。例えば、暗号化部３４２は、平文ｍが受け付けられた場合は、公開鍵ｈの送信を復号化装置２００に要求する。このような場合、暗号化部３４２は、公開鍵２３２と第２係数ｑとを復号化装置２００から受付ける。
【００７６】
続いて、暗号化部３４２は、乱数ｒを設定し、秘密鍵ｈと乱数ｒとの積に、平文ｍを第２係数ｑで除算した剰余を加算したベクトルを暗号文ｃとして算出する。すなわち、暗号化部３４２は、上述した式（１２）を用いて、暗号文を生成する。そして、暗号化部３４２は、暗号文ｃを復号化装置２００へと送信する。
【００７７】
〔３．生成処理の流れの一例〕
次に、図３を用いて、生成装置１００が実行する生成処理の流れの一例について説明する。図３は、実施形態に係る生成処理の流れの一例を説明するフローチャートである。例えば、生成装置１００は、格子空間Ｒを所定の回転行列ｖで回転させた回転格子空間の基底ベクトルを選択する（ステップＳ１０１）。すなわち、生成装置１００は、格子空間Ｒの基底ベクトルｇと回転行列ｖとの積を算出する。続いて、生成装置１００は、基底ベクトルを用いて、格子暗号における秘密鍵ｆと公開鍵ｈとを生成する（ステップＳ１０２）。例えば、生成装置１００は、格子空間Ｒにおける基底ベクトルｆを秘密鍵とし、第１係数ｐと、基底ベクトルｇと回転行列ｖとの積と、秘密鍵ｆの逆行列ｆ−１との積を第２係数ｑで除算した剰余を秘密鍵ｈとする。そして、生成装置１００は、生成した秘密鍵ｆと、公開鍵ｈと、回転行列ｖの逆行列ｖ−１とを復号化装置２００に提供し（ステップＳ１０３）、処理を終了する。
【００７８】
〔４．復号化処理の流れの一例〕
次に、図４を用いて、復号化装置２００が実行する復号化処理の流れの一例について説明する。図４は、実施形態に係る復号化処理の流れの一例を説明するフローチャートである。例えば、復号化装置２００は、公開鍵を暗号化装置３００に提供する（ステップＳ２０１）。このような場合、暗号化装置３００は、公開鍵を用いて、暗号文ｃを生成する。そして、復号化装置２００は、暗号文ｃを受信する（ステップＳ２０２）。
【００７９】
ここで、復号化装置２００は、秘密鍵ｆと、暗号文ｃと、回転行列ｖの逆行列ｖ−１とを用いて、暗号文ｃを復号する（ステップＳ２０３）。そして、復号化装置２００は、復号化した平文ｍを出力し（ステップＳ２０４）、処理を終了する。
【００８０】
〔５．変形例〕
上記では、生成処理、暗号化処理および復号化処理の一例について説明した。しかしながら、実施形態は、これに限定されるものではない。以下、生成処理、暗号化処理および復号化処理のバリエーションについて説明する。
【００８１】
〔５−１．装置構成〕
上述した例では、復号化装置２００は、生成装置１００が生成した暗号鍵を用いて、暗号化通信を実現した。しかしながら、実施形態は、これに限定されるものではない。例えば、復号化装置２００は、生成装置１００の機能を有していてもよい。すなわち、復号化装置２００は、暗号化通信を行う際、生成装置１００と同様の生成処理を実行することで暗号鍵を生成し、生成した暗号鍵のうち公開鍵を暗号化装置３００へと提供してもよい。このような場合、復号化装置２００は、例えば、図２に示す生成装置１００が有する生成部１４１を有していてもよい。
【００８２】
〔５−２．その他〕
また、上記実施形態において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上記文書中や図面中で示した処理手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。例えば、各図に示した各種情報は、図示した情報に限られない。
【００８３】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【００８４】
また、上記してきた各実施形態は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【００８５】
〔５−３．プログラム〕
また、上述してきた実施形態に係る生成装置１００、復号化装置２００、および暗号化装置３００は、例えば図５に示すような構成のコンピュータ１０００によって実現される。図５は、ハードウェア構成の一例を示す図である。コンピュータ１０００は、出力装置１０１０、入力装置１０２０と接続され、演算装置１０３０、一次記憶装置１０４０、二次記憶装置１０５０、出力ＩＦ（Interface）１０６０、入力ＩＦ１０７０、ネットワークＩＦ１０８０がバス１０９０により接続された形態を有する。
【００８６】
演算装置１０３０は、一次記憶装置１０４０や二次記憶装置１０５０に格納されたプログラムや入力装置１０２０から読み出したプログラム等に基づいて動作し、各種の処理を実行する。一次記憶装置１０４０は、ＲＡＭ等、演算装置１０３０が各種の演算に用いるデータを一次的に記憶するメモリ装置である。また、二次記憶装置１０５０は、演算装置１０３０が各種の演算に用いるデータや、各種のデータベースが登録される記憶装置であり、ＲＯＭ(Read  Only  Memory)、ＨＤＤ、フラッシュメモリ等により実現される。
【００８７】
出力ＩＦ１０６０は、モニタやプリンタといった各種の情報を出力する出力装置１０１０に対し、出力対象となる情報を送信するためのインタフェースであり、例えば、ＵＳＢ（Universal  Serial  Bus）やＤＶＩ（Digital  Visual  Interface）、ＨＤＭＩ（登録商標）（High  Definition  Multimedia  Interface）といった規格のコネクタにより実現される。また、入力ＩＦ１０７０は、マウス、キーボード、およびスキャナ等といった各種の入力装置１０２０から情報を受信するためのインタフェースであり、例えば、ＵＳＢ等により実現される。
【００８８】
なお、入力装置１０２０は、例えば、ＣＤ（Compact  Disc）、ＤＶＤ（Digital  Versatile  Disc）、ＰＤ（Phase  change  rewritable  Disk）等の光学記録媒体、ＭＯ（Magneto-Optical  disk）等の光磁気記録媒体、テープ媒体、磁気記録媒体、または半導体メモリ等から情報を読み出す装置であってもよい。また、入力装置１０２０は、ＵＳＢメモリ等の外付け記憶媒体であってもよい。
【００８９】
ネットワークＩＦ１０８０は、ネットワークＮを介して他の機器からデータを受信して演算装置１０３０へ送り、また、ネットワークＮを介して演算装置１０３０が生成したデータを他の機器へ送信する。
【００９０】
演算装置１０３０は、出力ＩＦ１０６０や入力ＩＦ１０７０を介して、出力装置１０１０や入力装置１０２０の制御を行う。例えば、演算装置１０３０は、入力装置１０２０や二次記憶装置１０５０からプログラムを一次記憶装置１０４０上にロードし、ロードしたプログラムを実行する。
【００９１】
例えば、コンピュータ１０００が生成装置１００として機能する場合、コンピュータ１０００の演算装置１０３０は、一次記憶装置１０４０上にロードされたプログラムを実行することにより、制御部１４０の機能を実現する。また、例えば、コンピュータ１０００が復号化装置２００として機能する場合、コンピュータ１０００の演算装置１０３０は、一次記憶装置１０４０上にロードされたプログラムを実行することにより、制御部２４０の機能を実現する。また、例えば、コンピュータ１０００が暗号化装置３００として機能する場合、コンピュータ１０００の演算装置１０３０は、一次記憶装置１０４０上にロードされたプログラムを実行することにより、制御部３４０の機能を実現する。
【００９２】
〔６．効果〕
上述したように、生成装置１００は、多項式環を用いて定義される格子による格子空間Ｒを所定の回転行列Ｖで回転させた回転格子空間の基底ベクトルを用いて、公開鍵暗号における公開鍵ｈを生成する。そして、生成装置１００は、生成された公開鍵ｆを出力する。この結果、生成装置１００は、秘密鍵を用いずに暗号文を復号する際に、格子暗号における暗号文のベクトルの最近傍の格子点を求めるという最短ベクトル問題のみならず、格子空間をどれくらい回転させたかという問題をも含めることができるので、格子暗号の堅牢性を向上させることができる。
【００９３】
また、生成装置１００は、格子空間Ｒから選択された第１の基底ベクトルｆを秘密鍵とし、格子空間Ｒから選択された第２の基底ベクトルｇと、回転行列ｖと、秘密鍵ｆの逆行列ｆ−１との積に基づいて、公開鍵ｈを生成する。例えば、生成装置１００は、第１係数ｐと、第２の基底ベクトルｇと、回転行列ｖと、秘密鍵ｆの逆行列ｆ−１との積を第２素数ｑで除算した剰余を公開鍵ｈとして算出する。このため、生成装置１００は、回転行列ｖを反映させた格子暗号における公開鍵を提供することができる。
【００９４】
また、暗号化装置３００は、暗号化の対象となる平文ｍを受付ける。そして、暗号化装置３００は、生成装置１００により生成された公開鍵ｈ、すなわち、回転行列ｖにより回転させられた格子空間Ｒの基底ベクトルを用いた公開鍵ｈと所定の乱数ｒとの積算値に、平文ｍを第２係数ｑで除算した剰余を加算することで平文を暗号化する。このため、暗号化装置３００は、回転行列ｖを反映させた格子暗号における公開鍵で、平文を暗号化するので、解析がより困難な暗号文を出力することができる。
【００９５】
また、復号化装置２００は、暗号化装置３００により暗号化された暗号文ｃを受信する
。そして、復号化装置２００は、秘密鍵ｆと、暗号文ｃと、回転行列ｖの逆行列ｖ−１との積を第２係数ｑで除算した剰余であるベクトルｄに基づいて、平文ｍを復号化する。このため、復号化装置２００は、回転行列ｖを反映させた格子暗号における公開鍵で暗号化された暗号文ｃを、適切に復号化することができる。
【００９６】
以上、本願の実施形態のいくつかを図面に基づいて詳細に説明したが、これらは例示であり、発明の開示の欄に記載の態様を始めとして、当業者の知識に基づいて種々の変形、改良を施した他の形態で本発明を実施することが可能である。
【００９７】
また、上記してきた「部（section、module、unit）」は、「手段」や「回路」などに読み替えることができる。例えば、特定部は、特定手段や特定回路に読み替えることができる。
【符号の説明】
【００９８】
１００  生成装置
２００  復号化装置
３００  暗号化装置
１２０、２２０、３２０  通信部
１３０、２３０、３３０  記憶部
１４０、２４０、３４０  制御部
２３１  秘密鍵
２３２  公開鍵
２３３  逆行列
１４１  生成部
１４２  出力部
２４１  受信部
２４２  復号化部
３４１  平文受付部
３４２  暗号化部
【図１】
2019032377.tif 000019
【図２】
2019032377.tif 000020
【図３】
2019032377.tif 000021
【図４】
2019032377.tif 000022
【図５】
2019032377.tif 000023