強力なRSA仮定

暗号学において、強いRSA仮定は、ソルバーが公開指数e ( e  ≥ 3)を選択できる場合でも、RSA 問題は解決不可能であると述べています。より具体的には、未知の因数分解の法Nと暗号文C が与えられた場合、 C  ≡  M ^e  mod  Nとなるようなペア ( M、  e ) を見つけることは不可能です。  

強力な RSA 仮定は、ランダム オラクル モデルに頼ることなく、存在偽造に対して証明可能な安全性を備えた署名スキームを構築するために最初に使用されました。

• 二次残差問題
• 決定的複合残余仮定

• Barić N.、Pfitzmann B. (1997) 衝突のないアキュムレータとツリーのないフェイルストップ署名方式。Fumy W. (編) 暗号学の進歩 - EUROCRYPT '97。EUROCRYPT 1997。コンピュータサイエンスの講義ノート、vol 1233。Springer、ベルリン、ハイデルベルク。doi : 10.1007 /3-540-69053-0_33
• 藤崎 栄、岡本 孝 (1997) モジュラー多項式関係を証明する統計的ゼロ知識プロトコル。Kaliski BS (編) 暗号学の進歩 - CRYPTO '97。CRYPTO 1997。コンピュータサイエンスの講義ノート、vol 1294。Springer、ベルリン、ハイデルベルク。doi :10.1007/ BFb0052225
• ロナルド・クレイマーとビクター・ショウプ。1999年。「強いRSA仮定に基づく署名方式」。第6回ACMコンピュータおよび通信セキュリティ会議（CCS '99 ）の議事録。米国ニューヨーク市計算機協会、46～51ページ。doi : 10.1145/319709.319716
• ロナルド L. リベストとバート カリスキ2003. RSA 問題pdf ファイル