(57)【特許請求の範囲】
【請求項１】
落とし戸付関数による暗号化対象のメッセージを、2のべき乗を要素とするベクトルとの内積を取ることで符号化したものと、離散ガウス分布に従う要素から成るエラーベクトルとを足し合わせた入力ベクトルを受け付け、前記入力ベクトルに基づいて前記メッセージの下位から複数のビットを所定の確率で正しく復号する複数ビット復号部と、
復号された複数のビットが正しいか否かを並列に判定する確認計算部と、を備える、
ことを特徴とする復号装置。
【請求項２】
前記確認計算部は、前記エラーベクトルに含まれる要素がとり得る値の範囲に基づいて、復号された複数のビットが正しいか否かを判定する、
請求項１に記載の復号装置。
【請求項３】
前記確認計算部は、復号された複数のビットが下位ビットから何ビットまで正しいかを判定する、
請求項１または２に記載の復号装置。
【請求項４】
前記確認計算部は、復号された複数のビットのうちの誤りと判定された最下位のビットを反転し、
前記複数ビット復号部は、前記メッセージを構成するビットのうちの、前記最下位のビットの１ビット上位のビットから上位側の複数のビットを、前記入力ベクトルに基づいて復号する、
請求項３に記載の復号装置。
【請求項５】
コンピュータが、落とし戸付関数による暗号化対象のメッセージを、2のべき乗を要素とするベクトルとの内積を取ることで符号化したものと、離散ガウス分布に従う要素から成るエラーベクトルとを足し合わせた入力ベクトルを受け付けるステップと、
前記入力ベクトルに基づいて前記メッセージの下位から複数のビットを所定の確率で正しく復号するステップと、
復号された複数のビットが正しいか否かを並列に判定するステップと、を含む、
ことを特徴とする復号方法。
【請求項６】
前記エラーベクトルに含まれる要素がとり得る値の範囲に基づいて、復号された複数のビットが正しいか否かを判定する、
請求項５に記載の復号方法。
【請求項７】
復号された複数のビットが下位ビットから何ビットまで正しいかを判定するステップを含む、
請求項５または６に記載の復号方法。
【請求項８】
復号された複数のビットのうちの誤りと判定された最下位のビットを反転するステップと、
前記メッセージを構成するビットのうちの、前記最下位のビットの１ビット上位のビットから上位側の複数のビットを、前記入力ベクトルに基づいて復号するステップと、を含む、
請求項７に記載の復号方法。
【請求項９】
落とし戸付関数による暗号化対象のメッセージを、2のべき乗を要素とするベクトルとの内積を取ることで符号化したものと、離散ガウス分布に従う要素から成るエラーベクトルとを足し合わせた入力ベクトルを受け付ける処理と、
前記入力ベクトルに基づいて前記メッセージの下位から複数のビットを所定の確率で正しく復号する処理と、
復号された複数のビットが正しいか否かを並列に判定する処理と、をコンピュータに実行させる、
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、復号装置、復号方法およびプログラムに関し、特に格子暗号および署名に用いられる落とし戸（trapdoor）付関数における復号装置、復号方法およびプログラムに関する。
【背景技術】
【０００２】
落とし戸付関数とは、鍵生成処理、関数計算処理、および、逆関数計算処理から成る手続きであり、特に公開鍵暗号や署名において使用される。格子を用いた暗号（格子暗号）や署名は、計算の簡潔性に基づく効率性と、基本演算の線形性から生じる準同型と、量子計算機による攻撃が発見されていない安全性を有する暗号として、鋭意研究が進められている。【０００３】
非特許文献１には、格子暗号および署名における落とし戸付関数の構成法として代表的なものが記載されている。【０００４】
ここで、非特許文献１における落とし戸付関数の構成法について詳細に説明する。なお、非特許文献１および本発明では、演算はqを2べきの整数q = 2K（Kは自然数）として
0006624307.tif 000002
（以下、Zq= Z/qZとも表す。）
において行うものとする。【０００５】
まず、非特許文献１による構成法において重要な役割を果たす「原始格子行列」について述べる。原始格子行列Gは
0006624307.tif 000003
によって表される行列である。ここで、ベクトル
0006624307.tif 000004
（以下、gとも表す。）
は、2のべき乗を要素とするベクトルである。この原子格子行列Gを用いて、鍵生成処理、関数計算処理、および、逆関数計算処理が行われる。以下、（１）鍵生成処理、（２）関数計算処理、および、（３）逆関数計算処理の具体的内容について説明する。【０００６】
（１）鍵生成処理
非特許文献１では、鍵生成処理を以下のように構成する。鍵生成処理は、N∈Zをセキュリティパラメータとし、パラメータ
0006624307.tif 000005
を入力として受け付ける。また、鍵生成処理は、「公開鍵」となる行列と、「落とし戸」（ないし「秘密鍵」）となる行列を出力する。ここで、O, ωはランダウの記号である。また、αは
0006624307.tif 000006
を満たす数である。【０００７】
まず、公開鍵の生成手続きについて述べる。公開鍵は、各成分がZqである行列として
0006624307.tif 000007
として構成される。ここで、(E|F)なる表記は２つの行列E, Fを横に並べたものを表す。
また、行列
0006624307.tif 000008
は、
0006624307.tif 000009
から一様にサンプルしたものである。さらに、行列HはZqN×Nの正則行列である。また、行列
0006624307.tif 000010
は、各列ベクトルを次に説明する分散値σである
0006624307.tif 000011
上の離散ガウス分布から生成した行列とする。ここで「分散値がσのZN上の離散ガウス分布」とは、実数
0006624307.tif 000012
により定まる関数
0006624307.tif 000013
を用いて、整数値
0006624307.tif 000014
を確率
0006624307.tif 000015
で出力した分布をいう。以下、かかる離散ガウス分布をDZN,σと表す。【０００８】
鍵生成処理では、最後に公開鍵Aと、落とし戸（ないし秘密鍵）となる行列Rを出力する。【０００９】
（２）関数計算処理
関数計算処理は、入力として、前述のように生成した公開鍵Aと、パラメータparamと、メッセージに相当するベクトル
0006624307.tif 000016
（以下mとも表す。）を受け付ける。また、関数計算処理は、離散ガウス分布から
0006624307.tif 000017
（以下eとも表す。）をとり、ベクトル
0006624307.tif 000018
を出力する（以下cとも表す。）。【００１０】
（３）逆関数計算処理
逆関数計算処理は、入力として関数計算処理で生成されたベクトルcを受け付ける。次に、ベクトルcに対して、行列
0006624307.tif 000019
を右から作用させる。ここで、ベクトルcに上記行列を作用させた結果をベクトルbと表す。このとき、ベクトルbは
0006624307.tif 000020
となる。なお、最右辺において
0006624307.tif 000021
とした。すなわち、ベクトルbはmHを原子格子行列Gによって符号化したものにエラーベクトル
0006624307.tif 000022
（以下εとも表す。）を加えたデータとなる。ここで、エラーベクトルεの各成分は、秘密鍵である行列Rとベクトルeを適当な分布からとることで、ほぼ確実に(-q/4, q/4]の範囲に含まれることに留意する。すなわち、エラーベクトルεの各成分が(-q/4, q/4]の範囲外となる確率を無視することができる。したがって、ベクトルmHが求まれば、逆行列H-1を右から作用させることで、メッセージmが求まることになる。本発明は、ベクトルbからmHを復号する処理に関するものであるため、行列Hを単位行列としても一般性は失われない。そこで、以下では行列Hを単位行列として扱う。【００１１】
以上より、メッセージmの復号処理は、結局、ベクトルbの誤り訂正（Error Correction）処理に帰着する。そこで、以下では、誤り訂正処理によってベクトルbからメッセージmを復号する手続きについて詳述する。【００１２】
また、この誤り訂正はメッセージｍ= (m0, ..., mN-1)の成分mi(i = 0, …, N-1)ごとに実行される。そこで、以下ではメッセージの第１成分m0∈Zqの復号処理についてのみ説明する。メッセージmの他の成分m1, …, mN-1も第１成分m0と同様に復号できるからである。さらに、ベクトルbについても、メッセージmの第1成分m0の復号に関係する最初のK個の成分（b0, …, bK-1）のみに着目する。【００１３】
以下では、メッセージmの第1成分m0はビット展開したときに
0006624307.tif 000023
と表されるものとする。非特許文献１に記載された誤り訂正処理は、次のとおりである。【００１４】
「非特許文献１の誤り訂正（ステップＡ１）」
ベクトルbの第K番目の成分は
0006624307.tif 000024
である。ここで、エラーベクトルの成分は
0006624307.tif 000025
を満たすから、メッセージmの第1成分m0の最下位（下位から1番目）のビットm0,0は一意に復号できる。【００１５】
「非特許文献１の誤り訂正（ステップＡ２）」
次に、ベクトルbの第（K-1）番目の成分は
0006624307.tif 000026
である。ここで、ステップＡ１でm0,0は復号済（既知）であり、エラーベクトルの成分は
0006624307.tif 000027
であるから、第1成分m0の下位から2番目のビットm0,1を復号することができる。【００１６】
「非特許文献１の誤り訂正（ステップＡ３）」
以下同様にして、メッセージmの第1成分m0のすべてのビット（m0,0, …, m0,K-1）を復号する。【００１７】
以上が、非特許文献１における逆関数計算処理である。【００１８】
非特許文献１では、このような鍵生成処理、関数計算処理および逆関数計算処理を行うことで、落とし戸付関数を構成している。【００１９】
なお、関連技術として、特許文献１には、複数ビットを一括して復号化処理する算術復号化装置が記載されている。
【先行技術文献】
【特許文献】
【００２０】
【特許文献１】特開２００５−２１７８７１号公報
【非特許文献】
【００２１】
【非特許文献１】Daniele Micciancio, Chris Peikert, “Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller,” [online]、2011年（平成23年）9月14日、EUROCRYPTO 2012, pp.700-718,［2016年（平成28年）11月17日検索］、インターネット〈URL：http://eprint.iacr.org/2011/501〉
【発明の概要】
【発明が解決しようとする課題】
【００２２】
特許文献１および非特許文献１の全開示内容は、本書に引用をもって繰り込み記載されているものとする。以下の分析は、本発明者によってなされたものである。【００２３】
非特許文献１による復号処理では、Kビットのメッセージを復号するのにK回のビット復号処理が必要となる。すなわち「非特許文献１の誤り訂正（ステップＡ１〜Ａ３）」というビットごとの逐次復号処理が必要であり、並列処理による高速化ができないという問題がある。【００２４】
なお、特許文献１に記載された算術復号化装置は、複数ビットを一括して復号化処理可能かどうか判定した上で、可能であれば一括復号処理を行うものであり、非特許文献１における上記の問題を解決することには寄与しない。【００２５】
そこで、落とし戸付関数の復号処理を高速化することが課題となる。本発明の目的は、かかる課題解決に寄与する復号装置、復号方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００２６】
本発明の第１の態様に係る復号装置は、落とし戸付関数による暗号化対象のメッセージを、2のべき乗を要素とするベクトルとの内積を取ることで符号化したものと、離散ガウス分布に従う要素から成るエラーベクトルとを足し合わせた入力ベクトルを受け付け、前記入力ベクトルに基づいて前記メッセージの下位から複数のビットを所定の確率で正しく復号する複数ビット復号部と、復号された複数のビットが正しいか否かを並列に判定する確認計算部と、を備えている。【００２７】
本発明の第２の態様に係る復号方法は、コンピュータが、落とし戸付関数による暗号化対象のメッセージを、2のべき乗を要素とするベクトルとの内積を取ることで符号化したものと、離散ガウス分布に従う要素から成るエラーベクトルとを足し合わせた入力ベクトルを受け付けるステップと、前記入力ベクトルに基づいて前記メッセージの下位から複数のビットを所定の確率で正しく復号するステップと、復号された複数のビットが正しいか否かを並列に判定するステップと、を含む。【００２８】
本発明の第３の態様に係るプログラムは、落とし戸付関数による暗号化対象のメッセージを、2のべき乗を要素とするベクトルとの内積を取ることで符号化したものと、離散ガウス分布に従う要素から成るエラーベクトルとを足し合わせた入力ベクトルを受け付ける処理と、前記入力ベクトルに基づいて前記メッセージの下位から複数のビットを所定の確率で正しく復号する処理と、復号された複数のビットが正しいか否かを並列に判定する処理と、をコンピュータに実行させる。なお、プログラムは、非一時的なコンピュータ可読記録媒体（non-transitory computer-readable storage medium）に記録されたプログラム製品として提供することもできる。
【発明の効果】
【００２９】
本発明に係る復号装置、復号方法およびプログラムによると、落とし戸付関数の復号処理を高速化することができる。
【図面の簡単な説明】
【００３０】
【図１】一実施形態に係る復号装置の構成を例示するブロック図である。
【図２】第１の実施形態に係る復号装置の構成を例示するブロック図である。
【図３】第１の実施形態の復号装置における複数ビット復号部の構成を例示するブロック図である。
【図４】第１の実施形態の復号装置における確認計算部の構成を例示するブロック図である。
【図５】第１の実施形態の復号装置における最終ビット復号部の構成を例示するブロック図である。
【図６】第１の実施形態に係る復号装置の動作を例示するフロー図である。
【図７】複数ビット復号部における推定値計算部の手続きを説明するための図である。
【図８】確認計算部における閾値判定部の手続きを説明するための図である。
【図９】情報処理装置の構成を例示するブロック図である。
【発明を実施するための形態】
【００３１】
はじめに、一実施形態の概要について説明する。なお、この概要に付記する図面参照符号は、専ら理解を助けるための例示であり、本発明を図示の態様に限定することを意図するものではない。
【００３２】
図１を参照すると、一実施形態に係る復号装置９０は、複数ビット復号部１００および確認計算部１１０を備えている。複数ビット復号部１００は、落とし戸付関数による暗号化対象のメッセージ（例えば上述のメッセージm）を、2のべき乗を要素とするベクトル（例えば上述のベクトルg=(1, 2, …, 2K-1)）との内積を取ることで符号化したものと、離散ガウス分布に従う要素から成るエラーベクトル（例えば上述のエラーベクトルε）とを足し合わせた入力ベクトル（例えば上述のベクトルb）を受け付ける。また、複数ビット復号部１００は、入力ベクトル（例えばベクトルbの（K-L+1）番目の成分bK-L）に基づいてメッセージ（例えばメッセージmの第1成分m0）の下位から複数のビット（例えば第1成分m0をビット展開したときの下位からLビットm0,0, …, m0, L-1）を所定の確率（例えばエラーベクトルεの成分εK-Lが後述する所定の範囲に含まれる確率）で正しく復号する。さらに、確認計算部１１０は、復号された複数のビットが正しいか否かを並列に判定する。
【００３３】
非特許文献１に記載された誤り訂正（ステップＡ１〜Ａ３）では、メッセージ（例えばメッセージmの第1成分m0）を構成する複数のビット（m0,0, …, m0,K-1）を逐次的に復号することで、基本的には復号したビットに誤りが含まれないようにしつつ、メッセージを復号化する。一方、一実施形態に係る復号装置では、メッセージ（例えばメッセージmの第1成分m0）を構成する複数のビット（例えばLビットm0,0, …, m0,L-1）を一括して復号する際に、復号したビットに誤りが含まれることを許容する。さらに、一実施形態に係る復号装置では、復号した複数のビットに誤りが含まれるか否かを並列に判定する。一実施形態によると、Lビットごと一括して復号することで、復号の回数をK/L回程度にまで削減することができる。また、復号したビットにおける誤りの有無の判定は、L個のプロセッサを用いた並列計算によって1ビット相当の計算時間で処理することができる。したがって、一実施形態によると、落とし戸付関数の復号処理を、非特許文献１と比較して大幅に高速化することが可能となる。
【００３４】
以下、一実施形態における復号方法について、さらに詳細に説明する。
【００３５】
「非特許文献１の誤り訂正（ステップＡ１〜Ａ３）」については、メッセージmの第1成分m0の復号法のみ説明すれば十分であった。同様の理由から、本発明の一実施形態についても第1成分m0の復号法についてのみ説明する。また、ベクトル
0006624307.tif 000028
に関しても、メッセージmの第1成分m0の復号に関係する最初のK個の成分（b0, …, bK-1）のみに着目する。
【００３６】
まず、一実施形態における復号処理手続きの概略構成について述べる。以下では、所定のパラメータL（ただし、LはK以下の正の整数とする）を用いる。
【００３７】
非特許文献１の復号処理では、第1成分m0のビットごとに逐次的に復号操作を行う。一方、本発明の一実施形態では、非特許文献１の復号処理における誤り訂正（ステップＡ１〜Ａ３）を、以下に概説する「誤り訂正（ステップＢ１〜Ｂ３）」に基づく操作に置き換える。
【００３８】
「誤り訂正（ステップＢ１）」：第1成分m0を構成する複数のビット（Lビットとする）を一度に計算する。
「誤り訂正（ステップＢ２）」：ステップＢ１の計算結果のうちLビットの中で何ビットまでが正しいかを判定する。
「誤り訂正（ステップＢ３）」：ステップＢ２による判定で誤りと判定された最下位の桁を反転させて、ステップＢ１に戻る。
また、本発明の一実施形態では、上記ステップＢ２の判定において並列計算を用いる。
【００３９】
このとき、ほぼK/L回の繰り返しのビット復号操作により、第1成分m0を構成するすべてのビット（Kビット）の復号を行うことができる。したがって、一実施形態によると、非特許文献１に記載された復号処理を大幅に高速化することが可能となる。
【００４０】
以下では、上記の復号手続きの詳細について説明する。
【００４１】
「誤り訂正（ステップＢ１）」
複数ビット（Lビット）を一括して復号する操作について述べる。ベクトルbの（K-L+1）番目の成分bK-Lについて
0006624307.tif 000029
が成り立つ。ここで、エラーベクトルの成分εK-Lはある確率で（Lを適当な値とすることで、相当に高い確率で）
0006624307.tif 000030
となる。ここでは、エラーベクトルの成分εK-Lがこの範囲に含まれるものと仮定し、ベクトルbの成分bK-Lから一括して第1成分m0の複数のビットm0,0, …, m0, L-1を推測する。ここで、推測値をtnewとおく。すなわち、tnew= m0,0+2m0,1+…+2L-1m0, L-1とする。
【００４２】
「誤り訂正（ステップＢ２）」
「誤り訂正（ステップＢ１）」で推測した値tnewの何ビット目までが正しいかを判定する。具体的には、以下のようにして判定する。
ベクトルbの（K-L+1）番目からK番目の各成分bi (i = K-L, K-L+1, …, K-1)についてbi - 2i tnewを並列に計算し、以下のようにして、フラグJiを定義する。
0006624307.tif 000031
ここでbK-I0からbK-1までのbiについてフラグJi = 1である（すなわち、ビットm0,0からビットm0,I0-1までのI0ビット分が正しく求められた）場合、I0を出力する（なお、I0をI0とも表す）。一方、フラグJi = 1となるiが存在しない場合（すなわち、すべてのiについてフラグJi = 0の場合）、I0 = 0とする。
【００４３】
「誤り訂正（ステップＢ３）」
「誤り訂正（ステップＢ１）」での推測値のうち、「誤り訂正（ステップＢ２）」での判定を基に正しい復号値を以下のように計算する。I0 ≠ Lのとき、tnewの（I0+1）番目のビットm0,I0を反転させて、tnewのうちの下位ビットから（I0+1）ビット分をtとして出力する。一方、I0 = Lのとき、tnewをそのままtとして出力する。
【００４４】
「誤り訂正（ステップＢ４）」
次の復号も、「誤り訂正（ステップＢ１）」から「誤り訂正（ステップＢ３）」と同様の操作を行う。具体的には、以下のように計算する。tのビット数を|t|と表したとき、ベクトルbの次のLビット(bK-|t|-L, …, bK-|t|-1)に注目する。ベクトルbの（K-|t|-L+1）番目の成分bK-|t|-Lについて
0006624307.tif 000032
が成り立つ。ここで、エラーベクトルの成分εK-|t|-Lはある確率で（Lを適当な値とすることで、相当に高い確率で）
0006624307.tif 000033
となる。そこで、エラーベクトルの成分εK-|t|-Lがこの範囲に含まれるものと仮定し、ベクトルbの成分bK-|t|-Lに基づいて、第1成分m0の（|t|+1）ビット目m0,|t|から（L+|t|）ビット目m0,L+|t|-1までを一括して推測してtnewとする。
【００４５】
推測したtnewおよび(bK-|t|-L, …, bK-|t|-1)に対して、上述の「誤り訂正（ステップＢ２）」と「誤り訂正（ステップＢ３）」で行った手続きを実行する。具体的には、ベクトルbの（K-|t|-L+1）番目の成分から（K-|t|）番目の各成分bi (i = K-|t|-L, …, K-|t|-1)についてbi - 2i tnewを並列に計算し、以下のようにして、フラグJiを定義する。
0006624307.tif 000034
ここでbK-|t|-I0からbK-|t|-1までのbiについてフラグJi = 1である（すなわち、ビットm0,|t|からビットm0,|t|+I0-1までのI0ビット分が正しく求められた）場合、I0を出力する。一方、フラグJi = 1となるiが存在しない場合（すなわち、すべてのiについてフラグJi = 0の場合）、I0 = 0とする。
【００４６】
I0 ≠ Lの場合、tnewの（|t|+I0+1）番目のビットm0,|t|+I0を反転させて、tnewのうちの下位ビットから（|t|+I0+1）ビット分をtとして出力する。一方、I0 = Lの場合、tnewをそのままtとして出力する。
【００４７】
「誤り訂正（ステップＢ５）」
「誤り訂正（ステップＢ４）」で求められたtのビット数が（K-L）ビットより大きくなるまで「誤り訂正（ステップＢ４）」を繰り返す。
【００４８】
「誤り訂正（ステップＢ６）」
「誤り訂正（ステップＢ５）」までは、メッセージmの第1成分m0についてLビットごとに一括して復号を行った。一方、第1成分m0について復号すべきKビットのうち、残りのビット数が（L-1）ビット以下となった場合、残りのビット（L-1ビット以下）を一括して復号する。具体的には、次のようにする。
【００４９】
ベクトルbの残りの（K-|t|）ビット(b0, …, bK-|t|-1)に注目する。ベクトルbの1番目の成分b0について
0006624307.tif 000035
が成り立つ。ここで、エラーベクトルの成分ε0はある確率で（（K-|t|）の値に応じて相当に高い確率で）
0006624307.tif 000036
となる。そこで、エラーベクトルの成分ε0がこの範囲に含まれるものと仮定し、ベクトルbの成分b0に基づいて、第1成分m0の（|t|+1）ビット目m0,|t|からKビット目m0,K-1までを推測してtnewとする。推測したtnewおよび(b0, …, bK-|t|-1)に対して、上述の「誤り訂正（ステップＢ４）」の手続きを実行する。
【００５０】
具体的には、ベクトルbの1番目の成分から（K-|t|）番目の各成分bi (i = 0, …, K-|t|-1)についてbi - 2i tnewを並列に計算し、以下のようにして、フラグJiを定義する。
0006624307.tif 000037
ここでbK-|t|-I0からbK-|t|-1までのbiについてフラグJi = 1である（すなわち、ビットm0,|t|からビットm0,|t|+I0-1までのI0ビット分が正しく求められた）場合、I0を出力する。一方、フラグJi = 1となるiが存在しない場合（すなわち、すべてのiについてフラグJi = 0の場合）、I0 = 0とする。
【００５１】
I0 ≠ K-|t|の場合、tnewの（|t|+I0+1）番目のビットm0,|t|+I0を反転させて、tnewのうちの下位ビットから（|t|+I0+1）ビット分をtとして出力する。一方、I0 = K-|t|の場合、tnewをそのままtとして出力する。
【００５２】
こうして求めたtのビット数がKである場合、tをそのまま出力する。一方、実行後のtのビット数がKに満たない場合、tのビット数がKとなるまで、「非特許文献１の誤り訂正（ステップＡ１〜Ａ３）」に従って1ビットごとに逐次的に復号を行う。
【００５３】
以上で述べた方法により、メッセージmの第1成分m0のすべてのビット（Kビット）の復号処理が可能となる。
【００５４】
一実施形態によると、Lビットごとにまとめて復号することにより、「非特許文献１の誤り訂正（ステップＡ１〜Ａ３）」のような逐次的なビット復号操作の繰り返しの回数を削減することが可能となる。
【００５５】
［効果］
一実施形態によると、落とし戸付き関数の復号において、複数ビットをまとめて復号し、復号結果を並列処理によりチェックすることで、復号処理の高速化が可能となる。
【００５６】
その理由は、非特許文献１に記載された方式ではビットごとの逐次処理であったのに対し、一実施形態では、1回のループでLビットごとまとめて復号し、復号結果のエラーチェックと組み合わせることで、ほぼK/L回の逐次処理で復号することができるからである。非特許文献１の方式では、逐次復号された結果には実質的に誤りが生じない。一方、一実施形態によると、Lビットごとまとめて復号値を推定することで、無視できない確率で誤りが生じ得る。この誤りを検知するために、エラーチェックを用いる。ここで、一実施形態で採用したエラーチェックはビットごとに独立かつ並列に行える方式であり、ビット列を下位から見た場合に最初にエラーが発生したビットを特定するものである。このエラーチェックをL個の計算ユニットにより並列実行した場合、実質的には非特許文献１に記載された方式の1ビット復号程度の処理時間で処理することが可能となる。したがって、一実施形態によると、エラーチェックも含めた全体の復号計算時間を、非特許文献１の方式のK/Lビット分の復号の時間にまで短縮することが可能となる。
【００５７】
＜実施形態１＞
次に、第１の実施形態に係る復号装置ついて図面を参照して詳細に説明する。
【００５８】
［構成］
図２を参照すると、本実施形態の復号装置９０は、複数ビット復号部１００、確認計算部１１０、最終ビット復号部１２０、および、出力部１３０を備えている。復号装置９０は、例えばプログラム制御により動作するコンピュータ（ないし情報処理装置）によって実現することもできる。
【００５９】
ここでは、記号として
0006624307.tif 000038
をセキュリティパラメータとして、以下のパラメータ
0006624307.tif 000039
を用いる。行列Gは、背景技術で述べた原始格子行列を表すものとする。また、行列Rは
0006624307.tif 000040
を用いて
0006624307.tif 000041
とする。ここで、
0006624307.tif 000042
は、背景技術で述べた離散ガウス分布を表す。
【００６０】
復号装置９０に入力される入力データ（入力ベクトル）
0006624307.tif 000043
（以下bとも表す。）は、次のように表される。すなわち、入力ベクトルbは、メッセージに相当するベクトル
0006624307.tif 000044
（以下mとも表す。）、および、離散ガウス分布
0006624307.tif 000045
から生成されたベクトルeを用いて
0006624307.tif 000046
という形で表される。図２を参照すると、入力ベクトルbは、複数ビット復号部１００、確認計算部１１０、および、最終ビット復号部１２０にそれぞれ入力される。
【００６１】
メッセージm = (m0, …, mN-1)の各成分mi (i = 0, …, N-1)は、いずれも同様の手続きにより復号される。したがって、以下では、メッセージmの第1成分m0の復号についてのみ説明する。
【００６２】
ここでは、メッセージmの第1成分m0はビット展開したときに
0006624307.tif 000047
と表されるものとする。
【００６３】
複数ビット復号部１００は、上述の「誤り訂正（ステップＢ１）」および「誤り訂正（ステップＢ４）」のように、第1成分m0の複数のビット（例えばLビット）を一括して復号する。確認計算部１１０は、上述の「誤り訂正（ステップＢ２）」〜「誤り訂正（ステップＢ４）」のように、複数ビット復号部１００によって復号されたデータ（tnew）と与えられたデータ（入力ベクトルb）を参照し、正しく復号されたビット数を求め、正しく復号されたビットから成るデータを生成する。最終ビット復号部１２０は、上述の「誤り訂正（ステップＢ６）」のように、復号が完了していないデータを復号する。出力部１３０は、復号結果を出力する。
【００６４】
図３を参照すると、複数ビット復号部１００は、入力部１０１、Ｌビットデータ作成部１０２、および、推測値計算部１０３を備えている。入力部１０１は、入力データとして、第1成分m0のうちの正しく復号済のデータtと入力ベクトルbを受け取る。Ｌビットデータ作成部１０２は、「誤り訂正（ステップＢ４）」における推測値を計算する処理の事前計算として、推測に用いるデータを生成する。すなわち、Ｌビットデータ作成部は、
ベクトルbの（K-|t|-L+1）番目の成分bK-|t|-Lについて
0006624307.tif 000048
を求める。推測値計算部１０３は、Ｌビットデータ作成部１０２によって計算されたデータから第1成分m0の（|t|+1）ビット目m0,|t|から（L+|t|）ビット目m0,L+|t|-1までのLビットを推測してtnewとする。推定値計算部１０３は、推測したtnewを確認計算部１１０に出力する。
【００６５】
図４を参照すると、確認計算部１１０は、入力部１１１、閾値判定部１１２、および、復号値生成部１１３を備えている。入力部１１１は、入力データとして、推測値計算部１０３が推測したtnewと入力ベクトルbを受け付ける。閾値判定部１１２は上述の「誤り訂正（ステップＢ２）」および「誤り訂正（ステップＢ４）」の処理を行い、推測したLビットのうちの何ビットまでが正しいかを判定し、正しく求められたビット数I0を算出する。復号値生成部１１３は上述の「誤り訂正（ステップＢ３）」および「誤り訂正（ステップＢ４）」の処理を行い、閾値判定部１１２による判定結果に基づいて正しい復号値tを生成する。復号値生成部１１３は、復号値tのビット数が（K-L）ビットより大きい（すなわち、未復号のビット数が（L-1）ビット以下）の場合、復号値tを最終ビット復号部１２０に出力する。それ以外の場合、復号値生成部１１３は、復号値tを複数ビット復号部１００に出力する。
【００６６】
図５を参照すると、最終ビット復号部１２０は、入力部１２１、複数ビット復号部１２２、閾値判定部１２３、復号値生成部１２４、および、ビット復号部１２５を備えている。入力部１２１は、入力データとして復号値生成部１１３により生成された復号値tと入力ベクトルbを受け付ける。複数ビット復号部１２２は、「誤り訂正（ステップＢ６）」で説明したように、残るビットを一括で復号する。閾値判定部１２３は、復号したビットのうちの何ビットまでが正しいかを判定する。復号値生成部１２４は、閾値判定部１２３による判定結果に基づいて正しい復号値を計算する。ビット復号部１２５は、残りのビットを逐次復号する。
【００６７】
［動作］
次に、本実施形態の復号装置９０および各部の動作について、図６のフロー図を参照して説明する。
【００６８】
Ｌビットデータ作成部１０２は、既に正しく復号されたデータtに基づいて、次のLビット分の復号値を推測するために必要となるデータ
0006624307.tif 000049
を作成して、推測値計算部１０３へ送出する。ここで、|t|はデータtのビット数を表す。
【００６９】
推測値計算部１０３は、bK-|t|-L-2K-|t|-Ltの上位から始まるLビットまでをビットシフトを用いて、まとめて推定復号し、（|t|+L）ビットまでの推測値tnewを計算する（図６のステップＳ１）。具体的には、推測値計算部１０３は、上述の「誤り訂正（ステップＢ４）」のように、エラーベクトルの成分εK-|t|-Lが所定の範囲内に含まれるものと仮定して（図７）、第1成分m0の（|t|+1）ビット目m0,|t|から（L+|t|）ビット目m0,L+|t|-1までを推測してtnewとする。また、推測値計算部１０３は、計算した推測値tnewを確認計算部１１０の入力部１１１へ出力する（図３および図４）。
【００７０】
確認計算部１１０の入力部１１１は、tnewおよび入力ベクトルbを入力データとして受け付ける。確認計算部１１１の閾値判定部１１２は、入力ベクトルbの（K-|t|-L+1）番目の成分から（K-|t|）番目の各成分biについてbi-2itnewを並列に計算し、各iについて[-q/4, q/4)の範囲に入るか否かを並列に判定する。閾値判定部１１２は、すべてのi < I0で条件（bi-2itnew ∈[-q/4, q/4)）を満たすような最大のI0を求める（図６のステップＳ２、図８）。なお、かかる条件を満たすiが存在しない場合、I0 = 0とする。また、閾値判定部１１２は、tnewとI0を復号値生成部１１３に送出する。
【００７１】
復号値生成部１１３は、閾値判定部１２３から、データtnewとI0を受信する。I0 ≠ Lの場合（図６のステップＳ３のＮｏ）、復号値生成部１１３はtnewの（|t|+I0+1）番目のビットを反転させて、tnewの（|t|+I0+1）ビットをtとして出力する（図６のステップＳ４）。一方、I0 = Lの場合（図６のステップＳ３のＹｅｓ）、復号値生成部１１３はtnewをそのままtとして出力する。
【００７２】
ここで、復号値生成部１１３は、tの出力先を次のように選択する。tのビット数が（K-L）ビットよりも大きい場合（図６のステップＳ５のＹｅｓ）、復号値生成部１１３はtを最終ビット復号部１２０に送出する（図２）。一方、tのビット数が（K-L）ビット以下の場合（図６のステップＳ５のＮｏ）、復号値生成部１１３はtを複数ビット復号部１００に送出する（図２）。
【００７３】
最終ビット復号部１２０の入力部１２１は、復号値生成部１１３からデータbおよびtを受け取る（図５参照）。最終ビット復号部１２０の複数ビット復号部１２２、閾値判定部１２３、および、復号値生成部１２４は、それぞれ、複数ビット復号部１００（図３参照）、確認計算部１１０（図４参照）の閾値判定部１１２、および、復号値生成部１１３と同様の手続きを実行する。
【００７４】
すなわち、複数ビット復号部１２２は、複数ビット復号部１００と同様の処理を行い、残りの（K-|t|）ビット（Lビット未満）を一括で復号する（図６のステップＳ６）。具体的には、複数ビット復号部１２２は上述の「誤り訂正（ステップＢ６）」のように第1成分m0の（|t|+1）ビット目m0,|t|からKビット目m0,K-1までを推測してtnewとする。
【００７５】
また、閾値判定部１２３は、確認計算部１１０の閾値判定部１１２と同様の処理を行い、複数ビット復号部１２２が推定した復号値のうちの正しいビット部分を判定する（図６のステップＳ７）。具体的には、閾値判定部１２３は、複数ビット復号部１２２により推測されたtnewと入力ベクトルbの成分(b0, …, bK-|t|-1)に対して、上述の「誤り訂正（ステップＢ４）」の手続きを実行し、正しいビット部分を判定し、求めたI0を復号値生成部１２４に出力する。
【００７６】
さらに、復号値生成部１２４は、確認計算部１１０の復号値生成部１１３（図４）と同様の処理を行い、閾値判定部１２３による判定結果に基づいて、正しい復号値tを生成する。具体的には、復号値生成部１２４は、上述の「誤り訂正（ステップＢ４）」の手続きを実行して、I0 ≠ K-|t|の場合、tnewの（|t|+I0+1）番目のビットm0,|t|+I0を反転させて、tnewの（|t|+I0+1）ビットをtとしてビット復号部１２５に出力する。一方、復号値生成部１２４は、I0 = K-|t|の場合、tnewをtとしてビット復号部１２５に出力する。
【００７７】
ビット復号部１２５は、|t| ≠ Kの場合、残りの（K-|t|）ビットについて「非特許文献１の誤り訂正（ステップＡ１〜Ａ３）」の手続きを用いて、逐次的に復号を行い第1成分m0のすべてのビット（Kビット）の復号を完了させる（図６のステップＳ８）。
【００７８】
［効果］
本実施形態によると、落とし戸付き関数の復号において、メッセージを構成する複数のビットをまとめて復号し、復号結果のエラーチェックを並列計算で行うことで、非特許文献１に記載された復号処理と比較して高速な復号処理が可能となる。
【００７９】
その理由は、本実施形態では、1回のループ（すなわち図２の複数ビット復号部１００と確認計算部１１０の間のループ、図６のステップＳ１〜Ｓ５のループ）においてLビットごとまとめて復号し、並列計算に基づく復号結果のエラーチェックと組み合わせることで、ほぼK/L回の逐次処理でメッセージのすべてのビットを復号することができるからである。
【００８０】
＜変形例＞
次に、上記の実施形態に係る復号装置９０の変形例について説明する。上記の実施形態に係る復号装置９０は、図９に示す情報処理装置８０に基づいて実現してもよい。
【００８１】
情報処理装置８０は、中央処理装置（ＣＰＵ：Central Processing Unit）８１およびメモリ８２を有する。図９には１つのＣＰＵ８１のみを示したが、情報処理装置８０は複数のＣＰＵを備えていてもよいし（マルチプロセッサ）、複数の演算コアを１チップに搭載したマルチコアプロセッサを備えていてもよい。
【００８２】
情報処理装置８０は、メモリ８２に記憶されているプログラムをＣＰＵ８１が実行することにより、復号装置９０が有する複数ビット復号部１００、確認計算部１１０、最終ビット復号部１２０、および出力部１３０の機能の一部または全部を実現する。特に、確認計算部１１０の閾値判定部１１２（図４）による判定処理（図６のステップＳ２）と、最終ビット復号部１２０の閾値判定部１２３（図５）による判定処理（図６のステップＳ７）を、複数のＣＰＵまたは複数の演算コアを用いて並列に実行することで、非特許文献１と比較して復号処理を高速化することが可能となる。
【００８３】
なお、特許文献１および非特許文献１の全開示内容は、本書に引用をもって繰り込み記載されているものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の全開示の枠内において種々の開示要素（各請求項の各要素、各実施形態の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【００８４】
８０    情報処理装置
８１    ＣＰＵ
８２    メモリ
９０    復号装置
１００    複数ビット復号部
１０１    入力部
１０２    Ｌビットデータ作成部
１０３    推測値計算部
１１０    確認計算部
１１１    入力部
１１２    閾値判定部
１１３    復号値生成部
１２０    最終ビット復号部
１２１    入力部
１２２    複数ビット復号部
１２３    閾値判定部
１２４    復号値生成部
１２５    ビット復号部
１３０    出力部
【図１】
0006624307.tif 000050
【図２】
0006624307.tif 000051
【図３】
0006624307.tif 000052
【図４】
0006624307.tif 000053
【図５】
0006624307.tif 000054
【図６】
0006624307.tif 000055
【図７】
0006624307.tif 000056
【図８】
0006624307.tif 000057
【図９】
0006624307.tif 000058