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

Можешь объяснить в каком месте в коде нужна верхняя граница для n

У тебя нет инструкции goto. Любой цикл тебе надо полностью развернуть. Т.е. цикл вида

for (int i = 0; i < n; i++) {
}

будет преобразован в конструкцию вида

i = 0;
if (0 < n) {
  тело цикла
}
i = 1;
if (1 < n) {
  тело цикла
}
...
i = max_n;
if (max_n < n) {
   тело цикла
}

На самом деле у тебя инструкции if тоже нет. У тебя есть только сложение и вычитание. Т.е. код вида

if (cond) {
    a = c1;
}

где cond это 0 или 1, преобразуется в

if (cond) {
    a = c1;
} else {
    a = a;
}

и в итоге в

a = c1 * cond + a * (1 - cond)

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

Не знаю, я просто повторил объяснение.

то я им шифрую «иванов» и делают поиск

Не, там типа: есть школа номер 69, и нужно узнать сколько учеников болело ветрянкой. Делаешь запрос – узнаёшь. Если все или никто – то это палево. Если нет – то ты ничего не узнаешь – только количество и всё.

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

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

Иными словами система требует всё равно подхода и ограничений.

Вообще это всё дело неплохо бы ввести себе банкам и сотовым операторам. А то у них там утечки персональных данных на каждом шагу.

Тут возникает пикантный нюанс распределения ключей. Который при массовой вами описанной схеме, коллега, я не понимаю, как решать. Если я загрузил мои данные и мой открытый ключ, система что-то сделала, зашифровала результат на моем открытом ключе и передала мне, понятно. Но если есть какие-то облачные данные и я и ещё овер 9000 народу хочет с них аналитику, то как?

PS криптография никогда не сможет закрыть дыру организационного уровня.

Таким образом, FHE позволяет работать с данными даже не расшифровывая их

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

нельзя из сложения и умножения сделать машину Тьюринга

Хорошо бы доказать.

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

Но я не копенгаген в этом вопросе.

Ассиметричный.

Как так, ключ симметричный, процедура шифрования одинаковая?

Поставка осуществляется в виде Docker-контейнеров для трех дистрибутивов: CentOS, Fedora и Ubuntu Linux.

А что, шареные либы - это уже не модно? Теперь каждый тулкит свой дистр тянет?

А что до гомоморфного шифрования - у него всегда была, есть и будет одна существенная проблема: уязвимость к атакам на гомоморфизм. Просто by design.

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

Вообще, это защита от сервера. И что там наделали IBM я не знаю. Но в теории, тут пишут, что вариант всё таки есть.

Он симметричный всередине процедуры шифрования, а не подаётся готовым на её вход.

В общем нельзя из сложения и умножения сделать машину Тьюринга.

Похоже на то, спасибо.

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

Коллега, всё-таки определения надо использовать общепринятые.

Упоминали уже об ужасной тормознутости этого шифрования? Искать ключевое слово в реальной БД выйдет очень долго и дорого. Чтобы защитить БД от хостера покупайте процессоры EPYC с шифрованием RAM.

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

Запрос на поиск тоже от тебя и слово для поиска тоже зашифровано тобой. Удалённая система видит два зашифрованные блока только.

Зачем ломать шифр, если можно ломать докер? Он де не безопасен by design

При чем здесь это? Там речь шла о двух битах. На сложениях и умножениях можно реализовать любую функцию, которая преобразует два бита. Это можно без циклов.

В общем нельзя из сложения и умножения сделать машину Тьюринга.

Похоже на то, спасибо.

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

Ну вот я понимаю, что любую функцию от любых входов реализовать можно, но пример Legioner меня смутил. «полный по Тьюрингу базис» == «полнота по Тьюрингу»? Если нет, то это объяснит всю путаницу.

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

Безумный мир становится еще безумнее

Нашёл забавную страничку, читаю (вроде как в 8 инструкций впихивается)

http://david.carybros.com/html/minimal_instruction_set.html

https://en.wikipedia.org/wiki/One_instruction_set_computer

Cryptoleq[edit] Cryptoleq processor made at NYU Abu Dhabi Cryptoleq[15] is a language consisting of one instruction, the eponymous, is capable of performing general-purpose computation on encrypted programs and is a close relative to Subleq. Cryptoleq works on continuous cells of memory using direct and indirect addressing, and performs two operations O1 and O2 on three values A, B, and C:

[..]

A program written in Subleq can run on a Cryptoleq machine, meaning backwards compatibility. Cryptoleq though, implements fully homomorphic calculations and since the model is be able to do multiplications. Multiplication on an encrypted domain is assisted by a unique function G that is assumed to be difficult to reverse engineer and allows re-encryption of a value based on the O2 operation: [..]

The multiplication algorithm is based on addition and subtraction, uses the function G and does not have conditional jumps nor branches.

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

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

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

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

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

Гомофобное шифрование? Ну наконец-то!

Вообще это всё дело неплохо бы ввести себе банкам и сотовым операторам. А то у них там утечки персональных данных на каждом шагу.

Не получится. Либо всё будет работать только по предоплатной/контрактной схеме. Кредит надо знать с кого требовать. А то, что знают двое - знает и свинья.

Тем кто не понимает как это «в целом» работает:

Работает как любой процессор. Процессору глубоко всё равно, какой текст в какой кодировке искать, какой канал усиливать и до каких значений. Алгоритм оперирует набором битов. Также и здесь, отправляется набор битов, процессор их обрабатывает, выдаёт на выход другой набор битов (найдено/не найдено, усиленный на 25% красный канал и т.д.)

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