Короткая случайность в Эль-Гамале и Пайе

Семантическая безопасность в этом случае сводится к семантической безопасности для стандартной схемы тогда и только тогда, когда определенное низкоэнтропийное распределение в подгруппе «нулевого шифротекста» вычислительно неотличимо от случайного.

• В случае Эль-Гамаля предполагается, что $(г^г, ч^г)$ для случайного малого $г$ вычислительно неотличим от стандартной пары DH, а именно $(г^г, ч^г)$ для униформы $г$. Это было изучено Куросавой и Косибой в Бумага ПКС 2004, и они показали, что предположение выполняется, если вычислительная задача дискретного логарифма с коротким показателем сложна. Для групп криптографической значимости наилучшей атакой на дискретный журнал с коротким показателем обычно является либо лямбда Полларда, либо то же самое, что и для некоротких дискретных журналов, поэтому, если $г$ достаточно велик (как минимум в два раза больше параметра безопасности), это считается допустимым. Однако это связано с $г$ в любом случае это то же самое, что и граница полноразмерной экспоненты, если вы правильно задали параметры, поэтому в большинстве случаев это бесполезно.

• В случае Пайе предполагается, что $r^n$ для маленьких $г$ вычислительно неотличима от случайной в подгруппе порядка $\varphi(n)$ из $\mathbb{Z}/n^2\mathbb{Z}$. Я не знаю о какой-либо атаке на эту конкретную проблему, и это выглядит несколько правдоподобно, если $г$ не так уж и мало, хотя я не знаю, с каким более стандартным предположением это могло бы быть связано. Несмотря на это, ускорение от использования меньшего $г$ в расчете $r^n \bmod n^2$ должно быть незначительным (на самом деле ускорения не должно быть вообще, если вы используете быструю арифметику), так что я тоже не уверен, что вижу смысл в этом варианте.