Вопрос 1

Вероятностные полиномиальные алгоритмы. ВМТ

С формальной точки зрения криптографические алгоритмы, в том числе алгоритмы, по которым действуют участники протоколов, представляются многоленточными машинами Тьюринга с входным и выходным алфавитом {0,1}, но не обычными, а вероятностными (ВМТ). Это значит, что в ходе работы такая машина может «подбрасывать монетку» или, что то же самое, у каждой такой машины есть дополнительная входная случайная лента, с ко-торой считываются случайные биты. Это соответствует, например, случайному выбору ключа шифрования, выбору случайного значения в ходе протокола и т. д.

Таким образом, о результате и времени работы такой машины или алгоритма А для входных данных х  М можно говорить только с некоторой вероятностью, точнее, рассматривать распределение результата А(х,r) и времени работы t_A(x,r), где в качестве r подставляются значения случайной величины, равномерно распределенной на {0,1}^* — множестве битовых строк конечной длины.

Мы будем рассматривать алгоритмы, время работы которых ограничено значением некоторой функции Т_A( |х|) от длины аргумента— |х|, которая в данном случае является параметром сложности. При этом для каждого значения х можно полагать, что r равномерно распределено на

В дальнейшем будут использоваться следующие обозначения:

• Р (х) — вероятность события х;

• М() — математическое ожидание случайной величины ;

• А(х) —случайная величина, результат алгоритма А на входных данных х при условии равномерного распределения содержимого случайной ленты;

• А(х,у) — то же самое, что А(х || у), при условии, что алгоритм А может точно определить, где на входной ленте кончается х и начинается у;

• t_A(x) — случайная величина, количество шагов алгоритма А на входных данных х при условии равномерного распределения содержимого случайной ленты;

• f(A(x)) — случайная величина, результат подстановки в качестве аргумента функции f значения случайной величины А (х);

• у=А(х) — выбор значения у в соответствии с распределением случайной величины А(х);

• уА(х) — значение у является одним из возможных значений случайной величины А (х);

• у_R М. — выбор значения у, равномерно распределенного на множестве М;

• если алгоритм А в ходе своей работы обращается к некоторому оракулу (вызывает подпрограмму), а В — алгоритм, то А^B — алгоритм, полученный в результате подстановки в качестве оракула вызовов алгоритма В.

Определение 1. Вероятностный алгоритм А(х,r) называется полиномиальным, если существует многочлен q такой, что для всех х

.

Иногда ограничения на полиномиальность ослабляются и рассматриваются алгоритмы, удовлетворяющие следующему определению.

Определение 2. Вероятностный алгоритм А(х,r) называется полиномиальным в среднем (expected polynomial-time), если существует многочлен q такой, что для всех х

К сожалению, класс полиномиальных в среднем алгоритмов в смысле этого определения оказывается незамкнутым по отношению к применению одного алгоритма в качестве подпрограммы (оракула) в другом алгоритме (А^B может не удовлетворять определению, даже если А и В удовлетворяют ему). Поэтому, если необходимо рассматривать полиномиальные в среднем алгоритмы, пользуются другим определением.

Определение 3. Вероятностный алгоритм А(х,r) называется полиномиальным в среднем, если существует  >0 такое, что для всех х

При 0<<1 (интересный случай) из неравенства Иенсена, утверждающего, что f(М())М (f()) для любой выпуклой функции f, следует

и алгоритм, удовлетворяющий определению 2, удовлетворяет и определению 3. Однако определение 3 интуитивно неочевидно, и мы будем пользоваться просто определением полиномиального алгоритма 1.

Итак, время работы вероятностного полиномиального алгоритма всегда ограничено значением многочлена от длины аргумента. Однако, когда говорят, что полиномиальный алгоритм решает ту или иную задачу, имеется в виду, что он может ошибаться с пренебрежимо малой вероятностью, т. е. для любого полинома р при достаточно больших значениях параметра надежности | х | вероятность ошибки меньше р( | х | )^-1. [1]

Вопрос 2,3

Односторонние функции

Определение. Функция f: X  Y называется односторонней (oneway Junction), если существует эффективный алгоритм для вычисления f(x), но не существует эффективного алгоритма для вычисления хотя бы одного элемента прообраза f^--1(у).

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

Обозначим через U_n случайную величину, равномерно распределенную на {0,1}ⁿ. Через 1ⁿ будем обозначать унарное представление числа п, т.е. последовательность из п единиц.

Определение.1 Функция f: {0,1}^*  {0,1}^* называется (сильной) односторонней (strong one-way), если выполнены следующие два условия.

• Существует детерминированный полиномиальный алгоритм А, вычисляющий эту функцию, — для всех х  {0,1}^* А (х) =f(x).

• Для любого вероятностного полиномиального алгоритма В, любого многочлена q, для достаточно больших n

Грубо говоря, при случайном выборе аргумента х трудно подобрать прообраз для f(x).

Общая длина аргументов алгоритма В с ростом п растет не более чем полиномиально. Дополнительный аргумент 1ⁿ понадобился, чтобы эта длина зависела от n по крайней мере линейно и можно было измерять сложность алгоритма В в зависимости от длины аргумента алгоритма А. Если дополнительного аргумента нет, то, например, функция, выдающая двоичное представление длины аргумента (f(x)= |x|), окажется односторонней, поскольку, хотя прообраз указать легко, никакой полиномиальный алгоритм не успеет его выдать.

Если функция f сохраняет длину, т. е. |f(x)| = |х|, то дополнительный аргумент не нужен. Если функция сохраняет длину и взаимно однозначна, то она является перестановкой (в обычном смысле).

Из определения 1 легко получить определение (сильной) неравномерно односторонней функции, заменив второе условие условием

которое должно выполняться для любого полиномиального семейства логических схем .

Семейства односторонних функций

Для описания практически применяемых конструкций удобнее использовать несколько более сложное определение. Вместо функций будем рассматривать семейства функций вида . Здесь К{0,1 }* — бесконечное множество, элементы которого называются ключами или индексами. Для каждого k К множество D_k конечно.

Определение.2 Семейство функций называется семейством (сильных) односторонних функций, если существуют три вероятностных полиномиальных алгоритма (I,S,F) таких, что выполнены следующие условия.

• Алгоритм выбора ключа I для аргумента 1ⁿ задает случайную величину со значениями в где р — многочлен.

• Алгоритм выбора аргумента S для аргумента k К задает случайную величину со значениями в D_k.

• Алгоритм вычисления функции F(k_,x) для k К, х D_k выдает f_k(x).

• Для любого вероятностного полиномиального алгоритма В, любого многочлена а, для достаточно больших п

где I_п и Х_п — случайные величины,

По любому семейству односторонних функций можно построить «единую» одностороннюю функцию и наоборот.

Примеры семейств предположительно односторонних функций.

• Функция RSA. Множество ключей состоит из пар вида k=(pq,e), удовлетворяющих требованиям к открытым компонентам ключей RSA, . Алгоритм I по аргументу 1ⁿ выбирает пару чисел р и q, равномерно распределенных среди простых чисел между 2^n-1 и 2^п, простое число е и выдает ключ (pq,e). Алгоритм S выбирает . Функция f_k является односторонней перестановкой D_k..

• Функция Рабина строится аналогично функции RSA, но ключ состоит из единственного значения k=(pq), a f_k(x)=x²mod pq. Если алгоритм I выбирает в качестве ключей числа Блума, a D_k = QR_pq— множество квадратичных вычетов по модулю pq, то получается семейство односторонних перестановок.

• Дискретная показательная функция. Ключом, который выбирается алгоритмом I по аргументу 1ⁿ, являются случайно и равномерно выбранное простое число р между 2^n-1 и 2^п и образующий элемент g  Z_p* По ключу k=(p,g) алгоритм S выбирает . Алгоритм F вычисляет f_k(x)=g^x mod p. В результате получается семейство односторонних перестановок. Вместо Z^*_p можно выбирать любую группу, в которой трудно вычисляется дискретный логарифм. [1]

Вопрос 4

Определение односторонней функции с ловушкой.

Определение. Односторонняя функция f:ХУ называется односторонней функцией с ловушкой (one-way trapdoor function), если f^--1(у) можно вычислить за полиномиальное время, имея некоторую дополнительную информацию, т, е. существует функция g(у,t), вычислимая за полиномиальное время и такая, что g(y, t)= f^--1(у) для некоторой ловушки (trapdoor) t.

Пример односторонней функции с ловушкой дает функция Рабина. При этом ловушкой служит разложение модуля на множители.

Односторонние перестановки с ловушкой

Определение. Семейство функций {f_k:D_k{0,1}^* }_k_K называется семейством (сильных) односторонних перестановок с ловушкой (one-way trapdoor permutations), если существуют четыре вероятностных полиномиальных алгоритма (I,S,F,F^-1) таких, что выполнены следующие условия.

• Алгоритм выбора пары ключей I для аргумента 1ⁿ задает случайную величину со значениями в ,где р — многочлен. Результат работы алгоритма обозначим I(lⁿ) = (e,d). Обозначим через I₁ алгоритм, который для аргумента 1ⁿ вычисляет е, а через I₂ — алгоритм, который для аргумента 1ⁿ вычисляет d.

• Алгоритмы (I₁,S,F) задают семейство (сильных) односторонних перестановок.

• Алгоритм F^-1 — детерминированный полиномиальный алгоритм обращения с использованием ловушки такой, что для любой пары (e,d) из области значений I, для любого х  D_k

.

Для функции RSA ловушкой, соответствующей ключу (pq,e), является разложение модуля на множители (p,q) или пара (pq,d) такая, что ed  1(mod (pq)). Для функции Рабина ловушкой является разложение модуля на множители. [1]

Вопрос 5