ブルム・ミカリアルゴリズム

Blum –Micaliアルゴリズムは、暗号学的に安全な擬似乱数生成器です。このアルゴリズムの安全性は、離散対数を計算することの難しさから得られます。^{[ 1 ]}

させて${\displaystyle p}$奇素数とし、${\displaystyle g}$原始根モジュロである${\displaystyle p}$。 させて${\displaystyle x_{0}}$種となり、

${\displaystyle x_{i+1}=g^{x_{i}}\ {\bmod {\ p}}}$。

の${\displaystyle i}$アルゴリズムの th 出力は、 ${\displaystyle x_{i}\leq {\frac {p-1}{2}}}$それ以外の場合は出力は0になります。これは1ビットを使用することに相当します。${\displaystyle x_{i}}$乱数として。${\displaystyle nc-1}$断片${\displaystyle x_{i}}$離散対数問題を解くことが、指数がわずかであっても不可能な場合に使用できます。${\displaystyle c}$ビット。^{[ 2 ]}

このジェネレーターが安全であるためには、素数が${\displaystyle p}$離散対数を計算するには、 が十分に大きい必要があります。${\displaystyle p}$実現不可能である。^{[ 1 ]} より正確には、生成される数を予測するあらゆる方法は、その素数に対する離散対数問題を解くアルゴリズムにつながる。^{[ 3 ]}

ブルム・ミカリ構成に対する量子永久侵害攻撃の可能性のある例について議論した論文がある。この攻撃は、ブルム・ミカリ生成器に対する以前の攻撃が、ブルム・ブルム・シュブ生成器やカリスキ生成器を含むブルム・ミカリ構成全体に拡張できることを示している。^{[ 4 ]}

• https://web.archive.org/web/20080216164459/http://crypto.stanford.edu/pbc/notes/crypto/blummicali.xhtml