情報処理学会 第81回全国大会講演要旨

ラビン暗号の安全性は素因数分解の困難性に基づいており、小さな公開鍵指数が使用される。暗号化の際には乱数のパディングが必要であるが、短いパディングに対してはCoppersmithのショートパッドアタックが効果的であり、秘密情報を取得できることが知られている。Coppersmithのショートパッドアタックでは格子基底簡約が使用されるが、本稿ではCoppersmithのショートパッドアタックとは異なる格子を使用する攻撃法の概要を示す。本稿で示す格子の次元はCoppersmithのショートパッドアタックで使用される格子の次元の半分であり、格子基底簡約の高速化が可能であることを示す。