発明の詳細な説明【技術分野】 【０００１】 本発明は、ＬＷＥ（Ｌｅａｒｎｉｎｇ ｗｉｔｈ Ｅｒｒｏｒｓ）問題に基づく高機能暗号（しきい値暗号等）における安全性設計のための技術に関する。 続きを表示（約 3,000 文字）【背景技術】 【０００２】 非特許文献１において、格子理論に関する計算困難問題としてＬＷＥ問題が提案され、その後、このＬＷＥ問題に基づいた暗号方式が多数提案されている。 また、非特許文献２において、ＬＷＥ問題の変種であるＲｅｕｓｅｄ－Ａ－ＬＷＥ問題が提案され、エラー分布χ 1 ，χ 2 が連続ガウシアン分布の場合に、ＬＷＥ≦Ｒｅｕｓｅｄ－Ａ－ＬＷＥ（ＬＷＥ問題からＲｅｕｓｅｄ－Ａ－ＬＷＥ問題への帰着）、つまり、Ｒｅｕｓｅｄ－Ａ－ＬＷＥ問題はＬＷＥ問題以上に計算困難であることが示された。そして、この帰着に基づいて安全性設計がなされたしきい値公開鍵暗号が提案されている。 【先行技術文献】 【非特許文献】 【０００３】 O. Regev. "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography". J. ACM 56.6 (2009). Preliminary version appeared in STOC '05. D. Micciancio and A. Suhl. "Simulation-Secure Threshold PKE from LWE with Polynomial Modulus". ePrint 2023/1728. 2023. D. Micciancio and C. Peikert. "Hardness of SIS and LWE with Small Parameters". CRYPTO 2013. 2013, pp. 21-39. L. Ducas, S. Galbraith, T. Prest, and Y. Yu. "Integral Matrix Gram Root and Lattice Gaussian Sampling without Floats". EUROCRYPT 2020. 2020, pp. 608-637. M. R. Albrecht, B. R. Curtis, A. Deo, A. Davidson, R. Player, E. W. Postlethwaite, F. Virdia, and T. Wunderer. "Estimate All the {LWE, NTRU} Schemes!" SCN 2018. 2018, pp. 351-367. V. Lyubashevsky, C. Peikert, and O. Regev. "On Ideal Lattices and Learning with Errors over Rings". EUROCRYPT 2010. 2010, pp. 1-23. 【発明の概要】 【発明が解決しようとする課題】 【０００４】 しかしながら、非特許文献２で示された帰着ＬＷＥ≦Ｒｅｕｓｅｄ－Ａ－ＬＷＥは、エラー分布χ 1 ，χ 2 が連続ガウシアン分布の場合に限られていた。一方、計算機上の実装においては、エラー分布は離散的な値である必要がある。また、連続ガウシアン分布における実数を浮動小数点型で代用した場合には、その丸め誤差の影響を別途議論する必要があった。 【０００５】 本発明は、離散ガウシアン分布をエラー分布とするＲｅｕｓｅｄ－Ａ－ＬＷＥ問題に基づく暗号設計において、安全性が保証されたセキュリティパラメータを導出できる安全性設計装置、安全性設計方法及び安全性設計プログラムを提供することを目的とする。 【課題を解決するための手段】 【０００６】 本発明に係る安全性設計装置は、離散ガウシアン分布をエラー分布としたＲｅｕｓｅｄ－Ａ－ＬＷＥ問題Ｒｅｕｓｅｄ－Ａ－ＬＷＥ S （ｎ，ｍ，ｑ，Ｄ Z,s1 ，Ｄ Z,s2 ）のパラメータｎ，ｍ，ｑ，ｓ 1 ，ｓ 2 （ただし、定数Ｃ∈Ｎ（自然数）に対してｓ 2 ＝Ｃｓ 1 ）の入力を受け付ける入力部と、パラメータｓ 1 及び定数Ｃから、離散ガウシアン分布をエラー分布としたＬＷＥ問題ｄ－ＬＷＥ S （ｎ，ｍ，ｑ，Ｄ Z,sb ）のパラメータｓ b を、 TIFF 2025176467000002.tif 16 134 と算出する算出部と、前記ＬＷＥ問題ｄ－ＬＷＥ S （ｎ，ｍ，ｑ，Ｄ Z,sb ）のセキュリティパラメータλを、所定の安全性を担保する計算式により取得する取得部と、前記取得部により取得されたセキュリティパラメータλを、前記Ｒｅｕｓｅｄ－Ａ－ＬＷＥ問題のセキュリティパラメータとして出力する出力部と、を備える。 【０００７】 前記Ｒｅｕｓｅｄ－Ａ－ＬＷＥ問題は、Ｒｅｕｓｅｄ－Ａ－Ｒｉｎｇ－ＬＷＥ問題であり、前記ＬＷＥ問題は、Ｒｉｎｇ－ＬＷＥ問題であってもよい。 【０００８】 本発明に係る安全性設計方法は、コンピュータが、入力部により、離散ガウシアン分布をエラー分布としたＲｅｕｓｅｄ－Ａ－ＬＷＥ問題Ｒｅｕｓｅｄ－Ａ－ＬＷＥ S （ｎ，ｍ，ｑ，Ｄ Z,s1 ，Ｄ Z,s2 ）のパラメータｎ，ｍ，ｑ，ｓ 1 ，ｓ 2 （ただし、定数Ｃ∈Ｎ（自然数）に対してｓ 2 ＝Ｃｓ 1 ）の入力を受け付け、算出部により、パラメータｓ 1 及び定数Ｃから、離散ガウシアン分布をエラー分布としたＬＷＥ問題ｄ－ＬＷＥ S （ｎ，ｍ，ｑ，Ｄ Z,sb ）のパラメータｓ b を、 TIFF 2025176467000003.tif 16 134 と算出し、取得部により、前記ＬＷＥ問題ｄ－ＬＷＥ S （ｎ，ｍ，ｑ，Ｄ Z,sb ）のセキュリティパラメータλを、所定の安全性を担保する計算式により取得し、出力部により、前記取得部により取得されたセキュリティパラメータλを、前記Ｒｅｕｓｅｄ－Ａ－ＬＷＥ問題のセキュリティパラメータとして出力する。 【０００９】 本発明に係る安全性設計プログラムは、前記安全性設計装置としてコンピュータを機能させるためのものである。 【発明の効果】 【００１０】 本発明によれば、離散ガウシアン分布をエラー分布とするＲｅｕｓｅｄ－Ａ－ＬＷＥ問題に基づく暗号設計において、安全性が保証されたセキュリティパラメータを導出できる。 【図面の簡単な説明】 （【００１１】以降は省略されています） この特許をJ-PlatPat（特許庁公式サイト）で参照する
特許ウォッチ
