"Священный Грааль" криптографии
Активное развитие технологий последних десятилетий обусловило популяризацию криптографии, и термины, применяемые ранее только математиками-криптографами, теперь стали широко известны. В их числе термин «гомоморфное шифрование».
Попробуем же разобраться, какие задачи решают стандартные алгоритмы шифрования, каковы их ограничения и зачем потребовалось гомоморфное шифрование.
Классические криптографические схемы осуществляют некие параметрические (зависящие от ключа) отображения пространства открытых данных в пространство шифрованных. При этом инвертировать такое преобразование возможно только располагая этим самым параметром (ключом).
Характерная особенность алгоритмов шифрования ― рассеивание и перемешивание информации, представляющей собой открытый текст, вследствие чего не сохраняются метрики, определенные в пространстве открытых текстов. Например, результаты шифрования на одном ключе двух входных открытых текстов, различающихся лишь в одном бите, совершенно не близки меж собой в пространстве шифрованных текстов. В свою очередь, любое изменение данных, представляющих собой шифртекст, ведет к тому, что, расшифровывая их, мы получим просто случайные неинтерпретируемые данные.
Можно констатировать, что эра “больших данных” уже наступила. Развитие машинного обучения изменило многие сферы жизни, в том числе появились облачные вычислительные платформы, предоставляющие пользователям существенные вычислительные мощности и различные сервисы для обработки данных.
У клиентов имеется возможность защитить данные в процессе передачи в облако, но для осуществления обработки и анализа данных их необходимо расшифровывать.
Таким образом, клиент предоставляет свои данные, возможно, доверенные ему третьими лицами, неподконтрольному ему ресурсу, что множит вероятность утечки или несанкционированного доступа.
Существуют различные подходы к решению данной задачи: например, физическая изоляция серверов, ограничение взаимодействия с ним сторонних лиц. Однако в любом из этих случаев клиент вынужден верить, по сути, на слово и вверять свои данные защите, реализованной на стороне сервера.
Естественно, возникает желание обеспечить своим данным собственную защиту, как в случае с передачей, когда не обязательно полагаться лишь на реализацию транспортного протокола защиты: можно отправлять уже зашифрованные данные.
Концепция схемы шифрования, допускающей выполнение операций над зашифрованными данными таким образом, что расшифрование результата есть корректное преобразование открытых данных, соответствующих оперируемым шифртекстам, витала в криптографической среде порядка 30 лет и зачастую именовалась “Священным Граалем” криптографии.
Однако достижение этой идеи продвигалось достаточно сложно.
Первые шаги в направлении разработки схем шифрования, допускающих некоторые преобразования над зашифрованными данными, совпадают с работами над схемами шифрования с открытым ключом, которые, на самом деле, преследовали иные цели.
Выбираются большие простые числа p and q, вычисляется N = pq ― модуль системы и φ(N) = (p-1)(q-1) ― функция Эйлера, выбирается элемент eЄZN* и вычисляется соответствующий ему элемент d, такой что ⅇ ⋅d ≡ 1(mod ϕ(N)). Формируются открытый ключ системы ― (e, N), и секретный ключ ― (φ(N),d).
Алгоритм шифрования сообщения m представляет собой Enc(x)=me (mod N), обозначим его результат как с. Алгоритм расшифрования ― Dec(c) = сd(mod N).
Корректность следует из того, чтоcd (mod N) = (ce)d (mod N) = m(mod N), так как ⅇ⋅d ≡ 1(mod φ(N)).
В приведенной схеме пространство открытых текстов совпадает с пространством шифрованных текстов и представляет собой ZN. Предположим, что имеются два шифрованных текста с1 and с2, соответствующие сообщениям m1 and m2. Рассмотрим произведение с1 ⋅ с2(mod N) и попробуем его расшифровать.
Dec(с1 ⋅ с2) = (с1 ⋅ с2)d (mod N) = (m1e ⋅ m2e)d(mod N) = (m1 ⋅ m2)ed (mod N) = m1 ⋅ m2(mod N).
Откуда можно видеть, что произведение двух шифртекстов является корректным шифрованным текстом для произведения соответствующих открытых текстов. Такие отображения называют гомоморфными относительно тех операций, для которых рассмотренные свойства выполняются. В частности, функции Enc() и Dec() мультипликативно гомоморфны.
Мультипликативной гомоморфности недостаточно для большинства задач обработки данных, из-за чего поиск криптографически стойких алгоритмов с гомоморфными относительно большего количества операций функциями шифрования/расшифрования является основным вызовом на пути развития данного направления.
Классическое машинное обучение и глубокое обучение может быть декомпозировано на набор элементарных операций над данными либо аппроксимировано рядом простейших операций, тогда работа безопасных ML-алгоритмов с защищенными данными эквивалентна работе исходных версий этих алгоритмов над незащищенными данными. В таком случае данные могут подвергаться анализу, оставаясь зашифрованными.
Например, предположим, что у нас есть система обмена сообщениями, в которой сообщения должны быть зашифрованы от отправителя до получателя (end-to-end encryption). В то же время необходимо проверять сообщения на спам, не нарушая их конфиденциальности.
Таким образом, гомоморфное шифрование возвращает владельцам данных контроль над собственными данными.
Однако стоит понимать, что оно не является криптопанацеей и не способно заменить более высокопроизводительные схемы, но по аналогии с криптосистемами с открытым ключом способно занять свою нишу.
