Комментарии 35
Гм. Кто-то может объяснить, как можно определить, является ли письмо спамом, не зная, что в письме? Или в статье пример некорректный?
«обработка поискового запроса в Google в случае, если текст зашифрован, потребует примерно в триллион раз больше вычислений».
Т.е. сам Гугл не будет знать, что я там ищу? Но вряд ли это надо Гуглу.
Пришло письмо «Продам булочки»
Клиент зашифровал сообщение в «As%6vD7;!» и отправил на сервер и?..
Тут либо сервер умеет расшифровывать сообщение и детектить по базе, либо кто то что то не договаривает.
Конечно с письмом можно:
Head — не шифруем
Body — шифруем
Тогда сервер проверяет только адреса и заголовок, сверяясь с базой, не проверяя тело письма, но это совсем не то, о чем написано в статье.
И как можно:
в блокчейне, где сервер может манипулировать зашифрованными данными клиента без раскрытия содержимого информации. То есть сервер может выполнять запросы клиента, не зная, что он запросил.
Это вообще как?
Отправляя как выше в примере запрос «As%6vD7;!» по поиску клиентов кому нужны булочки, как сервер может дать клиентскую базу покупателей булочек, не расшифровав сам запрос?
Автор, велком с объяснениями!
Если булочки зашифрованы на сервере как «6vD7;!» а покупатели как «As%», то сервер может что то искать, но это совсем не то, это поиск по словарю, тогда вместо слов можно использовать только цифры. Но это не шифрование.
Объясните плиз с примером:
Клиент: «Продам булочки» -> «As%6vD7;!» (шифро сообщение на сервере)
PS: И тут пример только со статическим шифрованием, когда в любое время зашифрованное сообщение будет всегда идентичным, а если оно каждый раз будет разным, то это еще интереснее и непонятнее как это технически возможно.
Как не зная что в сообщении можно выполнить это сообщение?
— Fullmoon
Ну, навскидку: есть подстрока, сигнализирующая о спаме, мы вычисляем, как бы выглядел зашифрованный текст, в котором эта подстрока находится на позиции n.
Отвечу тут, тк ограничен в высказываниях.
Как вы вычислите если у 100 клиентов разный ключ щифрования, при этом допустим что один алгоритм шифрования.
Как вы без ключа узнаете содержимое?
У 100 человек будет 100 различных шифро-текстов «Продам булочки», а не одно на все 100 человек, иначе это не шифрование, а глупость какая то.
Суть этого гомоморфного шифрования в том, что спам-фильтр, произведя вычисления над зашифрованными данными, сам не будет знать результата (является ли письмо спамом или нет). Узнает об этом только владелец информации, расшифровав своим ключом ответ от фильтра.
Это работает так: допустим все вычисления байесовской вероятности того, что письмо — спам, происходят над зашифрованными данными с помощью только 2 операций: сложения и умножения. В итоге получается какое-то зашифрованное нечто, которое фильтр сам интерпретировать не сможет. Итоговую оценку вероятности узнает только владелец информации, расшифровав ответ. Но он не сможет понять, как эта оценка была получена (сам алгоритм) из исходной посылки, потому что у него только конечный результат.
Как реализовать байесовский (хотя бы) фильтр (с разбиением текста на отдельные токены и пр.) с помощью только сложения и умножения — это, я думаю, будет предметом еще чьей-нибудь докторской диссертации. Что-то мне подсказывает, что работать оно будет оооочень неторопливо. Это же как кораблик внутри бутылки пинцетом собирать.
Почему-то вспомнился movfuscator
Алгоритмы можно свести к арифметике над натуральными числами (кодировка Гёделя), но работать это будет очень неспешно. Сложно представить практическую пользу такого неспешного метода. Странно, что все примеры в статье довольно абстрактные. Хотя бы показали, как это может работать для блокчейнов.
Это выглядит, как довольно паршивый алгоритм шифрования, т.к. достаточно прогать через него все слова из словаря, чтобы научиться по хэшу декодировать слово. Потом владелец сервера может смотреть логи и понять, что все запросы, на которые сервер вычисляет 66096db4d3126b086f289e17386e2773, содержат слово "Продам". Я понимаю, что это только пример, но в самой статье такие же плохие примеры(
Тут либо сервер умеет расшифровывать сообщение и детектить по базе, либо кто то что то не договаривает
Как вы без ключа узнаете содержимое?
Не, все интереснее.
Для того что бы сервер не мог узнать запрос, ему нужно будет его "смешать" со всей базой данных, то есть индексы тут не помогут. Например если у Гугла поисковая база 100 терабайт, но нужно будет выполнить вычисления над запросом и всей базой.
Пример:
Клиент хочет узнать если ли слово (число) x в множестве А, которое известно серверу, но не хочет что бы сервер узнал x. Сам он множество А не знает.
Клиент отправляет $f(x)$ на сервер. Сервер считает $prod(f(x)-y | y in A) = prod(f(x-y) | y in A) = f(prod(x-y | y in A))$, здесь мы пользуемся гомоморфностью относительно сложения и умножения одновременно. Теперь это значение получает клиент, снимает шифрование и получает нулевое или не нулевое значение, по которому узнает ответ. (нулевое значение почти всегда означает что слово есть в множестве)
Если библиотека не даёт сделать $y -> f(y)$, то клиент может отправить ${b_i = f(2^i) | 0 <= i < N}$, тогда сервер может получить любую константу сложением $n < 2^N -> f(n) = f(sum(2^e | e in B)) = sum(f(2^e | e in B)) = sum(b_e | e in B)$, где B двоичное представление n.
Как реализовать байесовский (хотя бы) фильтр (с разбиением текста на отдельные токены и пр.) с помощью только сложения и умножения — это, я думаю, будет предметом еще чьей-нибудь докторской диссертации
Ну или наивный Байес, тут еще проще. Отправляем ${f(p_w) | w in U}$, bag of words,
Сервер возвращает линейную комбинацию $sum(a_w f(p_w) | w in U) =… = f(sum(a_w p_w | w in U))$. В итоге сервер не знает письма, а клиент не знает коэффициентов, все очень просто.
При желании можно и нейронку на таком входе посчитать, все упирается в функцию активации, для логистической можно экспоненту в ряд Тейлора разложить до какого-то члена, и должно нормально получиться, ну еще и делить придётся.
Естественно f должна меняться при каждом письме, иначе двух запросов с разными p_w и одинаковыми остальными значениями будет достаточно для того что бы узнать одно a_w.
Для того что бы работать с длинными словами, можно отправлять ${f(x_i) | 0 <= i < W}$, и перемножать $sum(f((x_i — y_i)^2) | 0 <= i < W)$, (вместо $(x-y)$) но тогда клиент раскрывает часть информации об $x$, но тем меньшую, чем больший размер слова доступен, и чего можно совсем избежать если преобразовать слова по принципу '{s_1,s_2,s_3} -> {(1,s_1),(2,s_2),(3,s_3)}'.
Ну, навскидку: есть подстрока, сигнализирующая о спаме, мы вычисляем, как бы выглядел зашифрованный текст, в котором эта подстрока находится на позиции n.
Впрочем, может быть и пример надуманный, да.
Математически задача выглядит как преобразование данных в зашифрованные блоки, над которыми можно производить простые арифметические операции, результаты которых сможет декодировать владелец ключа.
То есть письмо преобразуется в некий набор микрошифров, которые сможет прожевать нейросеть на недоверенном сервере, вычислить какой-то результат, но смысл результата останется тайной для владельца сервера. Только клиент, расшифровав результат своим ключом, сможет интерпретировать оценку как «спам-не спам». Понял так
Если вы можете операцию детектирования спама в письме выразить как набор сложений и умножений над числами, однозначно соответствующими этому письму, то вот это оно и есть.
Пусть у нас есть модель-классификатор, которая определяет, является ли сообщение спамом. У нас есть датасет, на котором ее обучили, все настройки и все такое.
Далее мы шифруем все эти данные и обучаем новую модель на зашифрованных данных. Теперь у нас есть вторая модель, которая умеет работать только с зашифрованными сообщениями.
И теперь результаты первой модели на незашифрованных сообщениях будут почти полностью совпадать с результатами второй модели на тех же самых, но зашифрованных сообщениях.
И при этом вторая модель даже знать не может, какое это было сообщение изначально.
позволяет неограниченные операции сложения и умножения на любом массиве данных
Вот если бы зашифрованные данные можно было сортировать в том же порядке в котором сортируется clear text, причём добавление нового элемента не требовало бы полной перешифровки массива...
Тем не менее, сделанные IBM оптимизации позволили существенно повысить производительность библиотеки, так что через несколько лет или десятилетий, она вполне может найти широкое применение в веб-приложениях.
А есть какие-то конкретные цифры? Когда я писал гомоморфное шифрование, то писал через умножение матриц, что, как мы все знаем, очень не бесплатная операция, и бесплатной ближайшие «несколько лет или десятилетий» она точно не станет.
Theorem 1.3.1(Informal).If E is bootstrappable, then, for any integer d, one can constructuct scheme E(d) that can evaluate any circuit (consisting of NAND gates) of depth d.
Под bootstrappable понимается что мы можем гомоморфно делать дешифрование.
Далее он строит такую схему E и в качестве гомоморфных операций она использует именно сложение и умножение.
Впрочем, в современных схемах полностью гомоморфного шифрования не обязательно должны быть именно сложение и умножение. В схеме GSW, например, сразу конструируется логический вентель NAND как гомоморфная операция.
Дорогое удовольствие. А если d нужно не десятки а сотни, то на канале передачи разоритесь.
Да, схема Джентри имеет скорее теоретическое значение, чем практическое. Современные схемы, такие как BGV, BFV, CKKS более практичны. AES, например, без проблем можно на них гомоморфно вычислить. Ну и они уже использовались в некоторых реальных проектах.
P.S. при чем тут канал передачи? Вычисления локально производятся.
Как вы собираетесь делать ветвление
Можно всегда считать обе ветки, а уже получатель сообщения как-нибудь догадается какой из результатов правильный. Разумеется, каждое ветвление будет очень дорогим. Но в статье как раз и упоминается, что такие операции сильно усложняют обработку.
Чем-то похоже на алгоритмы для GPU, где ветвления тоже дорогие.
Вероятно — миллионеры шифруют значения своих состояний, передают их арбитру, который выполняет гомоморфную операцию вычитания и получает еще какое-то зашифрованное число, но не знает — положительное оно или отрицательное. Зато миллионеры, имеющие ключи расшифровки узнать это могут.
Разумеется, пример очень абстрактный, подразумевается, что отрицательные состояния миллионеров тоже имеют смысл и ничуть не менее вероятны для сравнивающего.
IBM открыла инструмент полностью гомоморфного шифрования для Linux