TOP特許意匠商標
特許ウォッチ Twitter
10個以上の画像は省略されています。
公開番号2025101353
公報種別公開特許公報(A)
公開日2025-07-07
出願番号2023218151
出願日2023-12-25
発明の名称暗号システム、暗号化装置、復号装置及びプログラム
出願人KDDI株式会社
代理人個人,個人
主分類G09C 1/00 20060101AFI20250630BHJP(教育;暗号方法;表示;広告;シール)
要約【課題】多項式サイズの法q LWE問題に基づく効率的でシミュレーション安全なしきい値公開鍵暗号を構成した暗号システムを提供すること。
【解決手段】暗号システム100は、鍵分布、及び乱数分布とともに、部分復号文をマスクするためのエラー分布を、正確性を満たす条件で定義する定義部11と、秘密鍵及び公開鍵とともに、エラー分布に従ってエラーを生成する鍵生成部12と、秘密鍵及びエラーを秘密分散したシェアを各パーティに配布する設定部13と、公開鍵及び第1の乱数を用いてメッセージを暗号化し、さらに第2の乱数を含んだ暗号文を生成する暗号化部21と、各パーティにおいて秘密鍵のシェアを用いて暗号文を部分復号し、第2の乱数に対してエラーのシェアを乗じた値を加算した部分復号文を算出する部分復号部31と、有効シェア集合の部分復号文の総和に基づいて、メッセージを復号する全体復号部32と、を備える。
【選択図】図1
特許請求の範囲【請求項1】
Learning with Errors(LWE)に基づくしきい値公開鍵暗号における公開鍵に対する第1のエラーを生成するための鍵分布、及び暗号化の際に用いる乱数分布とともに、部分復号文をマスクするためのエラー分布を、正確性を満たす条件で定義する定義部と、
前記しきい値公開鍵暗号の秘密鍵及び当該秘密鍵に対応する前記公開鍵とともに、前記エラー分布に従って第2のエラーを生成する鍵生成部と、
前記秘密鍵及び前記第2のエラーを秘密分散したシェアを各パーティに配布する設定部と、
前記公開鍵、及び前記乱数分布に従う第1の乱数を用いてメッセージを暗号化し、さらに前記乱数分布に従う第2の乱数を含んだ暗号文を生成する暗号化部と、
前記各パーティにおいて、秘密分散された前記秘密鍵のシェアを用いて前記暗号文を部分復号し、前記第2の乱数に対して秘密分散された前記第2のエラーのシェアを乗じた値を加算した部分復号文を算出する部分復号部と、
有効シェア集合の前記部分復号文の総和に基づいて、前記メッセージを復号する全体復号部と、を備える暗号システム。
続きを表示(約 1,000 文字)【請求項2】
前記しきい値公開鍵暗号は、完全準同型暗号である請求項1に記載の暗号システム。
【請求項3】
前記LWEは、Ring-LWEである請求項1に記載の暗号システム。
【請求項4】
Learning with Errors(LWE)に基づくしきい値公開鍵暗号における公開鍵に対する第1のエラーを生成するための鍵分布、及び暗号化の際に用いる乱数分布とともに、部分復号文をマスクするためのエラー分布が正確性を満たす条件で提供され、
前記しきい値公開鍵暗号の秘密鍵に対応して生成された前記公開鍵、及び前記乱数分布に従う第1の乱数を用いてメッセージを暗号化し、さらに前記乱数分布に従う第2の乱数を含んだ暗号文を生成する暗号化部を備え、
前記秘密鍵、及び前記エラー分布に従って生成された第2のエラーを秘密分散したシェアが配布された各パーティにおいて、前記暗号文を前記秘密鍵のシェアを用いて部分復号した際に、前記第2の乱数に対して前記第2のエラーのシェアを乗じた値を加算した部分復号文を算出させる暗号化装置。
【請求項5】
Learning with Errors(LWE)に基づくしきい値公開鍵暗号における公開鍵に対する第1のエラーを生成するための鍵分布、及び暗号化の際に用いる乱数分布とともに、部分復号文をマスクするためのエラー分布が正確性を満たす条件で提供され、
前記しきい値公開鍵暗号の秘密鍵、及び前記エラー分布に従って生成された第2のエラーを秘密分散したシェアが配布され、
前記秘密鍵に対応して生成された前記公開鍵、及び前記乱数分布に従う第1の乱数を用いてメッセージが暗号化され、さらに前記乱数分布に従う第2の乱数を含んだ暗号文が提供されると、前記秘密鍵のシェアを用いて前記暗号文を部分復号し、前記第2の乱数に対して秘密分散された前記第2のエラーのシェアを乗じた値を加算した部分復号文を算出する部分復号部と、
有効シェア集合の前記部分復号文の総和に基づいて、前記メッセージを復号する全体復号部と、を備える復号装置。
【請求項6】
請求項4に記載の暗号化装置としてコンピュータを機能させるための暗号化プログラム。
【請求項7】
請求項5に記載の復号装置としてコンピュータを機能させるための復号プログラム。

発明の詳細な説明【技術分野】
【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で参照する

関連特許

KDDI株式会社
支柱及び設置方法
2日前
KDDI株式会社
アンテナ指向装置
1か月前
KDDI株式会社
アンテナ指向装置
1か月前
KDDI株式会社
光増幅器及び光通信システム
1か月前
KDDI株式会社
情報処理装置及び情報処理方法
28日前
KDDI株式会社
光ニューラルネットワーク装置
2日前
KDDI株式会社
情報処理装置及び情報処理方法
1か月前
KDDI株式会社
情報処理装置及び情報処理方法
1日前
KDDI株式会社
画像フィルタ装置及びプログラム
13日前
KDDI株式会社
無線アクセスネットワークの制御装置
1か月前
KDDI株式会社
無線アクセスネットワークの制御装置
1か月前
KDDI株式会社
通信装置、無線デバイス及びプログラム
13日前
KDDI株式会社
演算装置、演算方法及び演算プログラム
1か月前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
27日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
27日前
KDDI株式会社
情報処理方法、プログラム及び情報処理装置
1か月前
KDDI株式会社
画像復号装置、画像復号方法及びプログラム
29日前
KDDI株式会社
情報処理方法、プログラム及び情報処理装置
1か月前
KDDI株式会社
情報処理方法、プログラム及び情報処理装置
1か月前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
13日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
13日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
1日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
7日前
KDDI株式会社
映像復号装置、映像復号方法及びプログラム
6日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
20日前
KDDI株式会社
情報処理装置、情報処理方法及び情報処理システム
1か月前
KDDI株式会社
情報処理装置、情報処理方法及び情報処理システム
16日前
KDDI株式会社
情報処理システム、情報処理方法及び情報処理装置。
20日前
KDDI株式会社
暗号システム、暗号化装置、復号装置及びプログラム
2日前
KDDI株式会社
報酬設定装置、報酬設定方法、及び報酬設定プログラム
6日前
KDDI株式会社
対価算出装置、対価算出方法及びコンピュータプログラム
今日
KDDI株式会社
飛行体及び接触方法
1か月前
KDDI株式会社
効率的なデータの転送のための制御装置、制御方法、及びプログラム
21日前
KDDI株式会社
効率的なセル・サーチを行う基地局、無線端末、通信方法及びプログラム
13日前
KDDI株式会社
効率的なセル・サーチを行う基地局、無線端末、通信方法及びプログラム
13日前
KDDI株式会社
メッセージ配信装置、メッセージ配信方法、及びメッセージ配信プログラム
7日前
続きを見る