Что это такое?
Гомоморфное шифрование (Homomorphic Encryption) очень долго было самым ярким открытием в молодой и бурно развивающейся области Computer Science — криптографии. Вкратце, такой тип шифрования позволяет делать произвольные вычисления на зашифрованных данных без их дешифровки. Например, гугл может осуществлять поиск по запросу не зная, что это за запрос, можно фильтровать спам, не читая писем, подсчитывать голоса, не вскрывая конверты с голосами, делать DNA тесты, не читая DNA и многое, многое другое.
То есть, человек/машина/сервер, производящий вычисления, делает механические операции с шифрами, исполняя свой алгоритм (поиск в базе данных, анализ на спам, и т.д.), но при этом не имеет никакого понятия о зашифрованной внутри информации. Только пользователь зашифровавший свои данные может расшифровать результат вычисления.
Здорово, правда? И это не из области фантастики — это то, что уже можно «теоретически» воплотить в жизнь.
От теории до практики не всегда, правда, рукой подать и иногда на это уходят десятилетия. Операции в современных схемах гомоморфного шифрования гораздо медленнее обычных и по закону Мура станут сравнимы со скоростью вычислений на сегодняшний день лет через 40. Но с каждым годом схемы становятся проще и быстрее, так что, кто знает, может уже не за горами новая веха в развитии IT технологий.
История создания
История создания первой схемы довольно необычна: профессор стэнфордского университета Dan Boneh взял за правило всем новоприбывшим аспирантам предлагать «Automatic PhD problem». Как правило, это очень сложная (но не гробовая) задача по криптографии, над которой ученые бьются хотя бы вот уже с десяток лет. В 2006 году Dan предложил придумать схему для Homomorphic Encryption своему новому студенту, Craig Gentry. Через два года Craig ее решил. Dan сдержал обещание и Craig стал одним из первых студентов кто так быстро получил доктора наук. Имея давнюю страсть к математике, Craig получил вначале юридическое образование и некоторое время работал юристом, пока в довольно сознательном возрасте не решил вновь вернуться к математике и поступил в аспирантуру Стэнфорда.
Простая идея
Схемы для гомоморфного шифрования были вначале доступны для понимания только специалистам в теории чисел, но за последние 5 лет они настолько упростились, что их основную идею можно объяснить школьнику.
Итак, представьте, что вы хотите зашифровать число x (может быть это всего лишь очередной бит ваших данных, может быть небольшое натуральное число). Выберите себе произвольный вектор v (он будет вашим секретным ключом). Возможно найти такую матрицу A, что будет верно Av ~= xv, т.е. произведение A на v даст примерно вектор v умноженный на число x (для тех кто помнит немножко алгебру, v будет «примерным» собственным вектором, а x «примерным» собственным числом матрицы A). Если вы захотите зашифровать новое число y, то опять же можно будет найти матрицу B, такую что Bv ~= yv. Таким образом вы можете, имея только один секретный ключ v, зашифровать сколько угодно чисел, где шифром каждого числа будет матрица. Чтобы расшифровать число, мы умножим матрицу на секретный вектор v.
Можно доказать, предполагая сложность одной архаической задачи про поиск короткого вектора в решетке, что также сложно, имея матрицы A и B, со значимой вероятностью (отличимой от случайного угадывания) сказать какие числа x и y они шифруют (не зная, разумеется, секретного вектора v).
Таким образом, это действительно шифровальная схема, но она также является гомоморфной! Т.е., оперируя с матрицами A и B, а именно умножая и складывая их, мы будем умножать и складывать те числа, которые они шифруют. Действительно, посмотрим, что даст расшифровка произведения A и B:
(AB)v = A (Bv) ~= A xv = x (Av) ~= (xy)v, она дает произведение x и y!
А расшифровка суммы A и B даст
(A + B)v = Av + Bv ~= xv + yv ~= (x + y)v, сумму x и y!
Конечно, здесь требуется более точный анализ, чтобы убедиться, что примерное равенство сохраняется. Также, нахождение шифрующей матрицы не совсем тривиальная задача, но во всем этом вполне реально разобраться, если ненадолго погрузиться в несколько хороших статей, как например вот эта:
[GSW'13] «Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based» (pdf)
Окно в новый мир
Craig открыл дверцу в своего рода новый мир. Сегодня мы имеем огромное количество вариаций гомоморфного шифрования и самое интересное, что одна из вариаций может дать лучший из возможных, теоретически самый стойкий способ обфускации программ, а это откроет еще больше возможностей для фантазии! Но об этом в другой раз. Если вам интересна текущая задача, за решение которой Dan дает PhD автоматически, пишите в комментариях ;)
Автор: valerini
