IBM выпустила для Linux тулкит для реализации полностью гомоморфного шифрования (FHE)

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

И вот тут мы приходим к вопросу доступа к ключам шифрования. Но это будет другой вопрос.

Пример с поиском в тексте вообше неадекватный. Чтобы стороняя система могла искать паттерн в тексте, это значит, что буквы должны шифррваться всегда одинаково. Например, ‘и’ это всегда 1, ‘в’ - 2, ‘а’ - 3 и тд. Порядок буков должен быть тем же, что и в оригинале.

Такое шифрование ломается банальным частотным анализом. По сути-то надо просто восстановить таблицу сорстветствия ‘буква-код’.

Толку в таком шифровании не очень-то много.

взять хоть режим ECB, при применении которого сохраняются некоторые особенности открытого текста

Пляшущие человечки? Шифр Цезаря? Ну такое себе…

Приведённый выше пример — это гомоморфное сложение, умножение тоже по аналогии.

Во-первых, на симметричных ключах в этом смысла нет, во-вторых куда делся маркант?

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

Очередной биткоин…

выглядит эта технология больше как подстава чтобы ей доверили данные.

Именно.

на странице проекта на GitHub

…написано, что проект распространяется по лицензии MIT, основной язык — C++.

Можно было бы добавить это в новость.

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

Ну типа там, если нужно сохранить например порядок относительно любого преобразования, то нет ли такого, что ничего не останется, кроме как превратить все в какое-нибудь кольцо-поле, изоморфное 1..n %)

Ну типа там если у тебя для любых a<b f(a)<f(b)…

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

Можно привести пример из реальной жизни, для чего это может быть использовано?

У меня есть алгоритм обработки изображений. Например поиск лиц. Я потратил много времени и сил в разработку этого алгоритма и теперь хочу его монетизировать. Я не хочу отдавать никому его, я хочу запускать его на своём сервере.

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

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

Это неправда. Вот такой цикл:

number n = read_input();
number i = 0;
while (cmp_lt(i, n)) {
    print(i);
    i = inc(i);
}

ты не сможешь реализовать на сложениях, если у тебя нет верхней границы n_max.

архив почты можно сканировать на ключевое слово не расшифровывая его.

А как такое шифрование звщищают от частотного анализа?

Мне вот тоже не понятно: смысл шифрования - убрать повторяющиеся элементы. Смысл МО - как раз их выявлять. То есть полностью противоположные.

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

Ох уж шалуны, всё норовят гомоморфным сделать )))

Если серьезно, сути революции я не понял, квантовое шифрование уже не нужно?

все виды поиска … кажутся странными.

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

Если серьезно, сути революции я не понял, квантовое шифрование уже не нужно?

Каким боком тут квантовое шифрование, вся суть которого — специально отведённый канал связи с надёжной защитой от искажения и подслушивания?

Сначала прочитал как «гомофобное шифрование».

Оно-то и контринтуитивно: классические схемы шифрования делают зависимость от предыдущих данных. В т.ч. для этого и нужен initialization vector.

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

Ассиметричность - это не свойство шифра, а свойство ключа.

Ну, не знаю:

Public-key cryptography, or asymmetric cryptography, is a cryptographic system that uses pairs of keys:

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

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

Гомоморфное шифорование позволит узнать только то, что клиент правильно считает. А правильно посчитать можно на ложных исходных данных.

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

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

В ML-примерах больше смысла, поскольку там идёт аутсорс обработки больших объемов данных, которые калькулятор не потянет.

Множество ключей определяется алгоритмом.

Хочу чтобы банк не знал сколько у меня денег, кому я их плачу и от кого получаю.

Не только банк знает. А вообще, ты хочешь уходить от налогов или для торговли запрещенными веществами?

ты хочешь уходить от налогов или для торговли запрещенными веществами?

Да. Я много чего хочу. А что, за желания и прочие «мыслепреступления» есть ответственность? Твой вопрос тоже «мыслепреступление», кстати

ты не сможешь реализовать на сложениях, если у тебя нет верхней границы n_max.

Можешь объяснить в каком месте в коде нужна верхняя граница для n и почему её наличие ломает Тьюринг-полноту? Или речь о том, что «лента» в реальных компьютерах не бесконечная? Это да, но гомоморфное шифрование здесь не хуже любой реальной машины, которые называют полными, хотя формально можно и придраться.

а можно эту штуку использовать для дрм-щины?

типа если контент больше нигде не надо расшифровывать - это ведь рай для копирастов :)

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

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

Для игр уже давно придуман Steam, PSN, Origin и т.д.

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

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

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

В 1970-тых некоторые математики высказали ПРЕДПОЛОЖЕНИЕ (могли сокрыть и неопубликовать), что возможно существуют такие крыптографтческие алгоритмы, которые разрешают зашифровать данные на клиенте, передать на сервер и там их обработать в шифрование виде, шифрованный результат вернуть на клиент и только клиент сможет расшифровать результат обработки.

Например: шифруем на клиенте 2 и 2 передаем на сервер в шифрование выде, на сервере не расшифровывая их складываем и полученный шифрованный результат возвращаем на клиент, где он расшифровывается в 4.

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

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

Да, но лучше свое держать при себе и обрабатывать у себя.

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

Нет. Если длина ключа равна длине текста.

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

Это решается маркантом.

Как можно найти что-либо в случайной равновероятной последовательности?

Как можно найти что-либо в случайной равновероятной последовательности?

В случайной равновероятной последовательности можно найти случайную равновероятную подпоследовательность.

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

кроме того, пока криптографы пытались осилить банальные операции за какое-то вменяемое время, многие задачи удалось решить алгоритмически. например есть всякие privacy-preserving алгоритмы (та же сумма):

ChrisClifton,MuratKantarcioglu,JaideepVaidya,XiaodongLin,andMichaelY. Zhu. 2002. Tools for Privacy Preserving Distributed Data Mining. SIGKDD Explor. Newsl. 4, 2 (Dec. 2002), 28–34.

Yehuda Lindell and Benny Pinkas. 2008. Secure Multiparty Computation for Privacy-Preserving Data Mining. IACR Cryptology ePrint Archive (2008), 197.

в общем, сугубо фанатская вещь

Классический Аль-Гамаль:

Алиса:
Основание степени - Х
Секретный ключ - а
Открытый ключ Х**а
Боб:
Основание степени - Х
Секретный ключ - b
Открытый ключ - Х**b

Алиса передаёт Бобу Х**а
Боб передаёт Алисе Х**b

Общий ключ шифровки расшифровки для Алисы и Боба:
(Х**a)*(Х**b) = X**(a+b) 

Дальше симметричное шифрование. 

Получить а или b через логарифмирование можно только полным перебором. 

В RSA не так, там ключи односторонние. А*В=С
С - открытый ключ 
А и B - секретный. 
У Алисы и Боба свои наборы А, В и С. 

PS можно использовать односторонние ключи и на симметричном алгоритме. Алгоритм от этого станет ассиметричным?

Алиса > Боб ключ А

Боб > Алиса ключ Б

Алгоритм тривиальный, сложение посимвольно: Текст + Ключ = Шифротекст

Именно что.

Например: шифруем на клиенте 2 и 2 передаем на сервер в шифрование выде, на сервере не расшифровывая их складываем и полученный шифрованный результат возвращаем на клиент, где он расшифровывается в 4.

И тут выясняется, что смысл этих 2, 2, 4 задается в операциях над ними. И тут вылезает утинная типизация. Если нечто лает как твоя любимая собака (утка), бегает как твоя любимая собака (утка), то это нечто - твоя любимая собака (утка).

То есть твои операции над зашифрованными данными придают смысл (расшифровывают) эти зашифрованные данные.

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

можно использовать односторонние ключи и на симметричном алгоритме. Алгоритм от этого станет ассиметричным?

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

А как такое шифрование звщищают от частотного анализа?

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

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

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

Работает это так, вот есть три числа 2 4 6 и их надо сложить.
Заказчик их шифрует гомоморфным шифром и отсылает исполнителю с игструкцией провести сложение трёх чисел.
тсполнитель в соответствии с инструкцией выполняет над шифротекстом действия и результат отсылает обратно.
После расшифровки вместо чисел 2 4 6 видим 12.

Зашифровать не проблема. А вот расшифровать…

гомоче? это симметричное или ассиметричное?

Я привёл в пример аль-гамаля. Он симметричный или ассиметричный?

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

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

Да, всё хотел спросить. Вот у меня три числа 2, 4 и 6. Я их зашифровал в 3, 5 и 7. Отправил туда, ну и дальше, как описано.

Хочу повторить операцию. На выходе моего шифрования будет опять 3, 5 и 7 или что-то другое?