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

Question

Похоже, там в криптографии происходили интересные вещи:первый гомоморфное шифрование схема появилась недавно (объяснение, ХТ).Грубо говоря, это способ кодирования 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 объединяются, чтобы выбрать одного из двух кандидатов, одним из которых является liber, пьющий латте.Al в то время как другой - это Bлюбитель оружия с иглой (все имена вымышлены).Они решают, что хотят, чтобы голосование было закрытым, но быстрым.Они отправляют свои голоса в векторном формате (1, vote_A, vote_B, vote_None) зашифрованные данные передаются Избирательной комиссии, которая добавляет их публично и получает результат в виде (count, count_A, count_B, count_None).После проверки этого count = count_A + count_B + count_None, официальные лица объявляют о победе одного из кандидатов, после чего выборы объявляются недействительными судьей по какой-то причине, не связанной с электронным голосованием, и я веду борьбу в суде в течение следующих 10 лет, но, эй, в любом случае, это не моя проблема.

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

В функциональной нотации это было бы:

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

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

и передает:

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

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

открытый текст = Желаемый исходный текст + Другой исходный текст

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

если зашифрованный текст::открытый текст, то ??::desiredPlaintext

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

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

отправить (desiredPlaintext, desiredCiphertext, сертификат)

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

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

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

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

• Финансам необходимо списать средства с моего счета и начать получать от меня платежи
• Инвентаризация необходима для изъятия товаров со склада или решения любых проблем, связанных с отсутствием товара на складе
• Для доставки необходимо получить товар со склада и перевезти его по моему адресу

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

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

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

Answer 3

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

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

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

Answer 4

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

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

Answer 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).

Answer 6

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 7

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

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

Answer 8

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

Answer 9

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

Answer 10

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

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