Мой вопрос касается эквивалентности безопасности различных односторонних функций-кандидатов, которые могут быть построены на основе сложности факторинга.
Предполагая проблему
ФАКТОРИНГ: [Дано для случайных простых чисел , найти , ]P , Q < 2 n P Q
невозможно решить за полиномиальное время с незначительной вероятностью, функция
PRIME-MULT: [Учитывая битовую строку качестве входных данных, используйте в качестве начального числа для генерации двух случайных простых чисел и (где длины , только полиномиально меньше длины ); затем выведите .]x P Q P Q x P Q
может быть показано, чтобы быть односторонним.
Еще одна кандидатная односторонняя функция
INTEGER-MULT: [Учитывая случайные целые числа качестве входных данных, выводить .] A B
INTEGER-MULT имеет то преимущество, что его легче определить по сравнению с PRIME-MULT. (Обратите внимание, в частности, что в PRIME-MULT существует вероятность (хотя, к счастью, незначительная), что начальное число не может генерировать которые являются простыми.)P , Q
По крайней мере, в двух разных местах (Арора-Барак, Вычислительная сложность, с. 177, сноска 2) и ( Примечания к лекции Вадхана «Введение в криптографию» ) упоминается, что INTEGER-MULT является односторонним методом, предполагающим среднюю твердость факторинга. Тем не менее, ни один из этих двух не дает причину или ссылку на этот факт.
Итак, вопрос:
Как мы можем уменьшить в полиномиальном факторе времени с незначительной вероятностью до инвертирования INTEGER-MULT с незначительной вероятностью?
Вот возможный подход (который, как мы увидим, НЕ работает!): Учитывая , умножьте N на гораздо более длинное (хотя и полиномиально) случайное целое число A ′, чтобы получить A = N A ′ . Идея заключается в том , что " настолько велика , что она имеет множество простых делителей размером примерно равен P , Q , так что P , Q не«выделяться»среди главных факторов A . Тогда A имеет приблизительно распределение равномерно случайного целого числа в заданном диапазоне (скажем, [ 0 ). Затемслучайным образомвыберите целое число B из того же диапазона [ 0 , 2 n - 1 ] .
Теперь, если инвертор для INTEGER-MULT может, учитывая , с некоторой вероятностью найти A ′ , B ′ < 2 n, такой, что A ′ B ′ = A B , есть надежда, что один из A ′ или B ′ содержит P как фактор , а другой содержит Q . Если бы это было так, то мы можем найти P или Q , взяв НОД А ' с N = P Q .
Проблема состоит в том, что инвертор может выбрать разделение основных факторов, например, помещая малые факторы в A ′ и большие в B ′ , так что P и Q заканчиваются как в A ′, так и в обоих в B ′ .
Есть ли другой подход, который работает?
Ответы:
Это не совсем ответ, но он проливает некоторый свет на трудность демонстрации таких сокращений.
Задача может быть обобщена следующим образом: Пусть - алгоритм, который решает задачу INTEGER-MULT с пренебрежимо малой вероятностью. Пусть эта вероятность будет по крайней мере n - c для некоторой константы c ∈ N (когда размер ввода равен n ). Докажите , что существует PPT (вероятностное полиномиальное время) алгоритм A ' , который использует A в качестве подпрограммы и решает экземпляр задачи FACTORING размера п с вероятностью по крайней мере п - г , для некоторой константы D ∈ N .A n−c c∈N n A′ A n n−d d∈N
Рассмотрим алгоритм который решает задачу INTEGER-MULT тогда и только тогда, когда вход N имеет специальное значение из N = P Q R , где P и Q - простые числа размера n / 4, а R - простое число размера n / 2. и в противном случае не удается. Кроме того, на входе целое число N указанного выше вида, он выводит P Q и R . Сначала покажем, что A ∗A∗ N N=PQR P Q n/4 R n/2 N PQ R A∗ имеет ничтожную вероятность решения задачи INTEGER-MULT. Для этого достаточно найти долю битных целых чисел специального вида, так как эта доля ограничивает вероятность успеха A ∗ снизу.n A∗
По теореме простых чисел число простых чисел, размер которых равен -битам:k
Следовательно, доля битных целых чисел специальной формы составляет:n
что немаловажно в .n
Таким образом, следует иметь возможность доказать существование РРТ алгоритм , который использует A * в качестве подпрограммы и решает экземпляр задачи FACTORING размера п с вероятностью по крайней мере п - г , для некоторой константы D ∈ N .A′ A∗ n n−d d∈N
ИМХО, это кажется очень трудной задачей, так как только (частично) разлагается целые специальной формы, и не кажется , что должен быть способ , чтобы использовать его для разложения чисел вида P Q .A∗ PQ
источник