Проблема с более высоким остатком

В криптографии большинство криптосистем с открытым ключом основано на проблемах, которые считаются неразрешимыми. Проблема более высокой невязкости (также называемая проблемой n -й невязкости ) является одной из таких проблем. Эту проблему легче решить, чем целочисленную факторизацию , поэтому предположение о том, что эту проблему трудно решить, сильнее, чем предположение о том, что целочисленная факторизация сложна.

Математическая основа

Если n целое число , то целые числа по модулю n образуют кольцо . Если n = pq , где p и q — простые числа , то китайская теорема об остатках говорит нам, что

$\mathbb {Z} /n\mathbb {Z} \simeq \mathbb {Z} /p\mathbb {Z} \times \mathbb {Z} /q\mathbb {Z}$

Единицы группу любого кольца образуют при умножении, а группу единиц при $\mathbb {Z} /n\mathbb {Z}$ традиционно обозначается $(\mathbb {Z} /n\mathbb {Z} )^{\times }$.

Из кольцевого изоморфизма , приведенного выше, мы имеем

$(\mathbb {Z} /n\mathbb {Z} )^{\times }\simeq (\mathbb {Z} /p\mathbb {Z} )^{\times }\times (\mathbb {Z} /q\mathbb {Z} )^{\times }$

как изоморфизм групп . Поскольку p и q предполагались простыми, группы $(\mathbb {Z} /p\mathbb {Z} )^{\times }$ и $(\mathbb {Z} /q\mathbb {Z} )^{\times }$ являются циклическими порядка p −1 и q −1 соответственно. Если d является делителем − 1 p , то набор d- х степеней в $(\mathbb {Z} /p\mathbb {Z} )^{*}$ образуют подгруппу индекса ​ d . Если НОД( d , q −1) = 1, то каждый элемент в $(\mathbb {Z} /q\mathbb {Z} )^{\times }$ является d -й степенью, поэтому набор d- й степени в $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ также является подгруппой индекса d . случае, если gcd( d , q ) g , = − 1 в В общем то $(\mathbb {Z} /q\mathbb {Z} )^{\times }$, поэтому набор d- х степеней в $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ имеет индекс dg .Чаще всего это наблюдается при d = 2, а мы рассматриваем подгруппу квадратичных вычетов , как известно, ровно четверть элементов в $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ являютсяквадратичные вычеты (когда n является произведением двух простых чисел, как здесь).

Важным моментом является то, что для любого делителя d числа p −1 (или q −1) набор d- х степеней образует подгруппу $(\mathbb {Z} /n\mathbb {Z} )^{\times }.$

Постановка задачи

Учитывая целое число n = pq , где p и q неизвестны, целое число d такое, что d делит p −1, и целое число x < n , невозможно определить, ли x является d -й степенью (эквивалентно d -м остатком) по модулю н .

Обратите внимание: если известны p и q, легко определить, ли x является d-м остатком по модулю n, потому что x будет d-м остатком по модулю p тогда и только тогда, когда

$x^{(p-1)/d}\equiv 1{\pmod {p}}$

Когда d = 2, это называется квадратичной проблемой невязкости .

Приложения

Семантическая безопасность криптосистемы Бенало и криптосистемы Наккеша–Штерна основана на трудноразрешимости этой проблемы.