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

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

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

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

электронное голосование
проверка целостности личных данных
Есть ли шанс, который поможет обеспечить конфиденциальность в целом?

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

Другой пример. Хорошие граждане X_1,..., X_n объединяются, чтобы выбрать одного из двух кандидатов, одним из которых является латте-выпивка lib 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 зашифрован, и каждый шаг очень медленный (есть некоторые решетки).

Ответ 1

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

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

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

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

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

Ответ 2

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

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

Пользовательские знаки:

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

и передает:

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

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

plaintext = requiredPlaintext + otherPlaintext

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

если ciphertext:: plaintext then??:: wishPlaintext

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

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

отправить (желательноPlaintext, wishCiphertext, сертификат)

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

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

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

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

Финансирование должно оплачивать мою учетную запись и начать получать платеж от меня.
Инвентарь должен вытаскивать предметы со склада или решать любые проблемы с запасом.
Доставка должна быть получена из инвентаря и переместить материал на мой адрес

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

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

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

Ответ 3

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

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

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

Ответ 4

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

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

Ответ 5

Я не знаю, насколько дорого будет вычисление 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).

Ответ 6

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

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

Давайте посмотрим на карту/Уменьшение схемы и схемы редукции по набору входов.

Сначала данные:

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

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

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

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

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

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

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

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

Итак, чтобы подвести итог,

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

Ответ 7

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

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

Ответ 8

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

Ответ 9

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

Ответ 10

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

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