発明の詳細な説明【技術分野】 【０００１】 本発明は、Ｌｅａｒｎｉｎｇ ｗｉｔｈ Ｅｒｒｏｒｓ（ＬＷＥ）問題に基づくしきい値公開鍵暗号の構成方法に関する。 続きを表示（約 2,900 文字）【背景技術】 【０００２】 暗号プロトコルのシミュレーションベース安全性とは、実現したい理想的な信頼できる機能（理想機能）を設計し、現実の暗号プロトコルがその理想機能の入出力と計算量的に識別不可能であることを示す、現代的な安全性証明技法・モデルであり、汎用的結合可能性を示すのに有用な手法である。特に、秘密計算（ｍｕｌｔｉ－ｐａｒｔｙ ｃｏｍｐｕｔａｔｉｏｎ： ＭＰＣ）の安全性証明は、シミュレーションベースで構成されることが多いため、暗号プロトコルをＭＰＣの構成要素として用いるためにもシミュレーションベース安全性は重要である。 【０００３】 対照的に、古典的なゲームベース安全性は、従来の安全性証明の構成のしやすさを優先した安全性設計となっている。例えば、公開鍵暗号のゲームベース安全性では、０の暗号文と１の暗号文とが識別不可能であることを示すが、シミュレーションベース安全性では、攻撃者に暗号文を与えている場合（＝現実）と攻撃者に暗号文を与えていない場合（＝理想機能）とで、攻撃者の出力に差異が生まれないことを示す。 【０００４】 また、（ｔ，Ｎ）－しきい値公開鍵暗号（Ｔｈｒｅｓｈｏｌｄ ＰＫＥ： ＴｈＰＫＥ）とは、互いに異なる秘密鍵シェアを持つ全参加者Ｎ人のうち、ｔ人が部分復号を行い、その部分復号文を持ち寄ることで復号が可能となる公開鍵暗号方式である。非特許文献１において、多項式サイズの法ｑ ＬＷＥ問題（後述の定義Ｄ．２）に基づくシミュレーション安全なしきい値公開鍵暗号が提案された。 【先行技術文献】 【非特許文献】 【０００５】 D. Micciancio, A. Suhl. "Simulation-Secure Threshold PKE from LWE with Polynomial Modulus". ePrint 2023/1728. 2023. V. Lyubashevsky, C. Peikert, O. Regev. "On Ideal Lattices and Learning with Errors over Rings". EUROCRYPT 2010. 2010, pp. 1-23. Z. Brakerski, C. Gentry, V. Vaikuntanathan. "(Leveled) Fully Homomorphic Encryption without Bootstrapping". ITCS 2012. 2012, pp. 309-325. D. Boneh, R. Gennaro, S. Goldfeder, A. Jain, S. Kim, P. M. R. Rasmussen, A. Sahai. "Threshold Cryptosystems from Threshold Fully Homomorphic Encryption". CRYPTO 2018. 2018, pp. 565-596. Z. Brakerski, N. Dottling. "Hardness of LWE on General Entropic Distributions". EUROCRYPT 2020. 2020, pp. 551-575. D. Micciancio, P. Mol. "Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions". CRYPTO 2011. 2011, pp. 465-484. O. Regev. "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography". J. ACM 56.6 (Sept. 2009). Preliminary version is in STOC ’05. 【発明の概要】 【発明が解決しようとする課題】 【０００６】 従来（非特許文献１）のシミュレーション安全なしきい値公開鍵暗号は、より詳しくは、ＬＷＥではなく、エラーｅのノルム∥ｅ∥が攻撃者に与えられたとしても計算困難であるという、ＬＷＥ仮定の変形である「Ｋｎｏｗｎ－Ｎｏｒｍ ＬＷＥ」仮定に基づいて構成された。 したがって、従来の方式は、この仮定に起因する次の２つの課題を持つ。 【０００７】 Ｎｏｎ－ｔｉｇｈｔな安全性： Ｋｎｏｗｎ－Ｎｏｒｍ ＬＷＥは、ＬＷＥからの帰着を示すことによって計算困難性が示されているが、その帰着の損失により、例えば１０数ｂｉｔ程度のビットセキュリティの損失が生じることが報告されている。 【０００８】 Ｒｉｎｇ－ＬＷＥとの適合性： 近年の効率的な格子暗号は、ＬＷＥ問題の拡張であるＲｉｎｇ－ＬＷＥ（非特許文献２）に基づいて構成されており、完全準同型暗号（例えば、非特許文献３，４）も同様である。 非特許文献１の手法で、Ｒｉｎｇ－ＬＷＥに基づくＴｈＰＫＥを構成しようとしたとき、エラーｅのノルム∥ｅ∥を既知とする「Ｋｎｏｗｎ－Ｎｏｒｍ Ｒｉｎｇ－ＬＷＥ」仮定が必要となるが、ＬＷＥとは異なり、Ｒｉｎｇ－ＬＷＥからＫｎｏｗｎ－Ｎｏｒｍ Ｒｉｎｇ－ＬＷＥへの帰着は知られていないため、この手法ではＲｉｎｇ－ＬＷＥを安全性仮定とすることができない。 【０００９】 本発明は、Ｋｎｏｗｎ－Ｎｏｒｍ ＬＷＥを必要としない、多項式サイズの法ｑ ＬＷＥ問題に基づくシミュレーション安全なしきい値公開鍵暗号を構成した暗号システムを提供することを目的とする。 【課題を解決するための手段】 【００１０】 本発明に係る暗号システムは、ＬＷＥに基づくしきい値公開鍵暗号における公開鍵に対する第１のエラーを生成するための鍵分布、及び暗号化の際に用いる乱数分布とともに、部分復号文をマスクするためのエラー分布を、正確性を満たす条件で定義する定義部と、前記しきい値公開鍵暗号の秘密鍵及び当該秘密鍵に対応する前記公開鍵とともに、前記エラー分布に従って第２のエラーを生成する鍵生成部と、前記秘密鍵及び前記第２のエラーを秘密分散したシェアを各パーティに配布する設定部と、前記公開鍵、及び前記乱数分布に従う第１の乱数を用いてメッセージを暗号化し、さらに前記乱数分布に従う第２の乱数を含んだ暗号文を生成する暗号化部と、前記各パーティにおいて、秘密分散された前記秘密鍵のシェアを用いて前記暗号文を部分復号し、前記第２の乱数に対して秘密分散された前記第２のエラーのシェアを乗じた値を加算した部分復号文を算出する部分復号部と、有効シェア集合の前記部分復号文の総和に基づいて、前記メッセージを復号する全体復号部と、を備える。 （【００１１】以降は省略されています）
特許ウォッチbot のツイートを見る
この特許をJ-PlatPatで参照する
特許ウォッチ
