Проблема более высокой остаточности - Higher residuosity problem

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

Математический фон

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

В группа единиц любого кольца образуют группа, а группа единиц в традиционно обозначается .

Из изоморфизма выше имеем

как изоморфизм группы. С п и q считались простыми, группы и находятся циклический заказов п-1 и q-1 соответственно. Если d является делителем п-1, то набор dсилы в образуют подгруппу индекс d. Если gcd (d,q-1) = 1, тогда каждый элемент в это dй степени, поэтому набор dсилы в также является подгруппой индекса d. В общем, если gcd (d,q-1) = грамм, то есть (q-1)/(грамм) dсилы в , поэтому набор dсилы в имеет индекс dgЭто чаще всего наблюдается, когда d= 2, и мы рассматриваем подгруппу квадратичные вычеты, как известно, ровно четверть элементов в аревадратные остатки (когда п является произведением ровно двух простых чисел, как здесь).

Важным моментом является то, что для любого делителя d из п-1 (или q-1) набор dth степеней образует подгруппу

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

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

Обратите внимание, что если п и q известны, легко определить, Икс это dй остаток по модулю п потому что Икс будет dй остаток по модулю п если и только если

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

Приложения

В семантическая безопасность из Криптосистема Бенало и Криптосистема Наккаш-Стерна зиждется на неразрешимости этой проблемы.

Рекомендации

  1. ^ Чжан, Юлянь; Цутому Мацумото; Хидеки Имаи (1988). "Криптографические приложения проблемы остаточности th с нечетным целым числом". Сделки IEICE. 71 (8): 759–767. CiteSeerX  10.1.1.137.8511.