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

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

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

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

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

Знаки пользователя:

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

и передает:

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

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

plaintext = desirePlaintext + otherPlaintext

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

if ciphertext :: plaintext, то ?? :: desirePlaintext

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

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

send (desirePlaintext, desireCiphertext, certificate)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

With this you can execute an arbitrary non-recursive circuit of bounded depth, so given a logarithmic key length you can execute an NC1 algorithm (basically a feed-forward Boolean circuit).

So, how can you use this?

Lets look at Map/Reducing a circuit and reduction scheme over a set of inputs.

First the data:

We probably don't want the client to have to have encrypted all of the data we are going to search, so you can provide an encrypted 1 and an encrypted 0 to the server, and let it use the ring structure to construct arbitrary encrypted integers for us, or we can just use those directly as bits. That way the server can provide some or all of the data that we are searching through. For integers it can construct them by peasant arithmetic (double or double and add 1 for each bit), for bits it just provides the appropriate encrypted bit.

We can mix and match boolean and integer values in our designs, obtaining an if/then/else (that requires evaluating both branches SIMD style) by evaluating cond * then + (1 - cond) * else using 1 as true and 0 as false in cond, so you can get away with using the built in arithmetic of your ring to make your circuits more shallow.

On the other hand, we may have pre-encrypted some data as well, but since you'll have to keep recycling the same key set to use it, this becomes seriously tricky to get right.

So, now we have server provided data. Now, encrypt the stuff you don't want the server to know, like what it is you are searching for, and have them feed that into the circuit at the right points as well, say as an extra input to your map function.

We should be able to map an arbitrary NC1-like circuit over each input to extract a field, multiply some values, and generally map it into a form that you can reduce cheaply.

Then reduce those fragments using more small circuits, such as for a simple monoid that has a nicely size-bounded result. (i.e. you map to obtain a bit that indicates if you found a match, and then you reduce by counting those bits with a small adder circuit)

Since you only need to construct the circuit logically and simulate its execution on these encrypted bits in the homomorphic ring, you could probably implement it relatively quickly using a small DSL, i.e. something like Lava in Haskell, assuming you got the homomorphic encryption pieces straight.

Also, keep in mind that each gate is seriously expensive to execute.

So, to summarize,

1. Give the server an encrypted 1 and 0 and any encrypted metainfo for your map and reduce functions.
2. For each data point, encode it into your homomorphic ring, feed your map circuit both the input and the meta info to obtain a value suitable for reduction.
3. In a balanced binary tree (or other balanced arrangement to minimize tree height), apply your reduction operation to the output from your circuit and any encrypted map metainfo.
4. Hand the result over to the client for decryption