発明の詳細な説明【技術分野】 【0001】 本発明は、Learning with Errors(LWE)問題に基づくしきい値公開鍵暗号の構成方法に関する。 続きを表示(約 2,900 文字)【背景技術】 【0002】 暗号プロトコルのシミュレーションベース安全性とは、実現したい理想的な信頼できる機能(理想機能)を設計し、現実の暗号プロトコルがその理想機能の入出力と計算量的に識別不可能であることを示す、現代的な安全性証明技法・モデルであり、汎用的結合可能性を示すのに有用な手法である。特に、秘密計算(multi-party computation: MPC)の安全性証明は、シミュレーションベースで構成されることが多いため、暗号プロトコルをMPCの構成要素として用いるためにもシミュレーションベース安全性は重要である。 【0003】 対照的に、古典的なゲームベース安全性は、従来の安全性証明の構成のしやすさを優先した安全性設計となっている。例えば、公開鍵暗号のゲームベース安全性では、0の暗号文と1の暗号文とが識別不可能であることを示すが、シミュレーションベース安全性では、攻撃者に暗号文を与えている場合(=現実)と攻撃者に暗号文を与えていない場合(=理想機能)とで、攻撃者の出力に差異が生まれないことを示す。 【0004】 また、(t,N)-しきい値公開鍵暗号(Threshold PKE: ThPKE)とは、互いに異なる秘密鍵シェアを持つ全参加者N人のうち、t人が部分復号を行い、その部分復号文を持ち寄ることで復号が可能となる公開鍵暗号方式である。非特許文献1において、多項式サイズの法q LWE問題(後述の定義D.2)に基づくシミュレーション安全なしきい値公開鍵暗号が提案された。 【先行技術文献】 【非特許文献】 【0005】 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. 【発明の概要】 【発明が解決しようとする課題】 【0006】 従来(非特許文献1)のシミュレーション安全なしきい値公開鍵暗号は、より詳しくは、LWEではなく、エラーeのノルム∥e∥が攻撃者に与えられたとしても計算困難であるという、LWE仮定の変形である「Known-Norm LWE」仮定に基づいて構成された。 したがって、従来の方式は、この仮定に起因する次の2つの課題を持つ。 【0007】 Non-tightな安全性: Known-Norm LWEは、LWEからの帰着を示すことによって計算困難性が示されているが、その帰着の損失により、例えば10数bit程度のビットセキュリティの損失が生じることが報告されている。 【0008】 Ring-LWEとの適合性: 近年の効率的な格子暗号は、LWE問題の拡張であるRing-LWE(非特許文献2)に基づいて構成されており、完全準同型暗号(例えば、非特許文献3,4)も同様である。 非特許文献1の手法で、Ring-LWEに基づくThPKEを構成しようとしたとき、エラーeのノルム∥e∥を既知とする「Known-Norm Ring-LWE」仮定が必要となるが、LWEとは異なり、Ring-LWEからKnown-Norm Ring-LWEへの帰着は知られていないため、この手法ではRing-LWEを安全性仮定とすることができない。 【0009】 本発明は、Known-Norm LWEを必要としない、多項式サイズの法q LWE問題に基づくシミュレーション安全なしきい値公開鍵暗号を構成した暗号システムを提供することを目的とする。 【課題を解決するための手段】 【0010】 本発明に係る暗号システムは、LWEに基づくしきい値公開鍵暗号における公開鍵に対する第1のエラーを生成するための鍵分布、及び暗号化の際に用いる乱数分布とともに、部分復号文をマスクするためのエラー分布を、正確性を満たす条件で定義する定義部と、前記しきい値公開鍵暗号の秘密鍵及び当該秘密鍵に対応する前記公開鍵とともに、前記エラー分布に従って第2のエラーを生成する鍵生成部と、前記秘密鍵及び前記第2のエラーを秘密分散したシェアを各パーティに配布する設定部と、前記公開鍵、及び前記乱数分布に従う第1の乱数を用いてメッセージを暗号化し、さらに前記乱数分布に従う第2の乱数を含んだ暗号文を生成する暗号化部と、前記各パーティにおいて、秘密分散された前記秘密鍵のシェアを用いて前記暗号文を部分復号し、前記第2の乱数に対して秘密分散された前記第2のエラーのシェアを乗じた値を加算した部分復号文を算出する部分復号部と、有効シェア集合の前記部分復号文の総和に基づいて、前記メッセージを復号する全体復号部と、を備える。 (【0011】以降は省略されています)
特許ウォッチbot のツイートを見る
この特許をJ-PlatPatで参照する