特許ウォッチ

公開番号2024146417
公報種別公開特許公報(A)
公開日2024-10-15
出願番号2023059297
出願日2023-03-31
発明の名称安全性評価装置、安全性評価方法及び安全性評価プログラム
出願人KDDI株式会社
代理人個人,個人
主分類G09C 1/00 20060101AFI20241004BHJP(教育;暗号方法;表示;広告;シール)
要約【課題】離散ガウスLWE問題を用いた暗号方式に対して、errorの分散が同一の丸めガウスLWE問題に基づき、正当性が保証された安全性を評価できる安全性評価装置、安全性評価方法及び安全性評価プログラムを提供すること。
【解決手段】安全性評価装置1は、離散ガウスLWE問題LWE(m,n,q,D_Zq,r)のパラメータm,n,q,rの入力を受け付ける入力部11と、パラメータが共通する丸めガウスLWE問題のセキュリティビットを取得する取得部12と、取得されたセキュリティビットから(πm/4r²)を減じた値を、離散ガウスLWE問題のセキュリティビットとして算出する算出部13と、算出されたセキュリティビットを出力する出力部14と、を備える。
【選択図】図2
特許請求の範囲【請求項１】
離散ガウスＬＷＥ問題ＬＷＥ（ｍ，ｎ，ｑ，Ｄ
Ｚｑ，ｒ
）のパラメータｍ，ｎ，ｑ，ｒの入力を受け付ける入力部と、
前記パラメータが共通する丸めガウスＬＷＥ問題のセキュリティビットを取得する取得部と、
前記取得部により取得されたセキュリティビットから（πｍ／４ｒ
２
）を減じた値を、前記離散ガウスＬＷＥ問題のセキュリティビットとして算出する算出部と、
前記算出部により算出されたセキュリティビットを出力する出力部と、を備える安全性評価装置。
続きを表示（約 350 文字）【請求項２】
離散ガウスＬＷＥ問題ＬＷＥ（ｍ，ｎ，ｑ，Ｄ
Ｚｑ，ｒ
）のパラメータｍ，ｎ，ｑ，ｒの入力を受け付ける入力ステップと、
前記パラメータが共通する丸めガウスＬＷＥ問題のセキュリティビットを取得する取得ステップと、
前記取得ステップにおいて取得されたセキュリティビットから（πｍ／４ｒ
２
）を減じた値を、前記離散ガウスＬＷＥ問題のセキュリティビットとして算出する算出ステップと、
前記算出ステップにおいて算出されたセキュリティビットを出力する出力ステップと、をコンピュータが実行する安全性評価方法。
【請求項３】
請求項１に記載の安全性評価装置としてコンピュータを機能させるための安全性評価プログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、暗号方式の安全性を評価する装置、方法及びプログラムに関する。
続きを表示（約 2,500 文字）【背景技術】
【０００２】
非特許文献１において、連続ガウスＬＷＥ（ＬｅａｒｎｉｎｇｗｉｔｈＥｒｒｏｒｓ）問題（：＝ｅｒｒｏｒ分布が連続ガウス分布のＬＷＥ問題）の計算困難性が証明されている。また、これにより、丸めガウスＬＷＥ問題（：＝ｅｒｒｏｒ分布が丸めガウス分布のＬＷＥ問題）の困難性も自明に導かれることが示され、この問題に基づいた安全性証明付きの公開鍵暗号方式が提案された。
その後、非特許文献２等において、より高機能な暗号方式（属性ベース暗号）であるが、離散ガウスＬＷＥ問題（：＝ｅｒｒｏｒ分布が離散ガウス分布のＬＷＥ問題）に基づいた暗号方式も提案されている。
【０００３】
非特許文献３において、離散ガウスＬＷＥ問題が丸めガウスＬＷＥ問題以上に難しいこと、すなわち丸めガウスＬＷＥ問題から離散ガウスＬＷＥ問題への帰着（「丸めガウスＬＷＥ問題→離散ガウスＬＷＥ問題」と書く）が示された。離散ガウスＬＷＥ問題の計算困難性も証明されているため、非特許文献２の方式も安全性が証明されている。
【０００４】
また、非特許文献４等では、ＬＷＥ問題の具体的なセキュリティビットλ（解読にかかる計算量２
λ
の指数）を生成する手法が示された。
ただし、この手法は、ＬＷＥ問題の困難性がｅｒｒｏｒの分散によってのみ決まるという仮説に基づいているため、丸めガウスＬＷＥ問題以外に用いた場合、セキュリティビットは安全性証明により正当性が保証されたパラメータ値ではない。
【先行技術文献】
【非特許文献】
【０００５】
Oded Regev. "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography". In: J. ACM 56.6 (Sept. 2009).
Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. "Attribute-Based Encryption for Circuits". In: J. ACM 62.6 (Dec. 2015).
Chris Peikert. "An Efficient and Parallel Gaussian Sampler for Lattices". In: CRYPTO 2010. 2010, pp. 80-97.
Martin R. Albrecht, Benjamin R. Curtis, Amit Deo, Alex Davidson, Rachel Player, Eamonn W. Postlethwaite, Fernando Virdia, and Thomas Wunderer. "Estimate All the {LWE, NTRU} Schemes!" In: SCN 2018. 2018, pp. 351-367.
Thomas Prest. "Sharper Bounds in Lattice-Based Cryptography Using the Renyi Divergence". In: ASIACRYPT 2017. 2017, pp. 347-374.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献３により、丸めガウスＬＷＥ問題から離散ガウスＬＷＥ問題への帰着
TIFF
2024146417000002.tif
11
134
を構成可能であるが、離散ガウスＬＷＥの標準偏差（パラメータ√２ｒ）が丸めガウスＬＷＥの標準偏差（パラメータｒ）より大きくなってしまうという課題がある。
この課題により、離散ガウスＬＷＥ問題に基づく暗号方式は、丸めガウスＬＷＥ問題より大きなノイズを利用する必要があり、つまり法ｑをより大きくとる必要があった。したがって、暗号文及び鍵のサイズが大きくなっていた。
【０００７】
本発明は、離散ガウスＬＷＥ問題を用いた暗号方式に対して、ｅｒｒｏｒの分散が同一の丸めガウスＬＷＥ問題に基づき、正当性が保証された安全性を評価できる安全性評価装置、安全性評価方法及び安全性評価プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明に係る安全性評価装置は、離散ガウスＬＷＥ問題ＬＷＥ（ｍ，ｎ，ｑ，Ｄ
Ｚｑ，ｒ
）のパラメータｍ，ｎ，ｑ，ｒの入力を受け付ける入力部と、前記パラメータが共通する丸めガウスＬＷＥ問題のセキュリティビットを取得する取得部と、前記取得部により取得されたセキュリティビットから（πｍ／４ｒ
２
）を減じた値を、前記離散ガウスＬＷＥ問題のセキュリティビットとして算出する算出部と、前記算出部により算出されたセキュリティビットを出力する出力部と、を備える。
【０００９】
本発明に係る安全性評価方法は、離散ガウスＬＷＥ問題ＬＷＥ（ｍ，ｎ，ｑ，Ｄ
Ｚｑ，ｒ
）のパラメータｍ，ｎ，ｑ，ｒの入力を受け付ける入力ステップと、前記パラメータが共通する丸めガウスＬＷＥ問題のセキュリティビットを取得する取得ステップと、前記取得ステップにおいて取得されたセキュリティビットから（πｍ／４ｒ
２
）を減じた値を、前記離散ガウスＬＷＥ問題のセキュリティビットとして算出する算出ステップと、前記算出ステップにおいて算出されたセキュリティビットを出力する出力ステップと、をコンピュータが実行する。
【００１０】
本発明に係る安全性評価プログラムは、前記安全性評価装置としてコンピュータを機能させるためのものである。
【発明の効果】
（【００１１】以降は省略されています）

関連特許