(57)【要約】【課題】ＮＴＲＵ暗号の復号処理を高速化すると共に、秘密鍵のサイズを小さくする。【解決手段】環Ｒ＝Ｚ［ｘ］／（ｆ（ｘ））（ただし、ｆ（ｘ）は所定のｎ次多項式）の部分集合をＤｆ及びＤｇ、ｐ＜ｑを互いに素な正整数、ｆ´及びｇ´を前記Ｒの要素として、前記Ｄｆからランダムに選択された要素ｆ＝ｐ・ｆ´と、前記Ｄｇからランダムに選択された要素ｇ＝１＋ｐ・ｇ´と、法ｑでの前記ｆの逆元Ｆｑとを用いて、ｈ＝ｇ・Ｆｑ（ｍｏｄ  ｑ）を公開鍵、前記ｆを秘密鍵として生成する鍵生成手段と、前記Ｒの部分集合をＤｒとして、前記Ｄｒから選択された要素ｒと、前記ｈとを用いて、暗号化メッセージｃ＝ｒｏｕｎｄｐ（ｈ・ｒ）を生成する暗号化手段と、前記暗号化メッセージｃを用いて、ａ＝ｆ・ｃ（ｍｏｄ  ｑ）を計算した後、ｒ＝ａ（ｍｏｄ  ｐ）を計算することで、前記暗号化メッセージｃを復号する復号手段と、を有することを特徴とする。【選択図】図４
2019200382.tif 000002
【特許請求の範囲】
【請求項１】
環Ｒ＝Ｚ［ｘ］／（ｆ（ｘ））（ただし、ｆ（ｘ）は所定のｎ次多項式）の部分集合をＤｆ及びＤｇ、ｐ＜ｑを互いに素な正整数、ｆ´及びｇ´を前記Ｒの要素として、前記Ｄｆからランダムに選択された要素ｆ＝ｐ・ｆ´と、前記Ｄｇからランダムに選択された要素ｇ＝１＋ｐ・ｇ´と、法ｑでの前記ｆの逆元Ｆｑとを用いて、ｈ＝ｇ・Ｆｑ（ｍｏｄ  ｑ）を公開鍵、前記ｆを秘密鍵として生成する鍵生成手段と、
前記Ｒの部分集合をＤｒとして、前記Ｄｒから選択された要素ｒと、前記ｈとを用いて、暗号化メッセージｃ＝ｒｏｕｎｄｐ（ｈ・ｒ）を生成する暗号化手段と、
前記暗号化メッセージｃを用いて、ａ＝ｆ・ｃ（ｍｏｄ  ｑ）を計算した後、ｒ＝ａ（ｍｏｄ  ｐ）を計算することで、前記暗号化メッセージｃを復号する復号手段と、
を有することを特徴とする暗号化システム。
【請求項２】
前記鍵生成手段は、
前記ｈを公開鍵、前記ｆ及び前記ｈを秘密鍵として生成し、
前記暗号化手段は、
前記Ｄｒからランダムに選択された要素ｒと、前記ｈと、所定のハッシュ関数Ｈとを用いて、ｃ１＝ｒｏｕｎｄｐ（ｈ・ｒ）と、（ｃ２，Ｋ）＝Ｈ（ｒ）とを計算し、暗号化メッセージｃ＝（ｃ１，ｃ２）と、共有鍵Ｋとを生成し、
前記復号手段は、
前記暗号化メッセージｃを用いて、ａ＝ｆ・ｃ  （ｍｏｄ  ｑ）を計算した後、ｒ´＝ａ  （ｍｏｄ  ｐ）を計算し、
前記ｒ´を用いて、ｃ１´＝ｒｏｕｎｄｐ（ｈ・ｒ´）と、（ｃ２´，Ｋ´）＝Ｈ（ｒ´）とを計算することで、共有鍵Ｋ＝Ｋ´を生成する、
ことを特徴とする請求項１に記載の暗号化システム。
【請求項３】
前記復号手段は、
前記ｒ´が前記Ｄｒの要素であり、かつ、（ｃ１，ｃ２）＝（ｃ１´，ｃ２´）である場合に、前記Ｋ´を共有鍵Ｋとして生成し、
前記ｒ´が前記Ｄｒの要素でない又は／及び（ｃ１，ｃ２）＝（ｃ１´，ｃ２´）でない場合、復号失敗とする、
ことを特徴とする請求項２に記載の暗号化システム。
【請求項４】
環Ｒ＝Ｚ［ｘ］／（ｆ（ｘ））（ただし、ｆ（ｘ）は所定のｎ次多項式）の部分集合をＤｒ、ｐ＜ｑを互いに素な正整数として、復号装置により生成された公開鍵ｈと、前記Ｄｒから選択された要素ｒとを用いて、暗号化メッセージｃ＝ｒｏｕｎｄｐ（ｈ・ｒ）を生成する暗号化手段と、
前記暗号化手段により生成された暗号化メッセージｃを前記復号装置に送信する送信手段と、
を有することを特徴とする暗号化装置。
【請求項５】
環Ｒ＝Ｚ［ｘ］／（ｆ（ｘ））（ただし、ｆ（ｘ）は所定のｎ次多項式）の部分集合をＤｆ及びＤｇ、ｐ＜ｑを互いに素な正整数、ｆ´及びｇ´を前記Ｒの要素として、前記Ｄｆからランダムに選択された要素ｆ＝ｐ・ｆ´と、前記Ｄｇからランダムに選択された要素ｇ＝１＋ｐ・ｇ´と、法ｑでの前記ｆの逆元Ｆｑとを用いて、ｈ＝ｇ・Ｆｑ（ｍｏｄ  ｑ）を公開鍵、前記ｆを秘密鍵として生成する鍵生成手段と、
前記ｈを用いて暗号化装置により暗号化された暗号化メッセージｃを受信する受信手段と、
前記受信手段により受信された暗号化メッセージｃを用いて、ａ＝ｆ・ｃ（ｍｏｄ  ｑ）を計算した後、ｒ＝ａ（ｍｏｄ  ｐ）を計算することで、前記暗号化メッセージｃを復号する復号手段と、
を有することを特徴とする復号装置。
【請求項６】
環Ｒ＝Ｚ［ｘ］／（ｆ（ｘ））（ただし、ｆ（ｘ）は所定のｎ次多項式）の部分集合をＤｒ、ｐ＜ｑを互いに素な正整数として、復号装置により生成された公開鍵ｈと、前記Ｄｒから選択された要素ｒとを用いて、暗号化メッセージｃ＝ｒｏｕｎｄｐ（ｈ・ｒ）を生成する暗号化手順と、
前記暗号化手順により生成された暗号化メッセージｃを前記復号装置に送信する送信手順と、
をコンピュータが実行することを特徴とする暗号化方法。
【請求項７】
環Ｒ＝Ｚ［ｘ］／（ｆ（ｘ））（ただし、ｆ（ｘ）は所定のｎ次多項式）の部分集合をＤｆ及びＤｇ、ｐ＜ｑを互いに素な正整数、ｆ´及びｇ´を前記Ｒの要素として、前記Ｄｆからランダムに選択された要素ｆ＝ｐ・ｆ´と、前記Ｄｇからランダムに選択された要素ｇ＝１＋ｐ・ｇ´と、法ｑでの前記ｆの逆元Ｆｑとを用いて、ｈ＝ｇ・Ｆｑ（ｍｏｄ  ｑ）を公開鍵、前記ｆを秘密鍵として生成する鍵生成手順と、
前記ｈを用いて暗号化装置により暗号化された暗号化メッセージｃを受信する受信手順と、
前記受信手順により受信された暗号化メッセージｃを用いて、ａ＝ｆ・ｃ（ｍｏｄ  ｑ）を計算した後、ｒ＝ａ（ｍｏｄ  ｐ）を計算することで、前記暗号化メッセージｃを復号する復号手順と、
をコンピュータが実行することを特徴とする復号方法。
【請求項８】
コンピュータを、請求項４に記載の暗号化装置における各手段又は請求項５に記載の復号装置における各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化システム、暗号化装置、復号装置、暗号化方法、復号方法、及びプログラムに関する。
【背景技術】
【０００２】
多項式環を用いて定義された格子の最短ベクトル問題の困難性を利用した公開鍵暗号であるＮＴＲＵ暗号が従来から知られている（非特許文献１）。近年では、耐量子暗号の候補として、ＮＴＲＵ暗号が注目されている。
【０００３】
また、ＮＴＲＵ暗号による暗号化においてＲｏｕｎｄ関数を用いることで、復号に要する時間をより高速化させることが可能なＲｏｕｎｄｅｄ  ＮＴＲＵ暗号と呼ばれる手法も知られている（非特許文献２）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman: NTRU: A Ring-Based Public Key Cryptosystem., In ANTS 1998, pages 267-288. 1998.
【非特許文献２】Daniel J. Bernstein, Chitchanok Chuengsatiansup, Tanja Lange, Christine van Vredendaal: NTRU Prime: Reducing Attack Surface at Low Cost. In SAC 2017, pages 235-260. 2017.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、近年では、ＩｏＴ機器等のハードウェア資源が比較的乏しい機器においても通信の暗号化や復号が要請されていることが多い。このため、より高速な処理が可能で、かつ、メモリ使用量が少ないＮＴＲＵ暗号の実現が期待されている。
【０００６】
本発明の実施の形態は、上記の点に鑑みてなされたもので、ＮＴＲＵ暗号の復号処理を高速化すると共に、秘密鍵のサイズを小さくすることを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するため、本発明の実施の形態は、環Ｒ＝Ｚ［ｘ］／（ｆ（ｘ））（ただし、ｆ（ｘ）は所定のｎ次多項式）の部分集合をＤｆ及びＤｇ、ｐ＜ｑを互いに素な正整数、ｆ´及びｇ´を前記Ｒの要素として、前記Ｄｆからランダムに選択された要素ｆ＝ｐ・ｆ´と、前記Ｄｇからランダムに選択された要素ｇ＝１＋ｐ・ｇ´と、法ｑでの前記ｆの逆元Ｆｑとを用いて、ｈ＝ｇ・Ｆｑ（ｍｏｄ  ｑ）を公開鍵、前記ｆを秘密鍵として生成する鍵生成手段と、前記Ｒの部分集合をＤｒとして、前記Ｄｒから選択された要素ｒと、前記ｈとを用いて、暗号化メッセージｃ＝ｒｏｕｎｄｐ（ｈ・ｒ）を生成する暗号化手段と、前記暗号化メッセージｃを用いて、ａ＝ｆ・ｃ（ｍｏｄ  ｑ）を計算した後、ｒ＝ａ（ｍｏｄ  ｐ）を計算することで、前記暗号化メッセージｃを復号する復号手段と、を有することを特徴とする。
【発明の効果】
【０００８】
本発明の実施の形態によれば、ＮＴＲＵ暗号の復号処理を高速化すると共に、秘密鍵のサイズを小さくすることができる。
【図面の簡単な説明】
【０００９】
【図１】本発明の実施の形態における暗号化システムの全体構成の一例を示す図である。
【図２】本発明の実施の形態における暗号化装置及び復号装置のハードウェア構成の一例を示す図である。
【図３】本発明の実施の形態における暗号化システムの機能構成の一例を示す図である。
【図４】本発明の実施の形態における暗号化及び復号処理の一例を示すシーケンス図（実施例１）である。
【図５】本発明の実施の形態における暗号化及び復号処理の一例を示すシーケンス図（実施例２）である。
【発明を実施するための形態】
【００１０】
以下、本発明の実施の形態について説明する。本発明の実施の形態では、ＮＴＲＵ暗号の復号処理を高速化すると共に、秘密鍵のサイズを小さくすることが可能な暗号化システム１について説明する。
【００１１】
＜ＮＴＲＵ暗号の従来手法＞
本発明の実施の形態におけるＮＴＲＵ暗号の手法を説明する前に、いくつかのＮＴＲＵ暗号の従来手法について説明する。以降では、ｎをセキュリティパラメータ、Ｒを環であるものとする。環Ｒは、整数係数の多項式環Ｚ［ｘ］を用いて、Ｒ：＝Ｚ［ｘ］／（ｆ（ｘ））と定義される。ここで、（ｆ（ｘ））はｆ（ｘ）が生成するイデアルである。ｆ（ｘ）としては、例えば、ｆ（ｘ）＝ｘｎ−１、ｆ（ｘ）＝ｘｎ＋１、ｆ（ｘ）＝ｘｎ−ｘ−１又はｆ（ｘ）＝ｘｎ＋ｘｎ−１＋・・・＋ｘ＋１等の所定のｎ次多項式であるものとする。
【００１２】
また、ｐ及びｑを、ｐ＜ｑ、かつ、互いに素な正整数であるものとする。このようなｐ及びｑとしては、例えば、ｐ＝３、ｑ＝２１０等が挙げられる。
【００１３】
更に、環Ｒの適当な部分集合をＤとした場合に、環Ｒの要素ｆをＤからランダムに選ぶことを「ｆ←ＲＤ」と表す。また、環Ｒの要素同士の加法を「＋」、乗法を「・」で表す。
【００１４】
（１）ＮＴＲＵ暗号
非特許文献１に開示されているＮＴＲＵ暗号では、以下のように鍵生成、暗号化及び復号が行われる。
【００１５】
（鍵生成）
ｆ←ＲＤｆ、ｇ←ＲＤｇとして、ｈ：＝ｇ・Ｆｑ  （ｍｏｄ  ｑ）を計算する。ここで、Ｄｆ及びＤｇは環Ｒの部分集合、Ｆｑは法ｑでのｆの逆元（すなわち、ｆ・Ｆｑ＝１  （ｍｏｄ  ｑ）となる要素）である。
【００１６】
そして、公開鍵をｈ、秘密鍵をｆ及びＦｐとする。ここで、Ｆｐは法ｐでのｆの逆元（すなわち、ｆ・Ｆｐ＝１  （ｍｏｄ  ｐ）となる要素）である。
【００１７】
なお、Ｆｐを秘密鍵として予め生成しておくのではなく、復号時にｆからＦｐを計算しても良い。ただし、この場合、復号時に、ｆからＦｐを計算するための計算時間を要する。
【００１８】
（暗号化）
（ｒ，ｅ）を用いて、暗号化メッセージｃ：＝ｐ・ｈ・ｒ＋ｅ  （ｍｏｄ  ｑ）を計算する。ここで、ｒは環Ｒの部分集合Ｄｒの要素である。また、ｅは環Ｒの部分集合Ｄｅの要素であり、暗号化対象のメッセージである。（ｒ，ｅ）は、暗号化メッセージの送信側（すなわち、暗号化メッセージを生成及び送信する機器又は装置等）により選ばれる。（ｒ，ｅ）としては、例えば、Ｄｒ及びＤｅを環Ｒの部分集合として、ｒ←ＲＤｒ、ｅをＤｅから選択された要素とすれば良い。なお、Ｄｅは、暗号化対象のメッセージの集合（例えば、平文集合等）である。
【００１９】
（復号）
暗号化メッセージｃの受信側（すなわち、暗号化メッセージを受信及び復号する機器又は装置等）は、以下のＳｔｅｐ１−１及びＳｔｅｐ１−２により暗号化メッセージｃをメッセージｅに復号する。
【００２０】
Ｓｔｅｐ１−１）ａ：＝ｆ・ｃ  （ｍｏｄ  ｑ）を計算する。なお、ｆ・ｃ＝ｐ・ｆ・ｈ・ｒ＋ｆ・ｅ＝ｐ・ｇ・ｒ＋ｆ・ｅ  （ｍｏｄ  ｑ）である。
【００２１】
Ｓｔｅｐ１−２）ｅ：＝ａ・Ｆｐ  （ｍｏｄ  ｐ）を計算する。これにより、メッセージｅが得られる。なお、必要ならば、ｒ＝（ｃ−ｅ）／（ｐ・ｈ）を計算しても良い。
【００２２】
（２）ｆ＝１＋ｐ・ｆ´型のＮＴＲＵ暗号
上記（１）のＮＴＲＵ暗号の手法の一部を変形した従来手法として、ｆを１＋ｐ・ｆ´の形に制限したＮＴＲＵ暗号（このＮＴＲＵ暗号を「ｆ＝１＋ｐ・ｆ´型のＮＴＲＵ暗号」と表す。）がある。ここで、ｆ´は環Ｒの要素である。
【００２３】
この場合、ｆの法ｐでの逆元Ｆｐは必ず１となる。これは、ｆ＝１  （ｍｏｄ  ｐ）となるためである。そのため、ｆ＝１＋ｐ・ｆ´型のＮＴＲＵ暗号では、上記のＮＴＲＵ暗号と比べて、秘密鍵にＦｐを含める必要がなく、かつ、上記のＳｔｅｐ１−２におけるＦｐの乗法が不要となるという利点がある。
【００２４】
（鍵生成）
ｆ＝１＋ｐ・ｆ´←ＲＤｆ、ｇ←ＲＤｇとして、ｈ：＝ｇ・Ｆｑ  （ｍｏｄ  ｑ）を計算する。ここで、Ｄｆ及びＤｇは環Ｒの部分集合、Ｆｑは法ｑでのｆの逆元である。
【００２５】
そして、公開鍵をｈ、秘密鍵をｆとする。
【００２６】
（暗号化）
（ｒ，ｅ）を用いて、暗号化メッセージｃ：＝ｐ・ｈ・ｒ＋ｅ  （ｍｏｄ  ｑ）を計算する。ここで、ｒは環Ｒの部分集合Ｄｒの要素である。また、ｅは環Ｒの部分集合Ｄｅの要素であり、暗号化対象のメッセージである。（ｒ，ｅ）は、暗号化メッセージの送信側により選ばれる。
【００２７】
（復号）
暗号化メッセージｃの受信側は、以下のＳｔｅｐ２−１及びＳｔｅｐ２−２により暗号化メッセージｃをメッセージｅに復号する。
【００２８】
Ｓｔｅｐ２−１）ａ：＝ｆ・ｃ  （ｍｏｄ  ｑ）を計算する。なお、ｆ・ｃ＝ｐ・ｆ・ｈ・ｒ＋ｆ・ｅ＝ｐ・ｇ・ｒ＋（１＋ｐ・ｆ´）・ｅ＝ｅ＋ｐ・（ｇ・ｒ＋ｆ´・ｅ）  （ｍｏｄ  ｑ）である。
【００２９】
Ｓｔｅｐ２−２）ｅ：＝ａ  （ｍｏｄ  ｐ）を計算する。これにより、メッセージｅが得られる。なお、必要ならば、ｒ＝（ｃ−ｅ）／（ｐ・ｈ）を計算しても良い。
【００３０】
（３）Ｒｏｕｎｄｅｄ  ＮＴＲＵ暗号
非特許文献２に開示されているＲｏｕｎｄｅｄ  ＮＴＲＵ暗号では、暗号化の際にＲｏｕｎｄ関数でｅを定義する。すなわち、Ｒｏｕｎｄｅｄ  ＮＴＲＵ暗号では、ｅをｐ・ｈ・ｒから一意に決定する。ここで、Ｒｏｕｎｄ関数をｒｏｕｎｄｐ（・）として、ｒｏｕｎｄｐ（ａ）は、ａ∈Ｚｑについて、最も近いｐの倍数に丸める関数であるものとする。具体的な計算例を挙げると、ｒｏｕｎｄ３（−５）＝−６、ｒｏｕｎｄ３（４）＝３等となる。
【００３１】
（鍵生成）
ｆ＝ｐ・ｆ´←ＲＤｆ、ｇ←ＲＤｇとして、ｈ：＝ｇ・Ｆｑ  （ｍｏｄ  ｑ）を計算する。ここで、Ｄｆ及びＤｇは環Ｒの部分集合、Ｆｑは法ｑでのｆの逆元である。
【００３２】
そして、公開鍵をｈ、秘密鍵をｆ及びＧｐとする。ここで、Ｇｐは法ｐでのｇの逆元（すなわち、ｇ・Ｇｐ＝１  （ｍｏｄ  ｐ）となる要素）である。
【００３３】
（暗号化）
ｒを用いて、暗号化メッセージｃ：＝ｒｏｕｎｄｐ（ｈ・ｒ）を計算する。ここで、ｒは環Ｒの部分集合Ｄｒの要素であり、暗号化対象のメッセージである。ｒは、暗号化メッセージの送信側により選ばれる。ｒとしては、例えば、Ｄｒを環Ｒの部分集合として、ｒをＤｒから選択された要素すれば良い。なお、Ｒｏｕｎｄｅｄ  ＮＴＲＵ暗号では、Ｄｒが暗号化対象のメッセージの集合（例えば、平文集合等）である。
【００３４】
ここで、上述したように、ｒｏｕｎｄｐ（ｈ・ｒ）によりｅが一意に決定される。すなわち、ｒｏｕｎｄｐ（ｈ・ｒ）＝ｈ・ｒ＋ｅである。
【００３５】
（復号）
暗号化メッセージｃの受信側は、以下のＳｔｅｐ３−１〜Ｓｔｅｐ３−３により暗号化メッセージｃをメッセージｒに復号する。
【００３６】
Ｓｔｅｐ３−１）ａ：＝ｆ・ｃ  （ｍｏｄ  ｑ）を計算する。なお、ｆ・ｃ＝（ｐ・ｆ´）・（ｈ・ｒ＋ｅ）＝ｇ・ｒ＋ｐ・ｆ´・ｅ  （ｍｏｄ  ｑ）である。
【００３７】
Ｓｔｅｐ３−２）ａ´：＝ａ  （ｍｏｄ  ｐ）を計算する。なお、ａ＝ｇ・ｒ  （ｍｏｄ  ｐ）である。
【００３８】
Ｓｔｅｐ３−３）ｒ：＝ａ´・Ｇｐ  （ｍｏｄ  ｐ）を計算する。これにより、メッセージｒが得られる。
【００３９】
（４）Ｒｏｕｎｄｅｄ  ＮＴＲＵ暗号＋Ｄｅｎｔ４
上記（３）のＲｏｕｎｄｅｄ  ＮＴＲＵ暗号に対して、以下の参考文献１のＴａｂｌｅ４に記載されている鍵カプセル化メカニズム（ＫＥＭ：Key Encapsulation Mechanism）を適用することもできる。
【００４０】
［参考文献１］
Alexander W. Dent: A Designer's Guide to KEMs, https://eprint.iacr.org/2002/174
上記の鍵カプセル化メカニズムをＲｏｕｎｄｅｄ  ＮＴＲＵ暗号に適用したＮＴＲＵ暗号を「Ｒｏｕｎｄｅｄ  ＮＴＲＵ暗号＋Ｄｅｎｔ４」と表す。
【００４１】
（鍵生成）
ｆ＝ｐ・ｆ´←ＲＤｆ、ｇ←ＲＤｇとして、ｈ：＝ｇ・Ｆｑ  （ｍｏｄ  ｑ）を計算する。ここで、Ｄｆ及びＤｇは環Ｒの部分集合、Ｆｑは法ｑでのｆの逆元である。
【００４２】
そして、公開鍵をｈ、秘密鍵をｈ、ｆ及びＧｐとする。ここで、Ｇｐは法ｐでのｇの逆元である。
【００４３】
（暗号化（鍵カプセル化））
ｒ←ＲＤｒとして、ｃ１：＝ｒｏｕｎｄｐ（ｈ・ｒ）を計算する。また、（ｃ２，Ｋ）：＝Ｈ（ｒ）を計算する。ここで、Ｄｒは環Ｒの部分集合、Ｈ（・）はハッシュ関数である。
【００４４】
そして、ｃ：＝（ｃ１，ｃ２）を暗号化メッセージ、Ｋを共有鍵とする。なお、（ｃ２，Ｋ）は、例えば、Ｈ（ｒ）として得られるビット長をＬ１、共有鍵のビット長をＬ２とした場合、Ｈ（ｒ）として得られたビット列のうち、０ビット目からＬ１−Ｌ２−１ビット目までのビット列をｃ２、Ｌ１−Ｌ２ビット目からＬ１−１ビット目までのビット列をＫとすれば良い。
【００４５】
ここで、上述したように、ｒｏｕｎｄｐ（ｈ・ｒ）によりｅが一意に決定される。すなわち、ｒｏｕｎｄｐ（ｈ・ｒ）＝ｈ・ｒ＋ｅである。
【００４６】
（復号（鍵カプセル化解除））
暗号化メッセージｃの受信側は、以下のＳｔｅｐ４−１〜Ｓｔｅｐ４−５により鍵カプセル化解除を行って、共有鍵を生成する。
【００４７】
Ｓｔｅｐ４−１）ａ：＝ｆ・ｃ  （ｍｏｄ  ｑ）を計算する。なお、ｆ・ｃ＝（ｐ・ｆ´）・（ｈ・ｒ＋ｅ）＝ｇ・ｒ＋ｐ・ｆ´・ｅ  （ｍｏｄ  ｑ）である。
【００４８】
Ｓｔｅｐ４−２）ａ´：＝ａ  （ｍｏｄ  ｐ）を計算する。なお、ａ＝ｇ・ｒ  （ｍｏｄ  ｐ）である。
【００４９】
Ｓｔｅｐ４−３）ｒ´：＝ａ´・Ｇｐ  （ｍｏｄ  ｐ）を計算する。
【００５０】
Ｓｔｅｐ４−４）ｒ´を用いて鍵カプセル化を行って、ｃ１´、ｃ２´及びＫ´を得る。すなわち、ｃ１´：＝ｒｏｕｎｄｐ（ｈ・ｒ´）と、（ｃ２´，Ｋ´）：＝Ｈ（ｒ´）とを計算して、ｃ１´、ｃ２´及びＫ´を得る。
【００５１】
Ｓｔｅｐ４−５）ｒ´∈Ｄｒ、かつ、（ｃ１，ｃ２）＝（ｃ１´，ｃ２´）である場合、Ｋ´を共有鍵とする。これより、暗号化メッセージｃの受信側と送信側との間で共有鍵Ｋ＝Ｋ´が共有される。なお、ｒ´∈Ｄｒ及び（ｃ１，ｃ２）＝（ｃ１´，ｃ２´）の少なくとも一方を満たさない場合、復号失敗（鍵カプセル化解除失敗）とする。
【００５２】
＜本発明の実施の形態におけるＮＴＲＵ暗号の手法＞
次に、本発明の実施の形態におけるＮＴＲＵ暗号の手法は、上記（３）のＲｏｕｎｄｅｄ  ＮＴＲＵ暗号を改良して、秘密鍵をｆとしたものである。これにより、上記（３）のＲｏｕｎｄｅｄ  ＮＴＲＵ暗号と比べて、秘密鍵としてＧｐを保存する必要がなく、かつ、上記のＳｔｅｐ３−３が不要になるという利点がある。すなわち、本発明の実施の形態におけるＮＴＲＵ暗号の手法では、復号処理の高速化させることができると共に、秘密鍵のサイズを小さくすることができる。
【００５３】
（鍵生成）
ｆ＝ｐ・ｆ´←ＲＤｆ、ｇ＝１＋ｐ・ｇ´←ＲＤｇとして、ｈ：＝ｇ・Ｆｑ  （ｍｏｄ  ｑ）を計算する。ここで、Ｄｆ及びＤｇは環Ｒの部分集合、ｇ´は環Ｒの要素、Ｆｑは法ｑでのｆの逆元である。
【００５４】
そして、公開鍵をｈ、秘密鍵をｆとする。このように、上記（３）のＲｏｕｎｄｅｄ  ＮＴＲＵ暗号と比べて、秘密鍵としてＧｐが不要であるため、秘密鍵のサイズを小さくすることができる。言い換えれば、秘密鍵の保存に必要な記憶領域を小さくすることができる。なお、ｆに加えて、ｇも秘密鍵としても良い。
【００５５】
（暗号化）
ｒを用いて、暗号化メッセージｃ：＝ｒｏｕｎｄｐ（ｈ・ｒ）を計算する。ここで、ｒは環Ｒの部分集合Ｄｒの要素であり、暗号化対象のメッセージである。ｒは、暗号化メッセージの送信側により選ばれる。ｒとしては、例えば、Ｄｒを環Ｒの部分集合として、ｒをＤｒから選択された要素すれば良い。なお、本発明の実施の形態におけるＮＴＲＵ暗号では、上記（３）のＲｏｕｎｄｅｄ  ＮＴＲＵ暗号と同様に、Ｄｒが暗号化対象のメッセージの集合（例えば、平文集合等）である。
【００５６】
ここで、上記（３）のＲｏｕｎｄｅｄ  ＮＴＲＵ暗号と同様に、ｒｏｕｎｄｐ（ｈ・ｒ）によりｅが一意に決定される。すなわち、ｒｏｕｎｄｐ（ｈ・ｒ）＝ｈ・ｒ＋ｅである。
【００５７】
（復号）
暗号化メッセージｃの受信側は、以下のＳｔｅｐ５−１〜Ｓｔｅｐ５−３により暗号化メッセージｃをメッセージｒに復号する。
【００５８】
Ｓｔｅｐ５−１）ａ：＝ｆ・ｃ  （ｍｏｄ  ｑ）を計算する。なお、ｆ・ｃ＝（ｐ・ｆ´）・（ｈ・ｒ＋ｅ）＝ｐ・ｆ´・ｈ・ｒ＋ｐ・ｆ´・ｅ＝（１＋ｐ・ｇ´）・ｒ＋ｐ・ｆ´・ｅ＝ｒ＋ｐ・（ｇ´・ｒ＋ｆ´・ｅ）  （ｍｏｄ  ｑ）
Ｓｔｅｐ５−２）ｒ：＝ａ  （ｍｏｄ  ｐ）を計算する。これにより、メッセージｒが得られる。このように、上記（３）のＲｏｕｎｄｅｄ  ＮＴＲＵ暗号と比べて、上記のＳｔｅｐ３−３が不要であるため、復号処理をより高速に行うことができるようになる。
【００５９】
＜本発明の実施の形態におけるＮＴＲＵ暗号＋Ｄｅｎｔ４の手法＞
本発明の実施の形態におけるＮＴＲＵ暗号に対して、上記の参考文献１のＴａｂｌｅ４に記載されている鍵カプセル化メカニズムを適用することもできる。この鍵カプセル化メカニズムを、本発明の実施の形態におけるＮＴＲＵ暗号に適用したＮＴＲＵ暗号を「本発明の実施の形態におけるＲｏｕｎｄｅｄ  ＮＴＲＵ暗号＋Ｄｅｎｔ４」と表す。
【００６０】
（鍵生成）
ｆ＝ｐ・ｆ´←ＲＤｆ、ｇ＝１＋ｐ・ｇ´←ＲＤｇとして、ｈ：＝ｇ・Ｆｑ  （ｍｏｄ  ｑ）を計算する。ここで、Ｄｆ及びＤｇは環Ｒの部分集合、ｇ´は環Ｒの要素、Ｆｑは法ｑでのｆの逆元である。
【００６１】
そして、公開鍵をｈ、秘密鍵をｈ及びｆとする。このように、上記（４）のＲｏｕｎｄｅｄ  ＮＴＲＵ暗号＋Ｄｅｎｔ４と比べて、秘密鍵としてＧｐが不要であるため、秘密鍵のサイズを小さくすることができる。言い換えれば、秘密鍵の保存に必要な記憶領域を小さくすることができる。なお、ｆに加えて、ｇも秘密鍵としても良い。
【００６２】
（暗号化（鍵カプセル化））
ｒ←ＲＤｒとして、ｃ１：＝ｒｏｕｎｄｐ（ｈ・ｒ）を計算する。また、（ｃ２，Ｋ）：＝Ｈ（ｒ）を計算する。ここで、Ｄｒは環Ｒの部分集合、Ｈ（・）はハッシュ関数である。
【００６３】
そして、ｃ：＝（ｃ１，ｃ２）を暗号化メッセージ、Ｋを共有鍵とする。
【００６４】
ここで、上述したように、ｒｏｕｎｄｐ（ｈ・ｒ）によりｅが一意に決定される。すなわち、ｒｏｕｎｄｐ（ｈ・ｒ）＝ｈ・ｒ＋ｅである。
【００６５】
（復号（鍵カプセル化解除））
暗号化メッセージｃの受信側は、以下のＳｔｅｐ６−１〜Ｓｔｅｐ６−４により鍵カプセル化解除を行って、共有鍵を生成する。
【００６６】
Ｓｔｅｐ６−１）ａ：＝ｆ・ｃ  （ｍｏｄ  ｑ）を計算する。なお、ｆ・ｃ＝（ｐ・ｆ´）・（ｈ・ｒ＋ｅ）＝（１＋ｐ・ｇ´）・ｒ＋ｐ・ｆ´・ｅ＝ｒ＋ｐ・（ｇ´・ｒ＋ｆ´・ｅ）  （ｍｏｄ  ｑ）である。
【００６７】
Ｓｔｅｐ６−２）ｒ´：＝ａ  （ｍｏｄ  ｐ）を計算する。
【００６８】
Ｓｔｅｐ６−３）ｒ´を用いて鍵カプセル化を行って、ｃ１´、ｃ２´及びＫ´を得る。すなわち、ｃ１´：＝ｒｏｕｎｄｐ（ｈ・ｒ´）と、（ｃ２´，Ｋ´）：＝Ｈ（ｒ´）とを計算して、ｃ１´、ｃ２´及びＫ´を得る。
【００６９】
Ｓｔｅｐ６−４）ｒ´∈Ｄｒ、かつ、（ｃ１，ｃ２）＝（ｃ１´，ｃ２´）である場合、Ｋ´を共有鍵とする。これより、暗号化メッセージｃの受信側と送信側との間で共有鍵Ｋ＝Ｋ´が共有される。なお、ｒ´∈Ｄｒ及び（ｃ１，ｃ２）＝（ｃ１´，ｃ２´）の少なくとも一方を満たさない場合、復号失敗（鍵カプセル化解除失敗）とする。
【００７０】
このように、上記（４）のＲｏｕｎｄｅｄ  ＮＴＲＵ暗号＋Ｄｅｎｔ４と比べて、上記のＳｔｅｐ４−３が不要であるため、復号処理（鍵カプセル化解除処理）をより高速に行うことができるようになる。
【００７１】
＜全体構成＞
次に、本発明の実施の形態における暗号化システム１の全体構成について、図１を参照しながら説明する。図１は、本発明の実施の形態における暗号化システム１の全体構成の一例を示す図である。
【００７２】
図１に示すように、本発明の実施の形態における暗号化システム１には、１台以上の暗号化装置１０と、１台以上の復号装置２０とが含まれる。また、暗号化装置１０と復号装置２０とは、例えばインターネット等の広域的なネットワークＮを介して通信可能に接続されている。
【００７３】
暗号化装置１０は、公開鍵の生成と、暗号化メッセージの復号とを行う各種装置又は機器である。一方で、復号装置２０は、メッセージの暗号化を行う各種装置又は機器である。
【００７４】
暗号化装置１０及び復号装置２０としては、他の装置又は機器と通信可能な任意の装置又は機器が用いられる。例えば、ＰＣ（パーソナルコンピュータ）、スマートフォン、タブレット端末、ウェアラブルデバイス、ゲーム機器、家電、カーナビゲーション端末、センサデバイス等のＩｏＴ機器等が用いられる。
【００７５】
＜ハードウェア構成＞
次に、本発明の実施の形態における暗号化装置１０及び復号装置２０のハードウェア構成について、図２を参照しながら説明する。図２は、本発明の実施の形態における暗号化装置１０及び復号装置２０のハードウェア構成の一例を示す図である。なお、暗号化装置１０及び復号装置２０は、略同様のハードウェア構成で実現可能であるため、以降では、主に、暗号化装置１０のハードウェア構成について説明する。
【００７６】
図２に示すように、本発明の実施の形態における暗号化装置１０は、入力装置１１と、表示装置１２と、外部Ｉ／Ｆ１３と、ＲＡＭ（Random Access Memory）１４と、ＲＯＭ（Read Only Memory）１５と、ＣＰＵ（Central Processing Unit）１６と、通信Ｉ／Ｆ１７と、補助記憶装置１８とを有する。これらの各ハードウェアは、それぞれがバスＢを介して通信可能に接続されている。
【００７７】
入力装置１１は、例えばキーボードやマウス、タッチパネル等である。表示装置１２は、例えばディスプレイ等である。なお、暗号化装置１０及び復号装置２０は、入力装置１１及び表示装置１２のうちの少なくとも一方を有していなくても良い。
【００７８】
外部Ｉ／Ｆ１３は、外部装置とのインタフェースである。外部装置には、記録媒体１３ａ等がある。記録媒体１３ａとしては、例えば、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等が挙げられる。記録媒体１３ａには、暗号化装置１０の各機能を実現する１以上のプログラムや復号装置２０の各機能を実現する１以上のプログラム等が記録されていても良い。
【００７９】
ＲＡＭ１４は、プログラムやデータを一時保持する揮発性の半導体メモリである。ＲＯＭ１５は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。
【００８０】
ＣＰＵ１６は、ＲＯＭ１５や補助記憶装置１８等からプログラムやデータをＲＡＭ１４上に読み出して処理を実行する演算装置である。
【００８１】
通信Ｉ／Ｆ１７は、ネットワークＮに接続するためのインタフェースである。なお、暗号化装置１０の各機能を実現する１以上のプログラムや復号装置２０の各機能を実現する１以上のプログラム等は、通信Ｉ／Ｆ１７を介して、所定のサーバ装置等から取得（ダウンロード）されても良い。
【００８２】
補助記憶装置１８は、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等の不揮発性の記憶装置である。補助記憶装置１８には、暗号化装置１０の各機能を実現する１以上のプログラム等が記憶されている。なお、復号装置２０の補助記憶装置１８には、当該復号装置２０の各機能を実現する１以上のプログラム等が記憶されている。
【００８３】
本発明の実施の形態における暗号化装置１０及び復号装置２０は、図２に示すハードウェア構成を有することにより、後述する各種処理を実現することができる。なお、図２では、本発明の実施の形態における暗号化装置１０及び復号装置２０が１台の情報処理装置（コンピュータ）で実現されている場合を示したが、これに限られない。本発明の実施の形態における暗号化装置１０及び復号装置２０は、複数台の情報処理装置（コンピュータ）で実現されていても良い。
【００８４】
＜機能構成＞
次に、本発明の実施の形態における暗号化システム１の機能構成について、図３を参照しながら説明する。図３は、本発明の実施の形態における暗号化システム１の機能構成の一例を示す図である。
【００８５】
図３に示すように、本発明の実施の形態における暗号化装置１０は、通信部１０１と、暗号化部１０２とを有する。これら各機能部は、暗号化装置１０にインストールされた１以上のプログラムがＣＰＵ１６に実行させる処理により実現される。
【００８６】
通信部１０１は、復号装置２０との間で各種データの送受信を行う。例えば、通信部１０１は、暗号化メッセージを復号装置２０に送信する。
【００８７】
暗号化部１０２は、復号装置２０によって公開された公開鍵を用いて、本発明の実施の形態におけるＮＴＲＵ暗号により暗号化メッセージを生成する。
【００８８】
図３に示すように、本発明の実施の形態における復号装置２０は、通信部２０１と、鍵生成部２０２と、復号部２０３とを有する。これら各機能部は、復号装置２０にインストールされた１以上のプログラムがＣＰＵ１６に実行させる処理により実現される。
【００８９】
通信部２０１は、暗号化装置１０との間で各種データの送受信を行う。例えば、通信部２０１は、暗号化装置１０からの暗号化メッセージを受信する。
【００９０】
鍵生成部２０２は、本発明の実施の形態におけるＮＴＲＵ暗号により公開鍵及び秘密鍵を生成する。
【００９１】
復号部２０３は、鍵生成部２０２により生成した秘密鍵を用いて、本発明の実施の形態におけるＮＴＲＵ暗号により暗号化メッセージを復号する。
【００９２】
＜暗号化及び復号処理（実施例１）＞
以降では、実施例１として、本発明の実施の形態におけるＮＴＲＵ暗号により暗号化及び復号を行う処理について、図４を参照しながら説明する。図４は、本発明の実施の形態における暗号化及び復号処理の一例を示すシーケンス図（実施例１）である。
【００９３】
まず、復号装置２０の鍵生成部２０２は、公開鍵ｈと秘密鍵ｆとを生成する（ステップＳ１０１）。すなわち、鍵生成部２０２は、ｆ＝ｐ・ｆ´←ＲＤｆ、ｇ＝１＋ｐ・ｇ´←ＲＤｇとして、ｈ：＝ｇ・Ｆｑ  （ｍｏｄ  ｑ）を計算し、公開鍵をｈ、秘密鍵をｆとする。ここで、Ｄｆ及びＤｇは環Ｒの部分集合、ｇ´は環Ｒの要素、Ｆｑは法ｑでのｆの逆元である。なお、公開鍵ｈは、暗号化装置１０に対して公開される。
【００９４】
次に、暗号化装置１０の暗号化部１０２は、公開鍵ｈを用いて、暗号化対象のメッセージｒ∈Ｄｒを暗号化して、暗号化メッセージｃを生成する（ステップＳ１０２）。すなわち、暗号化部１０２は、ｃ：＝ｒｏｕｎｄｐ（ｈ・ｒ）を計算することで、暗号化メッセージｃを生成する。ここで、Ｄｒは、環Ｒの部分集合である。
【００９５】
次に、暗号化装置１０の通信部１０１は、暗号化メッセージｃを復号装置２０に送信する（ステップＳ１０３）。
【００９６】
復号装置２０の復号部２０３は、通信部２０１により暗号化メッセージｃを受信すると、秘密鍵ｆを用いて、上記のＳｔｅｐ５−１〜Ｓｔｅｐ５−３により暗号化メッセージｃをメッセージｒに復号する（ステップＳ１０４）。
【００９７】
＜暗号化及び復号処理（実施例２）＞
以降では、実施例２として、本発明の実施の形態におけるＮＴＲＵ暗号＋Ｄｅｎｔ４により暗号化装置１０と復号装置２０との間で共有鍵を共有した上で、この共有鍵により暗号化及び復号を行う処理について、図５を参照しながら説明する。図５は、本発明の実施の形態における暗号化及び復号処理の一例を示すシーケンス図（実施例２）である。
【００９８】
まず、復号装置２０の鍵生成部２０２は、公開鍵ｈと秘密鍵ｆとを生成する（ステップＳ２０１）。すなわち、鍵生成部２０２は、ｆ＝ｐ・ｆ´←ＲＤｆ、ｇ＝１＋ｐ・ｇ´←ＲＤｇとして、ｈ：＝ｇ・Ｆｑ  （ｍｏｄ  ｑ）を計算し、公開鍵をｈ、秘密鍵をｆとする。ここで、Ｄｆ及びＤｇは環Ｒの部分集合、ｇ´は環Ｒの要素、Ｆｑは法ｑでのｆの逆元である。なお、公開鍵ｈは、暗号化装置１０に対して公開される。
【００９９】
次に、暗号化装置１０の暗号化部１０２は、公開鍵ｈを用いて、鍵カプセル化により共有鍵Ｋ及び暗号化メッセージｃを生成する（ステップＳ２０２）。すなわち、暗号化部１０２は、ｒ←ＲＤｒとして、ｃ１：＝ｒｏｕｎｄｐ（ｈ・ｒ）と、（ｃ２，Ｋ）：＝Ｈ（ｒ）とを計算して、暗号化メッセージｃ：＝（ｃ１，ｃ２）及び共有鍵Ｋを生成する。ここで、Ｄｒは環Ｒの部分集合、Ｈ（・）はハッシュ関数である。
【０１００】
次に、暗号化装置１０の通信部１０１は、暗号化メッセージｃを復号装置２０に送信する（ステップＳ２０３）。
【０１０１】
復号装置２０の復号部２０３は、通信部２０１により暗号化メッセージｃを受信すると、秘密鍵ｆを用いて、上記のＳｔｅｐ６−１〜Ｓｔｅｐ６−４により暗号化メッセージｃから共有鍵Ｋ＝Ｋ´を生成する（ステップＳ２０４）。そして、復号部２０３は、共有鍵Ｋが得られたことを暗号化装置１０に通知する。
【０１０２】
次に、暗号化装置１０の暗号化部１０２は、共有鍵Ｋを用いて、任意の暗号化アルゴリズムにより暗号化対象のメッセージを暗号化して、暗号化メッセージを生成する（ステップＳ２０５）。
【０１０３】
次に、暗号化装置１０の通信部１０１は、暗号化メッセージを復号装置２０に送信する（ステップＳ２０６）。
【０１０４】
復号装置２０の復号部２０３は、通信部２０１により暗号化メッセージを受信すると、共有鍵Ｋを用いて、上記の暗号化アルゴリズムに対応する復号アルゴリズムにより暗号化メッセージを復号する（ステップＳ２０７）。
【０１０５】
＜本発明の効果＞
ここで、一例として、以下の参考文献２に記載されているパラメータセットｋｅｍ／ｎｔｒｕｌｐｒ４５９１７６１を用いた場合における本発明の効果について説明する。
【０１０６】
［参考文献２］
Daniel J. Bernstein, Chitchanok Chuengsatiansup, Tanja Lange, Christine van Vredendaal: NTRU Prime NIST Submitted.
上記のパラメータセットｋｅｍ／ｎｔｒｕｌｐｒ４５９１７６１では、ｐ＝３、ｎ＝７６１、ｑ＝４５９１であり、ｆ（ｘ）＝ｘｎ−ｘ−１である。この場合、上記の参考文献２に記載されているように、従来のＲｏｕｎｄｅｄ  ＮＴＲＵ暗号では、公開鍵は１２１８ｂｙｔｅｓ、暗号化メッセージは１０１５ｂｙｔｅｓ、秘密鍵は１６００ｂｙｔｅｓ＝１２１８＋１９１＋１９１ｂｙｔｅｓである。
【０１０７】
これに対して、本発明の実施の形態におけるＮＴＲＵ暗号の手法を用いることで、秘密鍵のサイズを１４０９ｂｙｔｅｓ＝１２１８＋１９１ｂｙｔｅｓに削減することができる。
【０１０８】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【０１０９】
１        暗号化システム
１０      暗号化装置
２０      復号装置
１０１    通信部
１０２    暗号化部
２０１    通信部
２０２    鍵生成部
２０３    復号部
【図１】
2019200382.tif 000003
【図２】
2019200382.tif 000004
【図３】
2019200382.tif 000005
【図４】
2019200382.tif 000006
【図５】
2019200382.tif 000007