Часть I. Homomorphic encryption — святой Грааль онлайн-конфиденциальности

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

Крупные игроки, такие как Google, Facebook и Microsoft, доминируют в этой области не только благодаря усердной работе и капиталу. Это нечто большее.

Цифры показывают, что Google и FB влияют на 70% всего интернет-трафика .

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

Наблюдать за этим из той точки, где мы находимся сейчас, просто удивительно. Недавним примером является Duplex от Google с его способностями к человеческому общению или даже синтетическая генерация изображений в реальном времени от NVIDIA которые почти неотличимы от реальных изображений. Но перенесемся на несколько лет вперед и представьте себе такой вымышленный сценарий: Facebook может использовать вашу историю чатов, чтобы предоставить вам персонального интеллектуального агента, который может отвечать на чаты в вашем мессенджере от вашего имени точно так же, как и вы! Кроме того, вы можете предоставить Amazon все свои банковские реквизиты и развернуть специально созданные списки покупок / продуктов (теперь это приобретено Wholefoods), которые соответствуют вашему финансовому положению и предпочтениям! Компания, занимающаяся разработкой нового генома, может использовать вашу последовательность ДНК, чтобы дать вам подробный список лекарств, которые действительно хорошо на вас подействуют.

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

Но, в конце концов, вы все равно сознательно позволили этому случиться с собой, верно? Вы выдали свои данные. Что еще вы могли бы сделать? Отключить Ethernet-кабель от маршрутизатора и читать новости из ежедневной газеты? Нет.. Кто бы это сделал? Сейчас никто не хочет отказываться от своей онлайн-активности только ради сохранения своей конфиденциальности в долгосрочной перспективе.

С другой стороны, даже если мы это делаем, даже если мы стираем нашу онлайн-идентичность ради конфиденциальности, это косвенно наносит ущерб эволюции искусственного интеллекта. Возможно, вы не хотите давать согласие на использование данных о вашем местоположении для исследований из-за проблем с конфиденциальностью, и это вполне понятно, но в то же время вы вносите свой вклад в создание барьера, который сдерживает инновации искусственного интеллекта. Машинное обучение (ML) и Глубокое обучение  (DL) требуют огромных объемов данных для хорошей работы, и наоборот, неструктурированные данные совершенно бесполезны без какой-либо обработки для извлечения значимой информации.

Homomorphic encryption в помощь

А что, если я скажу вам, что существует технология, способная решить все эти проблемы? Это верно, и на самом деле она существует уже много лет, но до сих пор она не использовалась из соображений практичности/безопасности. Это homomorphic encryption.

Что такое Homomorphic encryption?

Homomorphic encryption (HE) — это схема шифрования, которая позволяет выполнять вычисления с зашифрованными данными без нарушения их свойств или формата.

Более формально, пусть (P, C, K, E, D) — шифрование, где P — пространство открытого текста, C — пространство зашифрованного текста, K — пространство ключей, а E — операция шифрования. Если у нас есть открытые тексты a и b в P, k в K и выполняется следующее:

Тогда схема аддитивно гомоморфна. Тот же принцип применим и к другим математическим операциям.

Немного истории

Как я упоминал ранее, homomorphic encryption существует уже некоторое время, однако в последнее время его нельзя было не использовать на практике. Одной из первых попыток выполнения операций с зашифрованными данными была Yao’s Gabled Circuit, которая восходит к 1982 году. В своем исследовании он также определил печально известную задачу миллионера Яо, цель которой состоит в том, чтобы позволить двум миллионерам выяснить, кто из них богаче, не зная, сколько у них денег. К сожалению, эффективность решения Яо была очень низкой, и для получения результата требовалось много накладных расходов на связь.

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

На самом деле ограничения, встречающиеся в схемах homomorphic encryption, привели к их категоризации в следующие три группы:

1. Partial Homomorphic Encryption (PHE): допускает только один тип операции неограниченное количество раз.

2. Somewhat Homomorphic Encryption (SWHE): позволяет выполнять некоторые типы операций с ограниченным количеством раз.

3. Fully Homomorphic Encryption (FHE): позволяет выполнять все типы операций неограниченное количество раз.

Только в 2009 году Крейг Джентри выпустил свою глубокую докторскую диссертацию, в которой впервые была описана схема полностью homomorphic encryption (запишите это… этот человек однажды получит премию Тьюринга ). Хотя это все еще непрактично, он представил в своем исследовании основу для достижения FHE. Это вызвало большой интерес в академическом сообществе, и впоследствии появилось много улучшений и новых схем.

Предложение Джентри было основано на идеальных решетках. Хотя это было очень многообещающе, его было трудно реализовать из-за сложных математических концепций и вычислительной стоимости. В результате решетки стали горячей темой в криптографическом сообществе. В частности, проблема, основанная на решетке, становится все более популярной, главным образом из-за ее постквантовой сложности — обучения с ошибками (LWE), и она была использована в качестве основы для нового FHE в 2014 году .

Вскоре после диссертации Джентри Ван Дейк и др. представили FHE над целыми числами, стремясь к простоте. Наконец, другой FHE был предложен Лопесом-Альтом и др.  на основе криптосистемы с открытым ключом NTRU (на основе решетки), которая привлекла внимание благодаря своей эффективности.

Учитывая вышеизложенное, схемы FHE можно разделить на:

1. Основанные на Идеальной решетке 

2. Схемы с целыми значениями

3. Основанные на LWE 

4. NTRU -подобные

Применение

Все еще не видите варианты использования? Позвольте мне привести вам простой пример. Возьмем, к примеру, описанный выше сценарий с автономным чат-агентом Facebook. Используя homomorphic encryption, FB может хранить все ваши разговоры в чате локально, зашифровав их с помощью вашего ключа шифрования, и выполнять над ними операции. то есть обучить нейронную сеть отвечать на разговоры, не раскрывая никакой информации в ваших разговорах.

Проще говоря, HE идеально подходит для аутсорсинговой обработки. На иллюстрации ниже показано, как это работает:

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

Области применения бесконечны. Я могу продолжать, но я бы предпочел, чтобы этот раздел был коротким. Я призываю вас принять участие в местном хакатоне и прочитать поставленные задачи. Я уверен, что будет как минимум один случай, когда homomorphic encryption будет полезно

Текущее состояние homomorphic encryption

Homomorphic encryption стало активной областью исследований, которая привлекает большое внимание академических кругов. Крупные компании, такие как Microsoft и IBM, активно вносят свой вклад и исследуют эту область из-за ее потенциального влияния на облачную обработку. Новейшие схемы FHE могут быть практически применены к обычному оборудованию, и появилось несколько программных библиотек, которые упростили доступ и эксперименты с этой удивительной технологией.

В настоящее время наиболее новаторскими схемами FHE являются:

a. Fully Homomorphic Encryption without Bootstrapping (BGV)

b. FHEW: Bootstrapping Homomorphic Encryption in less than a second (SV)

c. Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 (CGGI16)

d. Somewhat Practical Fully Homomorphic Encryption (FV12)

Кроме того, уже доказано, что HE работает с ML и DL с точностью, близкой к незашифрованной, что весьма удивительно. Исследователи продемонстрировали выполнение алгоритмов линейного машинного обучения на зашифрованных данных, а также разработали основу для обучения и классификации зашифрованных данных с помощью глубоких нейронных сетей.

Двумя наиболее широко используемыми программными библиотеками для гомоморфного шифрования являются:

1. Простая зашифрованная арифметическая библиотека (SEAL) от Microsoft

2. HELib

Конечно, есть еще много возможностей для улучшений и экспериментов, но все же прогресс был поразительным. Если кто-то из вас является исследователем, разработчиком или предпринимателем, эта конкретная область быстро расширяется, и я настоятельно рекомендую следить за ней

Выводы

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

В целом homomorphic encryption станет краеугольным камнем в недалеком будущем для приложений для анализа данных, повышающих конфиденциальность.

Часть II. Как на самом деле понять Zero-Knowledge Proof

Zero-Knowledge Proof — это техника/метод, при котором вы доказываете кому-то, что вы что-то знаете, не раскрывая им то, что вы на самом деле знаете. Если это звучит немного бессмысленно, позвольте мне пояснить.

Допустим, вы знаете секрет о чем-то. Вы хотите убедить своего друга, что знаете этот секрет, не раскрывая ему секрет. Как бы вы это сделали? Вот где бизнес Zero-Knowledge Proof пригодится. Оказывается, эта концепция находит очень полезные применения в области криптографии (в том числе криптовалют).

В этом эссе я расскажу об  интуиции, стоящей за понятием Zero-Knowledge Proof , используя пару иллюстрированных примеров. После этого я перейду к рассмотрению формальных требований для установления Zero-Knowledge Proof. В конце этого эссе у вас в идеале должно быть интуитивное понимание концепции, а также формальных требований для ее реализации. Начнем.

Zero-Knowledge Proof с помощью сейфа

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

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

Затем вы просите своего друга положить сложенный лист бумаги в открытый сейф (который представляет собой беспорядочную комбинацию, когда дверь открыта). После этого вы просите своего друга закрыть сейф. На этом этапе вы оба убедитесь, что сейф заперт и не может быть открыт силой.

Теперь вы поворачиваете сейф так, чтобы ваш друг не видел, как вы вводите комбинацию. Вы вводите комбинацию, открываете сейф, разворачиваете бумажку и читаете текст. Как только вы запомнили текст, вы складываете лист бумаги, кладете его в сейф и снова запираете. Затем вы продолжаете показывать своей подруге текст, который она написала на листе бумаги.

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

Zero-Knowledge Proof с использованием пещеры Али-Бабы

Пример, который мы собираемся сейчас рассмотреть, был первоначально опубликован  Жаном-Жаком Кискватером  и др. в статье под названием «Как объяснить своим детям Zero-Knowledge протоколы » (ссылка в справочном разделе в конце этого эссе).

В этом гипотетическом примере старая пещера Али-Бабы была обнаружена в действительности. Это была не просто фантастика, все это время! Пещера имеет один вход и два возможных пути вокруг тороидальной геометрии с волшебной дверью на противоположной стороне входа. Дверь просто замыкает тороидальную цепь при открытии.

Пегги  пришла узнать о волшебных словах, открывающих дверь, и хочет доказать Виктору  , что она может творить волшебство, не раскрывая ему волшебные слова. Для этого она сначала входит в пещеру, и Виктор не знает, по какому пути (из двух) она пошла.

После этого Виктор стоит перед развилкой и выкрикивает «А» для пути по часовой стрелке и «Б» для пути против часовой стрелки. Если Виктор кричит «А», а Пегги идет по пути «Б», все, что ей нужно сделать, это открыть волшебную дверь и появиться с другой стороны. Предполагая, что у Виктора есть 50%-й шанс выбрать тот же путь, что и Пегги, Виктора нужно больше убеждать.

Если дуэт повторит эту игру 40 раз в честь 40 воров,  вероятность того, что Пегги правильно угадает все случаи чисто по счастливой случайности, составит 1 из 2²⁰ . Другими словами, дуэт может повторять игру столько раз, сколько необходимо, пока Виктор не будет убежден. После рассмотрения этого примера давайте теперь приступим к изучению некоторых формальных требований для установления Zero-Knowledge Proof.

Формальные требования для доказательства с нулевым разглашением

По формальным требованиям любое Zero-Knowledge Proof должно удовлетворять трем условиям:

1. Полнота

2. Надежность

3. Нулевое знание

Полнота  требует, чтобы оба игрока придерживались протокола и никто не жульничал. Здесь следует отметить одну интересную вещь:  неполные Zero-Knowledge Proof объясняют множество фокусов . Доказывающая (Пегги) использует какой-то обман, чтобы убедить проверяющую (Виктор) выполнить фокус. В идеальном Zero-Knowledge Proof обман и нарушение правил не допускаются (отсюда и полнота).

Надежность  требует, чтобы обманщику было маловероятно (не невозможно!) убедить честного верификатора. Вот чего добились Виктор и Пегги, повторив одну и ту же игру 40 раз, чтобы получить вероятность чистой удачи 1 из 2²⁰.

Наконец,  Zero-Knowledge требует, чтобы Виктор никогда не узнал секрет, хотя он убежден, что Пегги знает волшебные слова. Даже если бы подслушиватель подслушал их разговор, он услышал бы либо «А», либо «Б». Это не дало бы никакой полезной информации о самих волшебных словах.

Однако, если бы Виктор использовал подбрасывание монеты, чтобы назвать «А» или «Б» (чтобы гарантировать 50% вероятности того и другого), и записал все приключение с помощью видеокамеры, это нарушило бы требование о Zero-Knowledge. 

Заключительные замечания

Знаете ли вы, что имена «Пегги» и «Виктор» я выбрал не случайно? На самом деле в области Zero-Knowledge Proof принято  называть доказывающего Пегги , а  проверяющего Виктором .

Кроме того, важно отметить, что  «Zero-Knowledge Proof  отличаются от математических доказательств . Они просто стремятся убедить верификатора, убедившись, что вероятность удачи/мошенничества незначительна. Для этого типичное Zero-Knowledge Proof должно удовлетворять формальным требованиям полноты, достоверности и нулевого разглашения.

Эта концепция находит широкий спектр как технологических, так и этических приложений. Все, что требует системы аутентификации, может выиграть от Zero-Knowledge Proof при условии, что можно выполнить три необходимых условия полноты, надежности и с Zero-Knowledge.

Возможно, эта информация достаточно поверхностная и для понимания процесса практического/коммерческого использования данных технологий к этой теме необходимо будет вернуться в последующих статьях. Поэтому, если вы дочитали до конца и “в теме” вопроса  буду рад комментариям и рекомендациям.