Гомоморфное шифрование
Гомомо́рфное шифрова́ние, схема шифрования данных, позволяющая проводить вычисления над зашифрованными данными без доступа к ключу.
При этом должны выполняться два условия: условие корректности и условие конфиденциальности. Первое условие означает, что можно получить результат некоторой функции от незашифрованных данных, заменив вычисление этой функции некоторой последовательностью вычислений над зашифрованными данными c последующим расшифрованием полученного результата. Условие конфиденциальности означает, что схема вычисления над зашифрованными данными и все полученные в процессе вычисления по этой схеме промежуточные данные не дают никакой дополнительной информации для расшифрования. Первое условие выполняется для тривиального шифрования, когда зашифрованные данные совпадают с исходными. Второе условие, условие конфиденциальности, отбрасывает такую возможность. При этом не обязательно предполагается, что любой эффективно вычислимой функции от незашифрованных данных должна соответствовать такая эффективно вычислимая функция от зашифрованных данных, для которой результат расшифрования её значения соответствовал бы значению исходной функции над незашифрованными данными.
Понятие гомоморфного шифрования имеет двойной смысл: во‐первых, это шифрование, а во‐вторых, это шифрование обладает дополнительным алгебраическим содержанием, связанным с понятием гомоморфизма. Такое гомоморфное шифрование может относиться к различным типам вычислений, как арифметическим, так и булевым. Соответственно, имеются следующие типы гомоморфного шифрования:
Частично гомоморфные схемы шифрования, поддерживающие вычисления схем, содержащих операции только одного типа: например, только сложение или умножение.
Частично гомоморфные схемы шифрования (англ. somewhat homomorphic encryption schemes), или схемы SHE‐шифрования, позволяющие выполнять вычисления с двумя операциями, но только для схем вычисления, принадлежащих некоторому множеству.
Полностью гомоморфное шифрование на схемах заданной глубины (т. е. с ограниченным максимальным числом последовательных операций, выполняемых в ходе вычислений). Такое шифрование позволяет вычислять произвольные функции, представимые схемами с заранее заданной глубиной.
Полностью гомоморфное шифрование (англ. fully homomorphic encryption; FHE‐шифрование), позволяющее производить вычисления функций, заданных схемами произвольной глубины и содержащих операции разных типов.
Впервые задача о гомоморфном шифровании сформулирована в 1978 г. (Rivest. On data banks ... 1978). Однако идея вычислений над зашифрованными данными настолько естественна и очевидна, что её появление лишь в 1978 г. выглядит весьма сомнительным. Вероятно, указанная работа – просто первая публикация, в которой эта идея обсуждалась публично. За этим последовали 30 лет безуспешных попыток найти такой метод шифрования, который позволил бы выполнять произвольные вычисления над зашифрованными данными. Наиболее значимые из этих попыток:
криптосистема RSA (Rivest. A Method for ... 1978), гомоморфная относительно умножения по заданному модулю (модулярного умножения);
криптосистема Эль Гамаля (ElGamal. 1985), гомоморфная относительно модулярного умножения;
гомоморфное шифрование в билинейных группах (Bonech. 1985), гомоморфная относительно сложения и одного скалярного произведения;
криптосистема Пэйе (Paillier. Public Key ... 1999; Paillier. Efficient Public‐Key ...1999), гомоморфная относительно модулярного сложения;
криптосистема Гольдвассер – Микали (Goldwasser. 1982; 1984), гомоморфная относительно «исключающего ИЛИ» (строгой дизъюнкции, XOR).
И, наконец, в 2009 г. была опубликована работа К. Джентри (Gentry. Fully Homomorphic Encryption Using ... 2009; Gentry. A fully homomorphic encryption scheme. 2009), в которой была предложена первая полностью гомоморфная схема шифрования. В этой схеме использовался метод шифрования на решётках (англ. ideal lattices), соответствующих идеалам в факторкольце кольца целочисленных многочленов по некоторому многочлену. Препятствием для построения полностью гомоморфной схемы было возрастание шума (англ. perturbation) в процессе вычислений над зашифрованными данными – обусловленным вероятностным характером метода шифрования и возможным несоответствием результата расшифрования вычисленного значения ожидаемым незашифрованным данным. При таком неоднозначном шифровании условие гомоморфности гарантируется только относительно фиксированного числа последовательных операций над зашифрованными данными, т. е. для схем определённой глубины. При его превышении результат может не соответствовать никакому открытому тексту.
Проблему ограниченности гомоморфности шифрования удалось решить введением процедуры внутреннего перешифрования (англ. bootstrapping) в процессе построения соответствующей схемы для вычислений по зашифрованным данным, позволившей уменьшать шум до допустимых пределов. Но главная заслуга Джентри – не процедура перешифрования, а доказательство, при некотором предположении, стойкости предложенной криптосистемы. Основной недостаток – слишком большое замедление вычислений. В дальнейшем были предложены модификации подхода Джентри (Fully Homomorphic ... 2010; A Guide to Fully Homomorphic Encryption; Nuida. 2015), однако задача построения практически, а не теоретически эффективного метода вычислений над зашифрованными данными пока не решена.
Основные возможные приложения связаны с удалёнными вычислениями, а также с облачными вычислениями (Варновский. 2007; 2016; Dijk van M. On the Impossibility of Cryptography Alone for Privacy‐Preserving Cloud Computing; О возможности стойкой обфускации ... 2019).
См. также Криптография.