強RSA仮定(きょうRSAかてい)とは、暗号技術において、RSA暗号やRSA類似の暗号方式の安全性研究に使用される仮定の一つである。

flexible RSA問題 編集

次の問題を flexible RSA 問題(フレキシブル アールエスエイもんだい, flexible RSA problem)という:

nRSAモジュラスとし、a とする。 組   で、  となるものを求めよ。

文献によっては flexible RSA 問題の事を強 RSA 問題(きょうアールエスエイもんだい, strong RSA problem)と呼んでいるものもある(注:この問題は RSA 問題よりも簡単な(難しくない)ので強 RSA 問題と呼ぶのはおかしい)。

強RSA仮定 編集

「flexible RSA 問題は難しい」という仮定を強RSA仮定(きょうアールエスエイかてい, strong RSA assumption)という。より正確には、以下の通り。

素数生成機   で次を満たすものが存在する: 任意の多項式時間アルゴリズム A に対し、

 

negligible

関連項目 編集