Модифицируемое шифрование


Вскоре вы сможете позволить своим конфиденциальным данным бесплатно обрабатываться в сети на любом количестве облачных серверов и при этом быть в безопасности, зная, что, хотя они могут вносить в них изменения, у них никогда не будет доступа к ним. Уловка называется «гомоморфное шифрование», и это самая захватывающая идея в криптографии за последние десять лет.

Это может показаться неинтересным, но «полностью гомоморфное шифрование» является очень востребованной функцией системы шифрования.

Идею довольно легко объяснить. Предположим, у вас есть стоимость, скажем, ставка на аукционе, и она зашифрована, чтобы держать ее подальше от посторонних глаз. Теперь предположим, что вам нужно добавить единицу к текущей ставке. На данный момент единственный способ сделать это – взять зашифрованное значение, расшифровать его, добавить его и повторно зашифровать. Если вы не знаете, как расшифровать значение, вы не сможете его изменить. К сожалению, это означает, что если вы хотите, чтобы что-то или кто-то изменил ваши зашифрованные данные, у вас нет другого выбора, кроме как предоставить им полный доступ к ним.

Однако полностью гомоморфное шифрование позволяет пользователю изменять зашифрованное значение, не зная, что это такое и как его расшифровать. То есть, если у вас есть операция, которую вы хотите выполнить с простым текстом, полностью гомоморфная система шифрования позволит вам выполнить операцию, обычно не ту же операцию, с зашифрованным текстом, которая при расшифровке зашифрованного текста дает тот же результат. .

Это немного похоже на возможность манипулировать содержимым запечатанного конверта, не открывая его и не зная, что в нем содержится.

Если такая система существовала, то ее применение несложно придумать – например, безопасная процедура голосования. Также очевидно, что такая схема шифрования особенно важна в наш век облачных вычислений. Полностью гомоморфное шифрование позволит облачным службам хранить ваши данные и манипулировать ими, даже не зная, что они содержат, и не имея к ним доступа.

На данный момент существует ряд частично гомоморфных систем шифрования, которые поддерживают одну операцию, сложение или умножение. Полностью гомоморфная система поддерживает сложение и умножение и, следовательно, все арифметические операции.

В 2009 году Крейг Джентри изобрел полностью гомоморфную систему шифрования (тезис: Полностью гомоморфная схема шифрования). Он начал со схемы «несколько гомоморфного шифрования», которая звучит как очень неточный и нематематический термин. Идея состоит в том, что вы можете создавать системы, которые являются гомоморфными, но по мере того, как вы складываете и умножаете шифротексты, они накапливают «шум», который в конечном итоге делает их нечитаемыми. Джентри взял несколько гомоморфную систему и продемонстрировал, как улучшить кодирование, чтобы удалить шум, чтобы получить полностью гомоморфную систему. К сожалению, система Gentry слишком сложна для реализации для реалистичного уровня безопасности.

Симметричное шифрование и Боб, и Алиса должны иметь один и тот же ключ к данным (Odder).

С момента открытия Джентри другие люди работали над более практичной системой, и все продвигалось к полностью реализуемой системе, которую можно было бы использовать для ряда новых приложений. В конце 2009 года Мартен ван Дейк, Крейг Джентри, Шай Халеви и Винод Вайкунтанатан представили упрощенную полностью гомоморфную систему: полностью гомоморфное шифрование над целыми числами. Еще совсем недавно Н. Смарт и Ф. Веркаутерен опубликовали еще одну более простую схему полностью гомоморфного шифрования с относительно малым размером ключа и зашифрованного текста. Оба результата используют преобразование «несколько» гомоморфной схемы шифрования в полностью гомоморфную схему с использованием очистки для исправления накопившегося шума.

Пока что кажется, что для того, чтобы очистка была эффективной, необходимы очень большие размеры параметров, и именно это делает всю схему неэффективной. Учитывая, сколько раз алгоритм будет применяться в любом реальном приложении, эффективность действительно важна.

Вы можете думать об этом как о необходимости встроить в шифр код исправления ошибок. Каждый действительный зашифрованный текст должен быть окружен уникальным пузырем недействительных зашифрованных текстов, в который манипуляция, сложение и умножение преобразует зашифрованный текст. Эти недопустимые зашифрованные тексты не могут быть декодированы, но поскольку каждый из них однозначно связан с действительным зашифрованным текстом, процесс «очистки» может исправить код, заменив его ближайшим действительным зашифрованным текстом. Фактический метод очистки работает с использованием второго ключа для шифрования данных и удаления ошибок.

Кажется вероятным, что практическая гомоморфная система будет создана очень скоро, и в знак признания его работы 16 июня 2010 г. Крейг Джентри был удостоен награды за докторскую диссертацию от ACM на сумму 20 000 долларов.

Путь Джентри в математику и проблема, имеющая некоторое значение для вычислений, также является интересным. Сначала он окончил Гарвардский юридический факультет, но со степенью бакалавра математики, так как ему наскучило право интеллектуальной собственности. В 2005 году Джентри поступил в Стэнфордский университет со степенью доктора философии. программу, а в июне 2008 года прошел трехмесячную стажировку в IBM, где изобрел алгоритм, который вызывает всю суету.

Обновление: 19 апреля 2011 г.

Джентри был удостоен награды ACM Grace Hopper 2010 за свою работу по гомоморфному шифрованию, а американское военное исследовательское агентство DARPA наградило исследовательского подрядчика Galois Inc почти 5 миллионами долларов на повышение производительности его алгоритма.

Смотрите: DARPA тратит 20 миллионов долларов на гомоморфное шифрование

неразборчивый


Добавить комментарий