Асимметричные криптосистемы на булевых функциях | Прикладная дискретная математика. 2018. № 40. DOI: 10.17223/20710410/40/3

Определяется новая асимметричная (с открытым ключом) криптосистема подстановок на множестве булевых векторов произвольной длины n, сочетающая в себе блочный шифр и схему цифровой подписи с функциональными ключами. В ней открытым ключом служит векторная булева функция f(x_1, ..., x_n) размерности n, получаемая операциями перестановки p1 и p2 и отрицания s1 и s2 над соответственно переменными (p1, s1) и координатными функциями (p2, s2) некоторой биективной векторной булевой функции g(x_1, ..., x_n) = (g_1(x_1, ..., x_n), ..., g_n(x_1, ..., x_n)), называемой порождающей функцией криптосистемы, где для каждого i из {1, ..., n} координатная функция g_i(x_1, ..., x_n) существенно зависит от небольшого числа переменных, а закрытым ключом является функция h, обратная к f, существующая ввиду биективности f, проистекающей из биективности g, сохраняемой в f применяемыми к g операциями перестановки и отрицания. Функции g_1, ..., g_n и их существенные переменные являются открытыми параметрами криптосистемы. (Вариант криптосистемы допускает их включение в закрытый ключ). Разумеется, операции перестановки p1 и p2 и отрицания s1 и s2, аналогично простым множителям в модуле RSA, должны быть закрытыми. Зашифрование блока P открытого текста в блок C шифртекста выполняется по правилу C = f(P), а его расшифрование - по правилу P = h(C). Подпись под P вычисляется как S = h(P), а её действительность проверяется равенством P = f(S). Стойкость данной криптосистемы основывается на трудной разрешимости задачи обращения обратимых функций - вычисления x = h(y) по y = f(x). Для нелегального пользователя (не знающего операций p1, p2, s1 и s2) это действительно трудная задача со сложностью решающего алгоритма O(2^n).