Сокращение факторинга основных продуктов до факторизации целочисленных продуктов (в среднем случае)

10

Мой вопрос касается эквивалентности безопасности различных односторонних функций-кандидатов, которые могут быть построены на основе сложности факторинга.

Предполагая проблему

ФАКТОРИНГ: [Дано для случайных простых чисел , найти , ]P , Q < 2 n P QN=PQP,Q<2nPQ

невозможно решить за полиномиальное время с незначительной вероятностью, функция

PRIME-MULT: [Учитывая битовую строку качестве входных данных, используйте в качестве начального числа для генерации двух случайных простых чисел и (где длины , только полиномиально меньше длины ); затем выведите .]x P Q P Q x P QxxPQPQxPQ

может быть показано, чтобы быть односторонним.

Еще одна кандидатная односторонняя функция

INTEGER-MULT: [Учитывая случайные целые числа качестве входных данных, выводить .] A BA,B<2nAB

INTEGER-MULT имеет то преимущество, что его легче определить по сравнению с PRIME-MULT. (Обратите внимание, в частности, что в PRIME-MULT существует вероятность (хотя, к счастью, незначительная), что начальное число не может генерировать которые являются простыми.)P , QxP,Q

По крайней мере, в двух разных местах (Арора-Барак, Вычислительная сложность, с. 177, сноска 2) и ( Примечания к лекции Вадхана «Введение в криптографию» ) упоминается, что INTEGER-MULT является односторонним методом, предполагающим среднюю твердость факторинга. Тем не менее, ни один из этих двух не дает причину или ссылку на этот факт.

Итак, вопрос:

Как мы можем уменьшить в полиномиальном факторе времени с незначительной вероятностью до инвертирования INTEGER-MULT с незначительной вероятностью?N=PQ

Вот возможный подход (который, как мы увидим, НЕ работает!): Учитывая , умножьте N на гораздо более длинное (хотя и полиномиально) случайное целое число A ′, чтобы получить A = N A . Идея заключается в том , что " настолько велика , что она имеет множество простых делителей размером примерно равен P , Q , так что P , Q не«выделяться»среди главных факторов A . Тогда A имеет приблизительно распределение равномерно случайного целого числа в заданном диапазоне (скажем, [ 0N=PQNAA=NAAP,QP,QAA ). Затемслучайным образомвыберите целое число B из того же диапазона [ 0 , 2 n - 1 ] .[0,2n1]B[0,2n1]

Теперь, если инвертор для INTEGER-MULT может, учитывая , с некоторой вероятностью найти A , B < 2 n, такой, что A B = A B , есть надежда, что один из A или B содержит P как фактор , а другой содержит Q . Если бы это было так, то мы можем найти P или Q , взяв НОД А ' с N = P Q .ABA,B<2NAB=ABABPQPQAN=PQ

Проблема состоит в том, что инвертор может выбрать разделение основных факторов, например, помещая малые факторы в A и большие в B , так что P и Q заканчиваются как в A ′, так и в обоих в B .ABABPQAB

Есть ли другой подход, который работает?

Омид Этесами
источник
Можем ли мы уменьшить вероятность ошибки экспоненциально малой INT-FACT, а затем использовать плотность простых чисел, чтобы сказать, что она не потерпит неудачу на большинстве произведений с двумя простыми числами?
Каве
2
Если бы мы могли инвертировать INTEGER-MULT для всех экземпляров, кроме экспоненциально малой доли экземпляров, действительно, ФАКТОРНОЕ произведение простых чисел было бы легко. Но я не знаю, как получить сильный инвертор от слабого инвертора.
Омид Этесами
1
(Как-то) обратная сторона этой проблемы уже обсуждалась здесь .
MS Dousti

Ответы:

4

Это не совсем ответ, но он проливает некоторый свет на трудность демонстрации таких сокращений.


Задача может быть обобщена следующим образом: Пусть - алгоритм, который решает задачу INTEGER-MULT с пренебрежимо малой вероятностью. Пусть эта вероятность будет по крайней мере n - c для некоторой константы c N (когда размер ввода равен n ). Докажите , что существует PPT (вероятностное полиномиальное время) алгоритм A ' , который использует A в качестве подпрограммы и решает экземпляр задачи FACTORING размера п с вероятностью по крайней мере п - г , для некоторой константы D N .AnccNnAAnnddN

Рассмотрим алгоритм который решает задачу INTEGER-MULT тогда и только тогда, когда вход N имеет специальное значение из N = P Q R , где P и Q - простые числа размера n / 4, а R - простое число размера n / 2. и в противном случае не удается. Кроме того, на входе целое число N указанного выше вида, он выводит P Q и R . Сначала покажем, что AAN N=PQRPQn/4Rn/2NPQRAимеет ничтожную вероятность решения задачи INTEGER-MULT. Для этого достаточно найти долю битных целых чисел специального вида, так как эта доля ограничивает вероятность успеха A снизу.nA

По теореме простых чисел число простых чисел, размер которых равен -битам:k

2k/ln(2k)2k1/ln(2k1)=Θ(2k/k)

Следовательно, доля битных целых чисел специальной формы составляет:n

Θ(2n/4/(n/4))2Θ(2n/2/(n/2))2n1=Θ(n3)

что немаловажно в .n

Таким образом, следует иметь возможность доказать существование РРТ алгоритм , который использует A * в качестве подпрограммы и решает экземпляр задачи FACTORING размера п с вероятностью по крайней мере п - г , для некоторой константы D N .AAnnddN

ИМХО, это кажется очень трудной задачей, так как только (частично) разлагается целые специальной формы, и не кажется , что должен быть способ , чтобы использовать его для разложения чисел вида P Q .APQ

М.С. Дусти
источник