308
• (pk, sk) обозначает пару ключей открытый/закрытый (для шифрования с от-
крытым ключом и цифровых подписей)
• negl обозначает
пренебрежимо малую функцию; см. определение 3.4
• poly(n) обозначает произвольный полином
• polylog(n) обозначает poly(log(n))
• Funcn
обозначает множество функций, отображающих n-битные строки для
n-битных строк
• Permn обозначает множество взаимно однозначных соответствий на
n-битных
строках
• IV обозначает вектор инициализации (используется для режимов работы и
устойчивых к коллизиям хэш-функций)
Алгоримы и процедуры:
• tt обозначает псевдослучайный генератор
• F обозначает функцию с ключом, т.е., как правило, псевдослучайную функ-
цию
или перестановку
• (Gen, Enc, Dec) обозначает процедуры генерации ключа, шифрования и де-
шифрования,
соответственно, как для шифрования с открытым ключом, так и
для шифрования с закрытым ключом Для случая шифрования с закрытым клю-
чом, когда Gen не указан, то Gen(1n) выводит равномерное k ∈ {0, 1}n
• (Gen, Mac, Vrfy) обозначает процедуры генерации ключа, генерации тега и
верификации, соответственно, для аутентификационного кода сообщения. Ког-
да Gen не указан, то Gen(1n) выводит равномерное k∈0, 1}n
• (Gen, Sign, Vrfy) обозначает процедуры генерации ключа, генерации подпи-
си и верификации, соответственно,
для схемы цифровой подписи
• GenPrime обозначает ppt алгоритм, который на входе 1n, выводит n-битное
простое число, кроме как при пренебрежимо малой вероятности в n
• GenModulus обозначает ppt алгоритм, который на входе 1n выводит (N, p, q),
где N= pq и (кроме как, при пренебрежимо малой вероятности) p и q являются
n-битными
простыми числами
• GenRSA обозначает ppt алгоритм, который на входе 1n, выводит (кроме как,
при пренебрежимо малой вероятности) модуль N , целое e > 0 с наибольшим
общим делителем (e, φ(N )) = 1, и целое d, удовлетворяющее ed = 1 mod φ(N )
• G обозначает ppt алгоритм, который на входе 1n выводит (кроме как, при
пренебрежимо малой вероятности) описание циклической группы G, группо-
вого порядка q (с ||q|| = n), и генератор g ∈ G.