Практическое применение алгоритмов гомоморфного шифрования?

Question

Похоже, в криптографии происходили интересные вещи: первая гомоморфная схема шифрования появилась недавно ( объяснение , HT ).Грубо говоря, это способ кодирования x в f(x), так что вы можете легко вычислить f(x+y), зная f(x) и f(y), даже если вы не можете легко восстановить x и y (ито же самое для f(x*y)).

Каковы практические применения для схем этого типа (после того, как их безопасность установлена)?Мне кажется, они могли бы сделать написание алгоритмов для манипулирования частными данными намного проще

Вот мои мысли :

1. электронное голосование
2. проверка целостности личных данных
3. есть ли шансчто могло бы помочь конфиденциальности в целом?

Пример : у меня есть счета в банках A, B, C. Компания X хочет подтвердить, что у меня более 1000 долларов США;он с радостью принял бы выписки из банков A, B, C или D, но, к сожалению, мне не хватает денег ни на одном счете.Банк А шифрует информацию о моих 500 долларах с помощью моего открытого ключа;Точно так же банки B и C шифруют информацию, что у меня есть 200 и 300 долларов соответственно.Они отправляют эти данные X, который добавляет их к некоторому числу, которое, как я демонстрирую, на самом деле зашифровано 1000 долларов (зашифровав 1000 долларов моим открытым ключом и продемонстрировав, что результат тот же).Я что-то доказал, не раскрывая X, сколько денег у меня на каждом счете.

Другой пример : Хорошие граждане X_1, ..., X_n объединяются, чтобы выбрать одного из двух кандидатов, один из которых - пьяница-латте A lв то время как другой является B любителем пушечного оружия (все имена вымышлены).Они решают, что хотят, чтобы голосование было частным, но быстрым.Они отправляют свои голоса в векторном формате (1, vote_A, vote_B, vote_None) в зашифрованном виде в Избирательную комиссию, которая добавляет их публично и получает результат в виде (count, count_A, count_B, count_None).После проверки этого count = count_A + count_B + count_None чиновники объявляют победу одного из кандидатов, после чего судья объявляет выборы недействительными по какой-то причине, не связанной с электронным голосованием, и сражался в суде в течение следующих 10 лет, но, эй,В любом случае это не моя проблема.

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

• Я бы особенно хотел увидеть ответы, содержащие код и / или разработку фреймворков, которыеимеют шанс быть использованным на практике, причина в том, что SO не является теоретической доской для информатики.

• Гомоморфный алгоритм, повторяющий то, что было сказано ниже в комментариях, позволяетсоздать программу, которая будет управлять данными, не зная их.К сожалению, типы программ несколько ограничены: у вас не может быть if (x=0) ..., потому что x зашифровано, и каждый шаг очень медленный (есть некоторые решетки).

Answer 1

Вот дикий выстрел в темноте:

Мы думаем о защите открытого текста от человека, выполняющего вычисления на нем. Но что, если целью было защитить как открытый текст, так и алгоритм?

Взять, к примеру, МРТ машины. Самая дорогая часть аппарата МРТ - это алгоритм, в котором аппарат анализирует данные магнитного резонанса. Из-за этого они надежно защищены аппаратными устройствами, предназначенными для уничтожения программы, прежде чем позволить себе быть проверенной ненадежной стороной (или кем-либо в этом отношении).

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

Так! Гомоморфное шифрование позволяет это делать, когда данные пациента и алгоритм защищены. «Полностью» гомоморфное шифрование (т. Е. Индуцирование кольцевого гомоморфизма на зашифрованные данные) позволяет гораздо более эффективный и надежный набор вычислений для обработки данных.

Answer 2

Возможно, вас заинтересует довольно резкое отрицательное мнение Брюса Шнайера о гомоморфном шифровании по адресу:

http://www.schneier.com/blog/archives/2009/07/homomorphic_enc.html?nc=11

Answer 3

Самое большое применение гомоморфного шифрования было бы в интеллектуальном анализе данных, ИМХО. Использование этого алгоритма может одновременно решить проблемы как конфиденциальности, так и выявления тенденций. Например, скажем, ваша компания размещает информацию о продажах у какого-либо поставщика SAS. Теперь этот провайдер может предоставить вам сложные услуги по интеллектуальному анализу данных без необходимости раскрывать вашу реальную информацию. По сути, вы сможете отправить свои данные поставщику вычислений, заставить его использовать свои циклы ЦП для вычисления от вашего имени и отправить вам зашифрованные данные обратно. Это было бы действительно замечательно для компаний, которые хотят перейти на облачные системы, но имеют проблемы с конфиденциальностью / IP, которые мешают им сделать это.

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

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

Answer 4

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

В обозначениях функций это будет:

Пользователь подписывает:

знак (открытый текст, закрытый ключ) = зашифрованный текст

и передает:

отправить (открытый текст, зашифрованный текст, сертификат)

Приложение получает сегменты:

открытый текст = требуемый открытый текст + другой открытый текст

и вычисляет то же преобразование зашифрованного текста, используя что-то вроде:

если зашифрованный текст: обычный текст, то ?? :: требуемый открытый текст

чтобы найти желаемый шифротекст

Приложение перенаправляет желаемый контент только на внешний сервис:

отправить (желаемый открытый текст, желаемый шифрованный текст, сертификат)

И служба может проверить это сообщение, как если бы пользователь отправил его напрямую.

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

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

Одним из примеров может быть простая система заказа посылок - я отправляю веб-приложению запрос на покупку коллекции предметов. Чтобы быть сверхбезопасным, я подписываю Заказ на поставку, который подтверждает, что я хочу (и обещаю оплатить) некоторое количество товаров, отправленных в определенное место, к определенной дате и с определенной информацией об оплате. Теперь .. веб-приложение захочет, чтобы произошло несколько вещей:

• Финансам нужно снять деньги с моего счета и начать получать от меня платеж
• В инвентаре необходимо вытащить предметы со склада или справиться с любыми проблемами на складе
• Доставка необходимо получить из инвентаря и переместить вещи на мой адрес

Инвентаризации или доставке нет причин знать, как я оплачиваю свой счет. И, возможно, у финансов не будет причин знать мой адрес доставки ... В каждом случае требуемый открытый текст и требуемый зашифрованный текст изменяются в зависимости от того, кто является получателем. Это еще более эффективно в системе, такой как используемые на Amazon.com книги, в которой сущность, которую я купил (Amazon), отличается от сущности, предоставляющей предмет (продавец подержанной книги).

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

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

Answer 5

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

Итак, как вы можете использовать это?

Давайте посмотрим на карту / Сокращение схемы и схемы сокращения для набора входов.

Первые данные:

Мы, вероятно, не хотим, чтобы клиент зашифровал все данные, которые мы собираемся искать, поэтому вы можете предоставить зашифрованную 1 и зашифрованную 0 серверу и позволить ему использовать структуру кольца для создания произвольные зашифрованные целые числа для нас, или мы можем просто использовать их как биты. Таким образом, сервер может предоставить некоторые или все данные, которые мы ищем. Для целых чисел он может построить их по крестьянской арифметике (double или double и добавить 1 для каждого бита), для битов он просто обеспечивает соответствующий зашифрованный бит.

Мы можем смешивать и сопоставлять логические и целочисленные значения в наших проектах, получая if / then / else (который требует оценки обеих ветвей в стиле SIMD), оценивая cond * then + (1 - cond) * else, используя 1 как true и 0 равно false в cond, так что вы можете избежать использования встроенной арифметики вашего кольца, чтобы сделать ваши схемы более поверхностными.

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

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

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

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

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

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

Итак, подведем итог,

1. Дайте серверу зашифрованные 1 и 0 и любое зашифрованное metainfo для вашей карты и уменьшите количество функций.
2. Для каждой точки данных закодируйте ее в ваше гомоморфное кольцо, подайте в схему вашей карты как входные данные, так и метаинформацию, чтобы получить значение, подходящее для сокращения.
3. В сбалансированном двоичном дереве (или другом сбалансированном расположении, чтобы минимизировать высоту дерева), примените операцию сокращения к выходным сигналам вашей схемы и любой зашифрованной карте metainfo.
4. Передать результат клиенту для расшифровки

Answer 6

Я не знаю, насколько дорогими будут вычисления f(x) + f(x), но, возможно, их можно использовать как способ реализации зашифрованной базы данных.

Вы можете хранить 1 миллион строк некоторых данных, зашифрованных как f(x_1), f(x_2), ... f(x_n). Вы могли бы сделать

SELECT SUM(x)
FROM Foo
WHERE y = 'some value'

Что можно рассчитать, выполнив сначала SUM(f(x)), а затем расшифровав до SUM(x).

Answer 7

Электронное голосование действительно является практическим применением гомоморфного шифрования, т.е. http://heliosvoting.org/

Answer 8

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

Answer 9

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

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

Answer 10

Некоторые банковские приложения могут стать быстрее с помощью гомоморфного шифрования.

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