В «Введении в современную криптографию» Каца есть несколько сложных задач, и для каждой проблемы есть эксперимент, в котором алгоритм создает экземпляр проблемы, а другой алгоритм решает экземпляр проблемы. Например, рассмотрим задачу дискретного логарифмирования в 9.3.2:
Пусть GG — алгоритм генерации групп, который для каждого n генерирует (G, q, p).
Пусть A — алгоритм решения задачи.
Дискретно-логарифмический эксперимент DLog_{A,GG} (n):
- Запустите GG(1^n), чтобы получить (G, q, g), где G — циклическая группа порядка q (с kqk = n), а g — генератор группы G.
- Выберите униформу h в G .
- A задано G , q, g, h и выводит x в Z_q .
- Выход эксперимента определяется как 1, если g^x = h, и 0 в противном случае.
ОПРЕДЕЛЕНИЕ 9.63. Мы говорим, что задача дискретного логарифмирования трудна относительно GG, если для всех вероятностных полиномиальных алгоритмов A существует пренебрежимо малая функция negl такая, что Pr[DLog
A,GG(n) = 1] = negl(n).
Является ли такое определение и анализ сложности проблемы, включающее понятие «эксперимент», стандартным для анализа сложности проблем в целом (не только в криптографии)?
Используются ли в книгах по анализу сложности проблем такое определение и анализ сложности проблемы?
Спасибо.
